历年noip普及组完善程序题总结归纳Word下载.docx

历年noip普及组完善程序题总结归纳Word下载.docx

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

偶数都满足哥德巴赫猜想。

【算法】先for一遍，找出质数，然后对每一个偶数进行一

一匹配（2除外），效率0（23）

【代码】

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.

cstring>

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;

for（i=1;

if（pos[i]==right）

num++;

if（hour[i]>

ans）

ans=hour[i];

if（①）

returnans;

ans=infinity;

=n_1;

for（j=i+1;

if（pos[j]==right）

pos[i]=left;

pos[j]=left;

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

if（tmp<

ans）ans=tmp;

pos[i]=right;

pos[j]=right;

if（stage==left_to_right）

if（③）

tmp=④;

ans=tmp;

⑤;

inti;

cin>

>

hour[i];

go[right_to_left）<

【算法】

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

【代码】1、num<

=2;

2、go[1];

3、pos[j]==1;

4、hour[i]+go[0];

5、pos[i]=1;

三、【题目】

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

Thereisnoanswer

相等。

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

若不存在输出

usingnamespacestd;

constintSIZE=50;

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

inti,j,k1,k2;

boolgood,haveAns;

n1>

>

m1;

=n1;

=m1;

cin>

a[i][j];

n2>

m2;

=n2;

=m2;

haveAns=false;

=n1-n2+1;

=②;

③;

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）{

'

'

if（!

haveAns）

"

Thereisnoanswer"

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

1、cin>

b[i][j];

2、m1-m2+1;

3、good=1;

4、m2;

5、haveAns=1;

【年份】2011年

四、【题目】

（大整数开方）输入一个正整数n（1<

nw100）,试用二分法计算它的平方根的整数部分。

string>

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））;

=a」en;

=b」en;

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

=a.len+b.len;

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

②;

if（ans.num[a」en+b.len]>

0）ans.len=a.len+b.len;

else

ans.len=a.len+b.len-1;

hugeintadd（hugeinta,hugeintb）

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

if（a.len>

b.len）

ans.len=a.len;

ans.len=b.len;

=ans」en;

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++;

hugeintaverage（hugeinta,hugeintb）

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

ans=add（a,b）;

for（i=ans」en;

i>

i__）{

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

ans.num[i]/=2;

ans.num[1]/=2;

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

ans.len--;

hugeintplustwo（hugeinta）

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

ans=a;

ans.num[1]+=2;

i=1;

while（（i<

=ans.len）&

&

（ans.num[i]>

=10））{

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

i++；

⑤；

boolover（hugeinta,hugeintb）

//若大整数a>

b则返回true，否则返回false{

if（⑥）

returnfalse;

if（a.len>

b.len）

returntrue;

for（i=a.len;

i>

=1;

if（a.num[i]<

b.num[i]）

if（a.num[i]>

strings;

hugeinttarget,left,middle,right;

s;

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

target.len=s.length（）;

=target.len;

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;

left=middle;

}while（!

over（plustwo（left）,right））;

for（i=left.len;

i--）

left.num[i];

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

【代码】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<

b.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（）

i++）cin>

x[i]»

y[i];

max_f=O;

f[i]=①；

if（x[j]<

x[i]&

②）

③；

if（④）

max_f=f[i];

⑤；

i++）cout<

f[i]<

cout<

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

1、02、y[j]<

y[i]3、f[i]++;

f[i]>

max_f）

4、（i>

1）&

（f[i]>

f[i-1]）（我写的是

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

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

【年份】2012年

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

*20,1<

m<

n），在1~n中任取m个

数，按字典序从小到大输出所有这样的排列。

例如:

输入：

32

输出：

12

23

31

#inelude<

usingnamespaeestd;

constintSIZE=25;

boolused[SIZE];

intdata[SIZE];

intn,m,i,j,k;

boolflag;

n»

m;

memset（used,false,sizeof（used））;

for（i=1;

=m;

data[i]=i;

used[i]=true;

flag=true;

while（flag）

=m-1;

data[i]<

;

data[m]<

flag=①；

for（i=m;

②；

for（j=data[i]+1;

j++）if（!

used[j]）

used[j]=true;

data[i]=③；

if（flag）

for（k=i+1;

k++）for（j=1;

=④；

data[k]=j;

break;

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

【代码】1、0

2、used[data[i]]=0

3、j

4、n

5、break

七、【题目】

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

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

小于其右子树上所有节点的值。

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

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

的为根结点。

之后的第i行有三个数value,left_child,right_child，分别表示该节点关键字的值、左子节点的编号、右子节点的编号；

如果不存在左子节点或右子节点，则用0代替。

输出1

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

#include<

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;

inti,n;

2分）

for（i=1;

i<

=n;

i++）cin>

a[i].value>

a[i].left_child>

a[i].right_child;

is_bst（（5）,-INFINITE,INFINITE）<

endl;

//return0;

【算法】就是遍历一遍。

【代码】1、j-i；

2、cur1；

3、count1--;

4、count2--;

5cur1=a[j]；

年份】2013年

八、【题目】

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

请填空。

（每空3分，共

12分）

intdelnum（char*s）

inti,j;

j=0;

for（i=0;

s[i]!

='

\0'

i++）

if（s[i]<

——————1——————s[i]>

9'

）{

s[j]=s[i];

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

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

constintSIZE=30;

chars[SIZE];

intlen,i;

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

len=delnum（s）;

len;

cout<

——————4——————）;

endl;

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

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

usingnamespacestd;

constintSIZE=100;

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

记录第i行前j个数的和

introwsum[SIZE+1][SIZE+1];

//rowsum[i][j]intm,n,i,j,first,last,area,ans;

m>

n;

for（i=1;

=m;

for（j=1;

j<

j++）

matrix[i][j];

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

for（i=1;

i++）

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

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

for（first=1;

first<

first++）

for（last=first;

last<

last++）

——————4———

area+=————if（area>

ans）ans=area;

if（area<

0）

area=0;

ans<

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

遇到目前

最大值就记录下来。

【代码】1、[1][1]【3】【4】、【4】2、rowsum[i][0]=0

（其实可以随便填，比如【2】【3】、

【6】都可以）

•

3、rowsum[i][j-1]+matrix[i][j]；

4、area=0；

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

【年份】2014

十、【题目】（打印月历）输入月份m（iwme12），按一定格式打印2015年第m月的月历。

（第三、四空2.5分，

其余3分）

例如，2015年1月的月历打印效果如下（第一列为周日）：

SMTWTFS

123

45678910

11121314151617

18192021222324

25262728293031

string>

constintd