|
完善程序，每年两题，每题每空2-4分，共28分。 【解题步骤】 1、仔细读题，尤其是题目给你的解题思路：解决什么问题？用的什么算法？输入输出是什么？…… 2、要知道变量的含义，也可通过变量单词的意思知道，比如sum表示和，que表示队列等等。 3、在充分了解前两点的基础上，先根据自己的想法大致想想：如果让你实现程序，你会怎么做。 4、通读程序，理顺程序结构，千万不要因为程序很长而觉得气馁，有时程序越长，填空越简单。 5、按照程序执行的顺序做，遇到难的先放一边，继续往下做。有些空格很简单，一下就能看出来的。 6、到这步为止，程序大概意图就知道了，然后就是填比较难的几格了。这一点就靠你对程序的理解了。 7、填完了以后，再执行一遍程序，有样例就结合样例，没样例就自己造数据模拟。 【解题技巧】 1、变量初始化：这个得结合后面的运算确定，不过有些也很简单，如sum=0之类的。 2、for循环初、终值：如果是嵌套的循环，可结合父循环或子循环确定。 3、更新最优解：比较或赋值。 4、要填的空格与某句对应，这样的例子在下面能找到很多。 NOIP2011-1.子矩阵 给输入一个n1*m1 的矩阵a，和n2*m2的矩阵b ，问a 中是否存在子矩阵和b 相等。若存在，输出所有子矩阵左上角的坐标:若不存在输出“There isno answer ”。 #include<iostream> using namespace std; const int SIZE = 50; int n1,m1,n2,m2,a[SIZE][SIZE],b[SIZE][SIZE]; int main() { int i,j,k1,k2; bool good ,haveAns; cin>>n1>>m1; for(i=1;i<=n1;i++) for(j=1;j<=m1;j++) cin>>a[i][j]; cin>>n2>>m2; for(i=1;i<=n2;i++) for(j=1;j<=m2;j++) cin>>b[i][j]; haveAns=false; for(i=1;i<=n1-n2+1;i++) for(j=1;j<=m1-m2+1;j++){ good=true; for(k1=1;k1<=n2;k1++) for(k2=1;k2<=m2;k2++){ if(a[i+k1-1][j+k2-1]!=b[k1][k2]) good=false; } if(good){ cout<<i<<''<<j<<endl; haveAns=true; } } if(!haveAns) cout<<"Thereis no answer"<<endl; return 0; } NOIP2011-2. 大整数开方 输入一个正整数n ( 1 ≤n≤10^100)，试用二分法计算它的平方根的整数部分。 #include<iostream> #include<string> using namespace std; const int SIZE=200; struct hugeint{ int len,num[SIZE]; }; // 其中len 表示大整数的位数; num[1] 表示个位，num[2] 表示十位，以此类推 hugeint times(hugeint a,hugeint b) // 计算大整数a和b的乘积 { int i,j; hugeint ans; memset(ans.num,0,sizeof(ans.num)); for(i=1;i<=a.len;i++) for(j=1;j<=b.len;j++) ans.num[i+j-1]+=a.num[i]*b.num[j]; for(i=1;i<=a.len+b.len;i++){ ans.num[i+1]+=ans.num[i]/10; ans.num[i]%=10; } if(ans.num[a.len+b.len]>0) ans.len=a.len+b.len; else ans.len=a.len+b.len-1; return ans; } hugeint add(hugeint a,hugeint b) // 计算大整数a和b 的和 { int i;hugeint ans; memset(ans.num,0,sizeof(ans.num)); if(a.len>b.len) ans.len=a.len; else ans.len=b.len; for(i=1;i<=ans.len;i++){ ans.num[i]+=a.num[i]+b.num[i]; ans.num[i+1]+=ans.num[i]/10; ans.num[i]%=10; } if(ans.num[ans.len+1]>0) ans.len++; return ans; } hugeint average(hugeint a,hugeint b) // 计算大整数a 和b 的平均数的整数部分 { int i; hugeint ans; ans=add(a,b); for(i=ans.len;i>=2;i--){ ans.num[i-1]+=(ans.num[i] % 2)*10; ans.num[i]/=2; } ans.num[1]/=2; if(ans.num[ans.len]==0) ans.len--; return ans; } hugeint plustwo(hugeint a) //计算大整数a 加2 之后的结果 { int i; hugeint ans; ans=a; ans.num[1]+=2; i=1; while((i<=ans.len)&&(ans.num[i]>=10) ){ ans.num[i+1]+=ans.num[i]/10; ans.num[i]%=10; i++; } if(ans.num[ans.len+1]>0) ans.len++; return ans; } bool over(hugeint a,hugeint b) // 若大整数a>b 则返回true ，否则返回false { int i; if(a.len<b.len) return false; if( a.len>b.len ) return true; for(i=a.len;i>=1;i--){ if(a.num[i]<b.num[i]) return false; if(a.num[i]>b.num[i]) return true; } return false; } int main() { string s; int i; hugeint target,left,middle,right; cin>>s; memset(target.num,0,sizeof(target.num)); target.len=s.length(); for(i=1;i<=target.len;i++) target.num[i]=s[target.len-i]- '0'; memset(left.num,0,sizeof(left.num)); left.len=1; left.num[1]=1; right=target; do{ middle=average(left,right); if(over(times(middle,middle),target)) right=middle; else left=middle; }while(!over(plustwo(left),right) ); for(i=left.len;i>=1;i--) cout<<left.num[i]; return 0; } NOIP2012-1. 坐标统计 输入 n 个整点在平面上的坐标。对于每个点，可以控制所有位于它左下方的点(即 x、y 坐标都比它小)，它可以控制的点的数目称为“战斗力”。依次输出每个点的战斗力，最后输出战斗力最高的点的编号 (如果两个点战斗力一样，输出较大的编号)。 #include<iostream> using namespace std; const int SIZE = 100; int x[SIZE], y[SIZE], f[SIZE]; int n, i, j, max_f, ans; int main() { cin>>n; for (i = 1; i <= n; i++) cin>>x[i]>>y[i]; max_f = 0; for (i = 1; i <= n; i++) { f[i] = 0; for (j = 1; j <= n; j++) { if (x[j] <x[i] &&y[j] < y[i]; f[i]++; } if(f[i] >= max_f) { max_f = f[i]; ans = i; } } for (i = 1; i <= n; i++) cout<<f[i]<<endl; cout<<ans<<endl; return o; } NOIP2012-2. 排列数 输入两个正整数 n, m (1 ≤n ≤20, 1 ≤m ≤n)，在 1~n 中任取 m 个数，按字典序从小到大输出所有这样的排列。例如 输入: 3 2 输出: 1 2 1 3 2 1 2 3 3 1 3 2 #include<iostream> #include<cstring> using namespace std; const int SIZE = 25; bool used[SIZE]; int data[SIZE]; int n, m, i, j, k; bool flag; int main() { cin>>n>>m; memset(used, false, sizeof(used)); for (i = 1; i <= m; i++) { data[i] = i; used[i] =true; } flag = true; while (flag) { for (i = 1; i<= m-1; i++) cout<<data[i]<<" "; cout<<data[m]<<endl; flag =false; for (i = m; i>= 1; i--) { used[data[i]] = false; for (j =data[i]+1; j <= n; j++) if (!used[j]) { used[j] =true; data[i] = j; flag = true; break; } if (flag) { for (k = i+1;k <= m; k++) for (j = 1; j<=n; j++) if (!used[j]) { data[k] = j; used[j] =true; break; } break; } } } } NOIP2013-1. 序列重排 全局数组变量 a 定义如下: const int SIZE = 100; int a[SIZE], n; 它记录着一个长度为 n 的序列 a[1], a[2], ..., a[n]。 现在需要一个函数，以整数 p (1 ≤ p≤ n)为参数，实现如下功能:将序列 a 的前 p 个数与后 n – p个数对调，且不改变这 p 个数(或n – p 个数)之间的相对位置。例如，长度为5 的序列1, 2, 3, 4, 5，当 p = 2 时重排结果为3, 4, 5, 1, 2。 有一种朴素的算法可以实现这一需求，其时间复杂度为O(n)、空间复杂度为O(n): void swap1(int p) { int i, j, b[SIZE]; for (i = 1; i <= p; i++) b[n–p+i] = a[i]; for (i = p + 1; i <= n; i++) b[i-p]= a[i]; for(i=1;i<= n;i++) a[i] = b[i]; } 我们也可以用时间换空间，使用时间复杂度为O(n2)、空间复杂度为O(1)的算法: void swap2(int p) { int i, j, temp; for (i = p + 1; i <= n; i++) { temp = a[i]; for(j=i;j>= i–p+1;j--) a[j] = a[j - 1]; a[i – p]= temp; } } NOIP2013-2. 二叉查找树 二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。试判断一棵树是否为二叉查找树。 输入的第一行包含一个整数 n，表示这棵树有 n 个顶点，编号分别为1, 2, ..., n，其中编号为1 的为根结点。之后的第 i 行有三个数 value, left_child, right_child，分别表示该节点关键字的值、左子节点的编号、右子节点的编号；如果不存在左子节点或右子节点，则用0 代替。输出1 表示这棵树是二叉查找树，输出0 则表示不是。 #include <iostream> using namespace std; const int SIZE = 100; const int INFINITE = 1000000; struct node { int left_child, right_child, value; }; node a[SIZE]; int is_bst(int root, int lower_bound, int upper_bound) { int cur; if (root == 0) return 1; cur = a[root].value; if ((cur > lower_bound) && (cur < upper_bound) && (is_bst(a[root].left_child, lower_bound, cur)== 1) && (is_bst(a[root].right_child, cur, upper_bound)== 1)) return 1; return 0; } int main() { int i, n; cin>>n; for (i = 1; i <= n; i++) cin>>a[i].value>>a[i].left_child>>a[i].right_child; cout<<is_bst( 1,-INFINITE, INFINITE)<<endl; return 0; } NOIP2014-1. 数字删除 下面程序的功能是将字符串中的数字字符删除后输出。请填空。 #include <iostream> using namespace std; int delnum(char *s) { int i, j; j = 0; for (i = 0; s[i] != '\0'; i++) if (s[i] < '0' || s[i] > '9') { s[j] = s[i]; j++; } return j; } const int SIZE = 30; int main() { char s[SIZE]; int len, i; cin.getline(s, sizeof(s)); len = delnum(s); for (i = 0; i < len; i++) cout<< s[i]; cout << endl; return 0; } NOIP2014-2. 最大子矩阵和 给出m 行n 列的整数矩阵，求最大的子矩阵和(子矩阵不能为空)。 输入第一行包含两个整数m 和n，即矩阵的行数和列数。之后m 行，每行n 个整数，描述整个矩阵。程序最终输出最大的子矩阵和。 #include <iostream> using namespace std; const int SIZE = 100; int matrix[SIZE + 1][SIZE + 1]; int rowsum[SIZE + 1][SIZE + 1]; //rowsum[i][j]记录第 i 行前 j 个数的和 int m, n, i, j, first, last, area, ans; int main() { cin >> m >> n; for (i = 1; i <= m; i++) for (j = 1; j<= n; j++) cin >>matrix[i][j]; ans = matrix[1][1]; for (i = 1; i <= m; i++) rowsum[i][0]=0; for (i = 1; i <= m; i++) for (j = 1; j<= n; j++) rowsum[i][j] = rowsum[i][j-1]+matrix[i][j]; for (first = 1; first <= n; first++) for (last = first;last <= n; last++) { area=0; for (i = 1; i<= m; i++) { area+=rowsum[i][last]-rowsum[i][first-1]; if (area > ans) ans = area; if (area < 0) area = 0; } } cout << ans << endl; return 0; } NOIP2015-1. 打印月历 输入月份m(1≤m≤12)，按一定格式打印 2015 年第 m 月的月历。例如，2015年 1 月的月历打印效果如下(第一列为周日)： #include<iostream> #include<string> usingnamespace std; const intdayNum[ ] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; int m,offset, i; int main() { cin>> m; cout<< "S\tM\tT\tW\tT\tF\tS" << endl; //'\t'为TAB制表符 offset=4; for(i= 1; i < m; i++) offset =(offset+dayNum[i])%7; for(i= 0; i < offset; i++) cout << '\t'; for(i=1;i<=dayNum[m];i++) { cout<< i; if(i == dayNum[m] || (offset+i)%7==0) cout << endl; else cout << '\t'; } return 0; } NOIP2015-2.中位数 median 给定n(n 为奇数且小于 1000)个整数，整数的范围在 0~m(0<m<2^31)之间，请使用二分法求这 n 个整数的中位数。所谓中位数，是指将这n 个数排序之后，排在正中间的数。 #include<iostream> usingnamespace std; const intMAXN = 1000; int n, i,lbound, rbound, mid, m, count; int x[MAXN]; int main() { cin>> n >> m; for(i= 0; i < n; i++) cin >> x[i]; lbound= 0; rbound= m; while(lbound<rbound) { mid = (lbound + rbound) / 2; count=0; for(i = 0; i < n; i++) if(x[i]>mid) count++; if(count > n / 2) lbound = mid + 1; else rbound=mid; cout << mid << " "<< lbound << " " << rbound << " "<< count << endl; } cout<< rbound << endl; return 0; } NOIP2016-1. 读入整数 请完善下面的程序，使得程序能够读入两个int 范围内的整数，并将这两个整数分别输出，每行一个。输入的整数之间和前后只会出现空格或者回车。输入数据保证合法。 例如: 输入: 123 -789 输出: 123 -789 #include<iostream> using namespacestd; int readint() { int num = 0; // 存储读取到的整数 int negative = 0; // 负数标识 charc; // 存储当前读取到的字符 c =cin.get(); while((c < '0' || c > '9') && c != '-') c = cin.get() ; if (c== '-') negative = 1; else num=c-'0'; c =cin.get(); while(c>='0'&&c<='9') { num=num*10+c-'0'; c = cin.get(); } if(negative == 1) return -num ; return num; } int main() { int a,b; a =readint(); b =readint(); cout<< a << endl << b << endl; return 0; } NOIP2016-2. 郊游活动 有n 名同学参加学校组织的郊游活动，已知学校给这n 名同学的郊游总经费为A 元，与此同时第i 位同学自己携带了Mi 元。为了方便郊游，活动地点提供B(≥n)辆自行车供人租用，租用第j 辆自行车的价格为Cj 元，每位同学可以使用自己携带的钱或者学校的郊游经费，为了方便账务管理，每位同学只能为自己租用自行车，且不会借钱给他人，他们想知道最多有多少位同学能够租用到自行车。 本题采用二分法。对于区间[l, r]，我们取中间点mid 并判断租用到自行车的人数能否达到mid。判断的过程是利用贪心算法实现的。 #include<iostream> using namespacestd; #define MAXN1000000 int n, B, A,M[MAXN], C[MAXN], l, r, ans, mid; bool check(int nn){ intcount = 0, i, j; i = n-nn+1 ; j = 1; while(i <= n) { if (M[i]<=C[j]) count += C[j] - M[i]; i++; j++; } return count<=A ; } void sort(int a[],int l, int r) { int i= l, j = r, x = a[(l + r) / 2], y; while(i <= j) { while (a[i] < x) i++; while (a[j] > x) j--; if (i <= j) { y = a[i]; a[i] = a[j]; a[j] = y; i++; j--; } } if (i< r) sort(a, i, r); if (l< j) sort(a, l, j); } int main() { int i; cin>> n >> B >> A; for (i= 1; i <= n; i++) cin >> M[i]; for (i= 1; i <= B; i++) cin >> C[i]; sort(M,1, n); sort(C,1, B); l = 0; r = n; while(l <= r) { mid = (l + r) / 2; if (check(mid) ) { ans = mid; l = mid + 1; } else r = mid-1 ; } cout<< ans << endl; return 0; } |
|
|
