记 2018/4/29 qbxt 测试（提高基础班）
简单的 NOIP 模拟赛
竞赛时间： 2018 年 4 月 29 日 13:30-17:00
| 题目名称 | 乘法 | 求和 | 计数 |
| 输入文件名 | mul.in | sum.in | count.in |
| 输出文件名 | mul.out | sum.out | count.in |
| 每个测试点时限 | 1 sec | 4 sec | 1 sec |
| 内存限制 | 128MB |
128MB | 128MB |
| 测试点数目 | 10 | 10 | 10 |
| 每个测试点分值 | 10 | 10 | 10 |
| 是否有部分分 | 无 | 无 | 无 |
| 题目类型 | 传统 | 传统 | 传统 |
T1 期望得分：100；实际得分：100
乘法
【问题描述】
给定正整数n，m，p，你需要输出 n * m 对 p 取模后的值
【输入文件】
输入文件为 mul.in
输入为一行 n, m, p
【输出文件】
输出文件为 mul.out
输出一行为一个整数，为所求的答案
【输入输出样例】
| mul.in | mul.out |
| 11 22 10 | 2 |
【数据规模和约定】
对于30%的数据，n, m, p <=10000;
对于60%的数据，n, m, p <= 109
对于100%的数据， n, m, p <= 1018
【一些提示】
以下是一些对取模操作的介绍：
一个整数a对一个整数p取模的值，是一个不超过p的非负整数b，并且a-b是p的倍数。可以证明，满足条件的b有且只有一个；
一些运算在取模前后仍然成立，例如：
两个数的和对p取模的值等于两个数先对p取模，再求和，在取模；
两个数的乘积对p取模的值等于两个数先对p取模，再求乘积，再取模
但两个数的除法没有类似的性质
思路：快速乘（类似于快速幂） or 高精
#include<iostream> #include<cstring> #include<cstdio> using namespace std; long long n, m, p; long long Mul(long long x, long long y){ long long res = 0; x %= p; y %= p; while(y) { if(y & 1) res = (res+x) % p; x = (x+x) % p; y >>= 1; } return res; } int main() { //freopen("mul.in","r",stdin); //freopen("mul.out","w",stdout); cin >> n >> m >> p; cout<< Mul(n, m); //fclose(stdin); fclose(stdout); return 0; }
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> namespace BigInteger { #define maxn 10005 using std::sprintf; using std::string; using std::max; using std::istream; using std::ostream; struct Big_integer { int d[maxn],len; void clean() { while(len>1&&!d[len-1]) len--; } Big_integer() { memset(d,0,sizeof(d)); len=1; } Big_integer(int num) { *this=num; } Big_integer(char* num) { *this=num; } Big_integer operator = (const char* num) { memset(d,0,sizeof(d)); len=strlen(num); for(int i=0;i<len;i++) d[i]=num[len-1-i]-‘0‘; clean(); return *this; } Big_integer operator = (int num) { char s[10005]; sprintf(s,"%d",num); *this=s; return *this; } Big_integer operator + (const Big_integer& b) { Big_integer c=*this; int i; for(i=0;i<b.len;i++) { c.d[i]+=b.d[i]; if(c.d[i]>9) { c.d[i]%=10; c.d[i+1]++; } } while(c.d[i]>9) { c.d[i++]%=10; c.d[i]++; } c.len=max(len,b.len); if(c.d[i]&&c.len<=i) c.len=i+1; return c; } Big_integer operator - (const Big_integer& b) { Big_integer c=*this; int i; for(i=0;i<b.len;i++) { c.d[i]-=b.d[i]; if(c.d[i]<0) { c.d[i]+=10; c.d[i+1]--; } } while(c.d[i]<0) { c.d[i++]+=10; c.d[i]--; } c.clean(); return c; } Big_integer operator * (const Big_integer& b) const { int i,j; Big_integer c; c.len=len+b.len; for(j=0;j<b.len;j++) for(i=0;i<len;i++) c.d[i+j]+=d[i]*b.d[j]; for(i=0;i<c.len-1;i++) { c.d[i+1]+=c.d[i]/10; c.d[i]%=10; } c.clean(); return c; } Big_integer operator % (const Big_integer& b) { int i,j; Big_integer a=0; for(i=len-1;i>=0;i--) { a=a*10+d[i]; for(j=0;j<10;j++) if(a<b*(j+1)) break; a=a-b*j; } return a; } bool operator < (const Big_integer& b) const { if(len != b.len) return len<b.len; for(int i=len-1;i>=0;i--) if(d[i]!=b.d[i]) return d[i]<b.d[i]; return false; } string str()const { char s[maxn]={}; for(int i=0;i<len;i++) s[len-1-i]=d[i]+‘0‘; return s; } }; istream& operator >> (istream& in,Big_integer& x) { string s; in>>s; x=s.c_str(); return in; } ostream& operator << (ostream& out,const Big_integer& x) { out<<x.str(); return out; } } using namespace BigInteger; using namespace std; Big_integer a,b,k; int main() { //freopen("mul.in","r",stdin); //freopen("mul.out","w",stdout); cin>>a>>b>>k; cout<<a*b%k; //fclose(stdin); //fclose(stdout); return 0; }
T2 期望得分：30；实际得分：0 qwq
求和
【题目描述】
给定n个正整数d1 , d2 , d3 ..... dn。如果取出其中的任意两个数（可以相同） ，则可以得到这两个数的和。对于n个数，则至多可以产生n*(n + 1) / 2 种不同的和。
给出正整数 m，你需要判断： 是否存在两个整数 u, v , 满足 du + dv = m.
【输入文件】
输入文件为 sum. in。
本题一个输入中包含多组数据。 输入第一行为一个整数 T , 表示数据组数。对于每组数据， 输入的第一行为两个正整数 n, m，输入的第二行为 n 个正整数 d1, d2, d3 ..... dn
【输出文件】
输入文件为 sum.out。
输出 T 行， 每行一个整数。 如果正整数 u, v 存在， 则输出 1； 否则输出 0。
【输入输出样例】
| sum.in | sum.out |
|
2 3 3 2 3 4 3 4 1 2 4 |
0 1 |
【数据规模和约定】
对于30%的数据，满足 n <= 1000, m <= 10000;
对于60%的数据，满足 n <= 105；
对于另30%的数据，满足 m <= 107;
对于100%的数据，满足 1 <= n <= 106, 1 <= di <= 109, 1 <= T <= 20.
【一些提示】
在下发文件中附有文件 sample.cpp， 包含了自定义函数 read()及其使用示例。 对于本题，请务必使用 read()函数进行读入， 否则可能会有时间的问题。
思路： 30 分： 暴力
60 分： 排序后， 两根指针进行扫?。
另 30 分： 用计数数组记录数的分布
100 分： 在使用计数数组的基础上进行拓展。考虑设置一个数 b ，把每个di 写成 di = ai * b + ri ;并且把每个 di 按 ai 的值分成若干组，ai 相同的数放在一组里。
考虑一次性处理某一组的数。 如果假设 du + dv = m 的一个数在某一组中，那么另一个数的分布范围一定不超过两组。 所以， 如果要检测某一组的数是否可以作为一个加数， 只需要把另外的两组放入计数数组即可。 这样就解决了计数数组开不下的问题。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> #include<vector> using namespace std; typedef long long ll; typedef vector<int>::iterator iter; const int N = 1000010, M = 100000; int d[N]; int a[M]; vector<int> block[M]; int cnt[M * 4]; int read() { int x=0;char ch=getchar(); while(ch<‘0‘||ch>‘9‘) ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x; } int main() { freopen("sum.in","r",stdin); freopen("sum.out","w",stdout); setvbuf(stdin, new char[1 << 20], _IOFBF, 1 << 20); setvbuf(stdout, new char[1 << 20], _IOFBF, 1 << 20); int T = read(); while (T--) { int n = read(), m = read(); int maxblock = m / M; int ans = 0; for (int i = 0; i <= maxblock; i++) block[i].clear(); int tmptme = clock(); while (n--) { int x = read(); int y = x % M; x /= M; block[x].push_back(y); } for (int i = 0; i <= maxblock; i++) { int lblock = (m - (i + 1) * M + 1) / M; int rblock = (m - i * M) / M; int base = lblock * M; for (int j = lblock; j <= rblock; j++) { for (iter it = block[j].begin(); it != block[j].end(); it++) { cnt[*it + j * M - base] = 1; } } for (iter it = block[i].begin(); it != block[i].end(); it++) { if (cnt[m - i * M - *it - base]) { ans = 1; break; } } for (int j = lblock; j <= rblock; j++) { for (iter it = block[j].begin(); it != block[j].end(); it++) { cnt[*it + j * M - base] = 0; } } if (ans) break; } cout << ans << endl; } return 0; }
T3 期望得分：40；实际得分：40；
思路：杨辉三角的奇偶分布是一个经典的分形图形。 由此可以观察出的规律有：杨辉三角的前 2n 行的奇数个数是 3n 个，如果找到一个 k，使 2k <= n < 2k-1, 那么前 2k 行的奇数个数可以单独计算； 而余下部分两边对称， 所以可以递归算其中的一边， 再乘以 2 加入答案。
上述算法计算出的是杨辉三角前 n 行有多少个奇数， 作差即可得到偶数的个数。
对于最后一个测试点， 需要使用高精度来支持上述做法。
#include<algorithm> #include<cstdio> using namespace std; int n, sum; int a[1000][1000]; int main() { //freopen("count.in","r",stdin); //freopen("count.out","w",stdout); scanf("%d", &n); a[0][0] = 1; for(int i = 0; i < n; i++) for(int j = 0; j < i+1; j++) { if(i == 0) a[i][j] = 1; else a[i][j] = a[i-1][j-1]+a[i-1][j]; if(a[i][j]%2 == 0) sum++; } printf("%d", sum); //fclose(stdin); fclose(stdout); return 0; }
#include<iostream> using namespace std; long long n; long long work(long long n) { if(n==0 || n==1 )return 0; if(n&1)return 2*work(n/2)+work(n/2+1)+(n/2)*(n/2+1)/2; else return 3*work(n/2)+(n/2)*(n/2-1)/2; } int main() { //freopen("count.in","r",stdin); //freopen("count.out","w",stdout); cin>>n; cout<<work(n); //fclose(stdin);fclose(stdout); return 0; }
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> #include<string> using namespace std; const int N = 201; struct bignum { int a[N]; int n; bignum() { n = 0; memset(a, 0, sizeof(a)); } bignum(string s) { memset(a, 0, sizeof(a)); n = s.size(); for (int i = 0; i < n; i++) a[i] = s[n - 1 - i] -‘0‘; } bignum(int x) { memset(a, 0, sizeof(a)); n = 0; while (x) { a[n] = x % 10; x /= 10; n++; } } void deal() { for (int i = 0; i < n; i++) { if (a[i] < 0) { int tmp = (-a[i] - 1) / 10 + 1; a[i] += 10 * tmp; a[i + 1] -= tmp; } if (a[i] >= 10) { int tmp = a[i] / 10; a[i] -= 10 * tmp; a[i + 1] += tmp; if (i == n - 1 && a[i + 1] > 0) n++; } } while (n > 0 && a[n - 1] == 0) n--; } void div2() { int tmp = 0; for (int i = n - 1; i >= 0; i--) { int tmp_ = a[i] & 1; a[i] = (a[i] + tmp * 10) >> 1; tmp = tmp_; } deal(); } void print() { for (int i = n - 1; i >= 0; i--) cout << a[i]; cout << endl; } }; bignum operator + (const bignum &a, const bignum &b) { bignum c; c.n = max(a.n, b.n); for (int i = 0; i < c.n; i++) c.a[i] = a.a[i] + b.a[i]; c.deal(); return c; } bignum operator - (const bignum &a, const bignum &b) { bignum c; c.n = max(a.n, b.n); for (int i = 0; i < c.n; i++) c.a[i] = a.a[i] - b.a[i]; c.deal(); return c; } bignum operator * (const bignum &a, const bignum &b) { bignum c; c.n = a.n + b.n - 1; for (int i = 0; i < a.n; i++) for (int j = 0; j < b.n; j++) c.a[i + j] += a.a[i] * b.a[j]; c.deal(); return c; } bool no_bigger_than(const bignum &a, const bignum &b) { if (a.n < b.n) return 1; if (b.n < a.n) return 0; for (int i = a.n - 1; i >= 0; i--) { if (a.a[i] > b.a[i]) return 0; if (a.a[i] < b.a[i]) return 1; } return 1; } bignum calc(bignum n) { if (n.n == 0) return 0; bignum ret(1); bignum now(1); bignum big2(2); bignum big3(3); while (no_bigger_than(now * big2, n)) { now = now * big2; ret = ret * big3; } /* cout << "*****" << endl; n.print(); now.print(); ret.print(); cout << "*****" << endl; */ return ret + big2 * calc(n - now); } int main() { freopen("count.in","r",stdin); freopen("count.out","w",stdout); string s; cin >> s; bignum a(s); bignum n(s); bignum b(1); //b.print(); bignum c = a + b; //a.print(); //c.print(); //return 0; a = a * c; //a.print(); a.div2(); //a.print(); (a - calc(n)).print(); return 0; }
附加题：HDU 矩形面积并
原文：https://www.cnblogs.com/v-vip/p/8971880.html
