NOIP普及组初赛历年试题及答案完善题篇.pdfVIP

NOIP 普及组初赛历年试题及答案（完善题篇） 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”。 #includeiostream 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; cinn1m1; for(i 1;i n1;i++) for(j 1;j m1;j ++) cina[i][j]; cinn2m2; for(i 1;i n2;i++) for(j 1;j m2;j ++) cinb[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){ coutij endl; haveAns true; } } if(!haveAns) coutThereis no answerendl; return 0; } NOIP2011-2. 大整数开方 输入一个正整数n ( 1≤n≤10^100)，试用二分法计算它的平方根的整数部分。 #includeiostream #includestring 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) 计