NOIP普及组初赛历年试题及答案完善题篇.pdf
文本预览下载声明
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)
计
显示全部