历年noip普及组c++完善程序题总结归纳.docx

历年noip普及组c++完善程序题总结归纳.docx

《历年noip普及组c++完善程序题总结归纳.docx》由会员分享，可在线阅读，更多相关《历年noip普及组c++完善程序题总结归纳.docx（26页珍藏版）》请在冰点文库上搜索。

历年noip普及组c++完善程序题总结归纳

完善程序题总结归纳

By：

七（6）yx

一、【题目】（哥德巴赫猜想）哥德巴赫猜想是指，任一大于2的偶数都可写成两个质数之和。

迄今为止，这仍然是一个著名的世界难题，被誉为数学王冠上的明珠。

试编写程序，验证任一大于2且不超过n的偶数都能写成两个质数之和。

#include

usingnamespacestd;

intmain（）

{

constintSIZE=1000;

intn,r,p[SIZE],i,j,k,ans;

booltmp;

cin>>n;

r=1;

p[1]=2;

for（i=3;i<=n;i++）

{

①;

for（j=1;j<=r;j++）

if（i%②==0）

{

tmp=false;

break;

}

if（tmp）

{

r++;

③;

}

}

ans=0;

for（i=2;i<=n/2;i++）

{

tmp=false;

for（j=1;j<=r;j++）

for（k=j;k<=r;k++）

if（i+i==④）

{

tmp=true;

break;

}

if（tmp）

ans++;

}

cout<

return0;

}

若输入n为2010，则输出⑤时表示验证成功，即大于2且不超过2010的偶数都满足哥德巴赫猜想。

【算法】先for一遍，找出质数，然后对每一个偶数进行一一匹配（2除外），效率O（n^3）

【代码】

1、tmp=1；2、p[j];3、p[r]=j;4、p[j]+p[k]5、1004

【年份】2010年

二、【题目】（过河问题）在一个月黑风高的夜晚,有一群人在河的右岸,想通过唯一的一根独木桥走到河的左岸.在伸手不见五指的黑夜里,过桥时必须借照灯光来照明,不幸的是,他们只有一盏灯.另外,独木桥上最多能承受两个人同时经过,否则将会坍塌.每个人单独过独木桥都需要一定的时间,不同的人要的时间可能不同.两个人一起过独木桥时,由于只有一盏灯,所以需要的时间是较慢的那个人单独过桥所花费的时间.现在输入N（2<=N<1000）和这N个人单独过桥需要的时间,请计算总共最少需要多少时间,他们才能全部到达河左岸.

  例如,有3个人甲、乙、丙,他们单独过桥的时间分别为1、2、4,则总共最少需要的时间为7.具体方法是:

甲、乙一起过桥到河的左岸,甲单独回到河的右岸将灯带回,然后甲、丙在一起过桥到河的左岸,总时间为2+1+4=7.

#include

#include

usingnamespacestd;

constintsize=100;

constintinfinity=10000;

constboolleft=1;

constboolright=0;

constboolleft_to_right=1;

constboolright_to_left=0;

intn,hour[size];

boolpos[size];

intmax（inta,intb）{returna>b?

a:

b;}

intgo（boolstage）

{

inti,j,num,tmp,ans;

if（stage==right_to_left）

{

num=0;

ans=0;

for（i=1;i<=n;i++）

if（pos[i]==right）

{

num++;

if（hour[i]>ans）

ans=hour[i];

}

if（①）

returnans;

ans=infinity;

for（i=1;i<=n-1;i++）

if（pos[i]==right）

for（j=i+1;j<=n;j++）

if（pos[j]==right）

{

pos[i]=left;

pos[j]=left;

tmp=max（hour[i],hour[j]）+②;

if（tmp

ans=tmp;

pos[i]=right;

pos[j]=right;

}

returnans;

}

if（stage==left_to_right）

{

ans=infinity;

for（i=1;i<=n;i++）

if（③）

{

pos[i]=right;

tmp=④;

if（tmp

ans=tmp;

⑤;

}

returnans;

}

return0;

}

intmain（）

{

inti;

cin>>n;

for（i=1;i<=n;i++）

{

cin>>hour[i];

pos[i]=right;

}

cout<

return0;

}

【算法】

利用深搜，左右交替寻找最优解（maybe是动态规划）

【代码】1、num<=2;2、go[1];3、pos[j]==1;

4、hour[i]+go[0];5、pos[i]=1;

【年份】2010年

三、【题目】

（子矩阵）给输入一个n1*m1的矩阵a，和n2*m2的矩阵b，问a中是否存在子矩阵和b相等。

若存在，输出所有子矩阵左上角的坐标：

若不存在输出“Thereisnoanswer”。

#include

usingnamespacestd;

constintSIZE=50;

intn1,m1,n2,m2,a[SIZE][SIZE],b[SIZE][SIZE];

intmain（）

{

inti,j,k1,k2;

boolgood,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++）

①;

haveAns=false;

for（i=1;i<=n1-n2+1;i++）

for（j=1;j<=②;j++）

{

③;

for（k1=1;k1<=n2;k1++）

for（k2=1;k2<=④;k2++）{

if（a[i+k1-1][j+k2-1]!

=b[k1][k2]）

good=false;

}

if（good）{

cout<

⑤;

}

}

if（!

haveAns）

cout<<"Thereisnoanswer"<

return0;

}

【算法】

枚举每一条对角线，进行判断。

【代码】

1、cin>>b[i][j];2、m1-m2+1；3、good=1;4、m2;5、haveAns=1;

【年份】2011年

四、【题目】

（大整数开方）输入一个正整数n（1≤n≤10100），试用二分法计算它的平方根的整数部分。

#include

#include

usingnamespacestd;

constintSIZE=200;

structhugeint{

intlen,num[SIZE];

};

//其中len表示大整数的位数；num[1]表示个位，num[2]表示十位，以此类推

hugeinttimes（hugeinta,hugeintb）

//计算大整数a和b的乘积

{

inti,j;

hugeintans;

memset（ans.num,0,sizeof（ans.num））;

for（i=1;i<=a.len;i++）

for（j=1;j<=b.len;j++）

①+=a.num[i]*b.num[j];

for（i=1;i<=a.len+b.len;i++）{

ans.num[i+1]+=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;

returnans;

}

hugeintadd（hugeinta,hugeintb）

//计算大整数a和b的和

{

inti;

hugeintans;

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]+=③;

ans.num[i+1]+=ans.num[i]/10;

ans.num[i]%=10;

}

if（ans.num[ans.len+1]>0）

ans.len++;

returnans;

}

hugeintaverage（hugeinta,hugeintb）

//计算大整数a和b的平均数的整数部分

{

inti;

hugeintans;

ans=add（a,b）;

for（i=ans.len;i>=2;i--）{

ans.num[i-1]+=（④）*10;

ans.num[i]/=2;

}

ans.num[1]/=2;

if（ans.num[ans.len]==0）

ans.len--;

returnans;

}

hugeintplustwo（hugeinta）

//计算大整数a加2之后的结果

{

inti;

hugeintans;

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）

⑤;

returnans;

}

boolover（hugeinta,hugeintb）

//若大整数a>b则返回true，否则返回false

{

inti;

if（⑥）

returnfalse;

if（a.len>b.len）

returntrue;

for（i=a.len;i>=1;i--）{

if（a.num[i]

returnfalse;

if（a.num[i]>b.num[i]）

returntrue;

}

returnfalse;

}

intmain（）

{

strings;

inti;

hugeinttarget,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]-⑦;

memset（left.num,0,sizeof（left.num））;

left.len=1;

left.num[1]=1;

right=target;

do{

middle=average（left,right）;

if（over（⑧））

right=middle;

else

left=middle;

}while（!

over（plustwo（left）,right））;

for（i=left.len;i>=1;i--）

cout<

return0;

}

【算法】每二分一次，就判断一下答案在哪个区间，然后在那个区间继续二分，避免不必要的计算。

【代码】1、ans.num[i+j-1]

2、ans.num[i]%=10

3、a.num[i]+b.num[i]

4、ans.num[i]%2

5、ans.len++

6、a.len

7、'0'

8、times（middle,middle）,target

【年份】2011年

五、【题目】（坐标统计）输入n个整点在平面上的坐标。

对于每个点，可以控制所有位于它左下方的点（即x、y坐标都比它小），它可以控制的点的数目称为“战斗力”。

依次输出每个点的战斗力，最后输出战斗力最高的点的编号（如果若干个点的战斗力并列最高，输出其中最大的编号）。

#include

usingnamespacestd;

constintSIZE=100;

intx[SIZE],y[SIZE],f[SIZE];

intn,i,j,max_f,ans;

intmain（）

{

cin>>n;

for（i=1;i<=n;i++）cin>>x[i]>>y[i];

max_f=0;

for（i=1;i<=n;i++）

{

f[i]=①;

for（j=1;j<=n;j++）

{

if（x[j]

③;

}

if（④）

{

max_f=f[i];

⑤;

}

}

for（i=1;i<=n;i++）cout<

cout<

return0;

}

【算法】依次进行战斗力的计算，找出最大的一个

【代码】

1、0

2、y[j]

3、f[i]++;

4、（i>1）&&（f[i]>f[i-1]）（我写的是f[i]>max_f）

5、ans=max_f（我写的是ans=i）

其实我做的是对的，正确答案有bug；

【年份】2012年

六、【题目】（排列数）输入两个正整数n，m（1

例如：

输入：

32

输出：

12

13

21

23

31

32

#include

#include

usingnamespacestd;

constintSIZE=25;

boolused[SIZE];

intdata[SIZE];

intn,m,i,j,k;

boolflag;

intmain（）

{

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<

cout<

flag=①;

for（i=m;i>=1;i--）

{

②;

for（j=data[i]+1;j<=n;j++）

if（!

used[j]）

{

used[j]=true;

data[i]=③;

flag=true;

break;

}

if（flag）

{

for（k=i+1;k<=m;k++）

for（j=1;j<=④;j++）

if（!

used[j]）

{

data[k]=j;

used[j]=true;

break;

}

⑤;

}

}

}

return0;

}

【算法】直接进行枚举，一个个进行选择

【代码】1、0

2、used[data[i]]=0

3、j

4、n

5、break

【年份】2012年

七、【题目】

（二叉查找树）二叉查找树具有如下性质：

每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。

试判断一棵树是否为二叉查找树。

输入的第一行包含一个整数n，表示这棵树有n个顶点，编号分别为1,2,…,n，其中编号为1的为根结点。

之后的第i行有三个数value,left_child,right_child，分别表示该节点关键字的值、左子节点的编号、右子节点的编号；如果不存在左子节点或右子节点，则用0代替。

输出1表示这棵树是二叉查找树，输出0则表示不是。

#include

usingnamespacestd;

constintSIZE=100;

constintINFINITE=1000000;

structnode{

intleft_child,right_child,value;

};

nodea[SIZE];

intis_bst（introot,intlower_bound,intupper_bound）

{

intcur;

if（root==0）

return1;

cur=a[root].value;

if（（cur>lower_bound）&&（

（1））&&//（3分）

（is_bst（a[root].left_child,lower_bound,cur）==1）&&

（is_bst（

（2）,（3）,（4））==1））

//（3分，3分，3分）

return1;

return0;

}

intmain（）

{

inti,n;

cin>>n;

for（i=1;i<=n;i++）

cin>>a[i].value>>a[i].left_child>>a[i].right_child;

cout<

return0;

}

【算法】就是遍历一遍。

【代码】1、j-i；2、cur1；3、count1--;4、count2--;5、cur1=a[j]；

【年份】2013年

八、【题目】

（数字删除）下面程序的功能是将字符串中的数字字符删除后输出。

请填空。

（每空3分，共12分）

#include

usingnamespacestd;

intdelnum（char*s）

{

inti,j;

j=0;

for（i=0;s[i]!

='\0';i++）

if（s[i]<'0'——————1——————s[i]>'9'）

{

s[j]=s[i];

——————2——————;

}

return——————3——————;

}

constintSIZE=30;

intmain（）

{

chars[SIZE];

intlen,i;

cin.getline（s,sizeof（s））;

len=delnum（s）;

for（i=0;i

cout<<——————4——————）;

cout<

return0;

}

【算法】搜索一遍，把非字母的字符保留。

【代码】

1、||2、j++；3、j4、s[i]

【年份】2014年

九、【题目】

（最大子矩阵和）给出m行n列的整数矩阵，求最大的子矩阵和（子矩阵不能为空）。

输入第一行包含两个整数m和n，即矩阵的行数和列数。

之后m行，每行n个整数，描述整个矩阵。

程序最终输出最大的子矩阵和。

（最后一空4分，其余3分，共16分）

比如在如下这个矩阵中：

44

0-2-70

92-62

-41-41

-180-2

拥有最大和的子矩阵为：

92

-41

-18

其和为15

33

-21020

-1100-2

0-2-3

最大子矩阵和为128

44

0-2-9-9

-91157

-4-3-7-6

-1775

最大子矩阵和为26

#include

usingnamespacestd;

constintSIZE=100;

intmatrix[SIZE+1][SIZE+1];

introwsum[SIZE+1][SIZE+1];//rowsum[i][j]记录第i行前j个数的和

intm,n,i,j,first,last,area,ans;

intmain（）

{

cin>>m>>n;

for（i=1;i<=m;i++）

for（j=1;j<=n;j++）

cin>>matrix[i][j];

ans=matrix————1——————;

for（i=1;i<=m;i++）

——————2——————;

for（i=1;i<=m;i++）

for（j=1;j<=n;j++）

rowsum[i][j]=——————3——————;

for（first=1;first<=n;first++）

for（last=first;last<=n;last++）

{

——————4——————;

for（i=1;i<=m;i++）

{

area+=——————5——————;

if（area>ans）

ans=area;

if（area<0）

area=0;

}

}

cout<

return0;

}

【算法】三个for，枚举子矩阵左上，右上和高。

遇到目前最大值就记录下来。

【代码】1、[1][1]（其实可以随便填，比如【2】【3】、【3】【4】、【4】【6】都可以）

2、rowsum[i][0]=0；

3、rowsum[i][j-1]+matrix[i][j]；4、area=0；

5、rowsum[i][last]-rowsum[i][first