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

2021年1月20日发(作者：肿胀)
完善程序题总结归纳


By
：七（
6
）
yx
一、
【题目】
（ 哥德巴赫猜想）哥德巴赫猜想是指，任一大于
2
的偶数都可写成两个质
数之和。
迄今为止，
这仍然是一个著名的世界难题，
被誉为数学王冠上的明珠。
试编写程序，
验证任一大于
2
且不超过
n
的偶数都能写成两个质数之和。

#include
using namespace std;
int main()
{
const int SIZE=1000;
int n,r,p[SIZE],i,j,k,ans;
bool tmp;
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< return 0;
}
若输入
n
为
2010
，则输出

⑤






时表示验证成功，即大于
2
且不超过
2010
的
偶数都满足哥德巴赫猜想。

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

【代码】

1
、
tmp=1
；
2
、
p[j];3
、
p[r]=j;4
、
p[j]+p[k]5
、1004
【年份】
2010
年

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



例如
,
有
3
个人甲、乙、丙
,
他们单独过桥的时间分别为
1
、
2
、
4,
则总共最少需要 的
时间为
7.
具体方法是
:
甲、乙一起过桥到河的左岸
,< br>甲单独回到河的右岸将灯带回
,
然后甲、
丙在一起过桥到河的左岸
,< br>总时间为
2+1+4=7.
#include
#include
using namespace std;
const int size=100;
const int infinity = 10000;
const bool left=1;
const bool right =0;
const bool left_to_right=1;
const bool right_to_left=0;
int n,hour[size];
bool pos[size];
int max(int a,int b){return a>b?a:b;}
int go(bool stage)
{
int i,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(
①







)
return ans;
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;

}
return ans;
}
if(stage==left_to_right)
{
ans=infinity;
for(i=1;i<=n;i++)
if(
③







)
{
pos[i]=right;
tmp=
④

if(tmp ans=tmp;

⑤






;
}
return ans;
}
return 0;
}
int main()
{
int i;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>hour[i];
pos[i]=right;
}
cout< return 0;
}

【算法】

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

【代码 】
1
、
num<=2;2
、
go[1];3
、
po s[j]==1;
4
、
hour[i]+go[0];5
、
pos[i]=1;
【年份】
2010
年

三、
【题目】

（ 子矩阵）
给输入一个
n1*m1
的矩阵
a
，和
n2*m2< br>的矩阵
b
，问
a
中是否存在子矩阵和
b
相等。若存在 ，输出所有子矩阵左上角的坐标：若不存在输出“
There isno answer
”
。

#include
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++)

①





;
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<<
return 0;
}

【算法】

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

【代码】

1
、
cin>>b[i][j];2
、
m1-m2+1
；
3
、
g ood=1;4
、
m2;5
、
haveAns=1;
【年份】
2011
年

四、
【题目】

(
大整数开方
)

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

#include
#include
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(,0,sizeof());
for(i=1;i<=;i++)
for(j=1;j<=;j++)

①






+=[i]*[j];
for(i=1;i<=+;i++){
[i+1]+=[i]/10;

②









;
}
if([+]>0)
=+;
else
=+-1;
return ans;
}

hugeint add(hugeint a,hugeint b)
//
计算大整数
a
和
b
的和

{
int i;
hugeint ans;
memset(,0,sizeof());
if(>)
=;
else
=;
for(i=1;i<=;i++){
[i]+=
③







;
[i+1]+= [i]/10;
[i]%=10;
}
if([+1]>0)
++;
return ans;
}

hugeint average(hugeint a,hugeint b)
//
计算大整数
a
和
b
的平均数的整数部分

{
int i;
hugeint ans;
ans=add(a,b);
for(i=;i>=2;i--){
[i-1]+=(
④
)*10;

[i]/=2;
}
[1]/=2;
if([]==0)
--;
return ans;
}

hugeint plustwo(hugeint a)
//
计算大整数
a
加
2
之后的结果

{
int i;
hugeint ans;
ans=a;
[1]+=2;
i=1;
while( (i<=)&&([i]>=10) ){
[i+1]+=[i]/10;
[i]%=10;
i++;
}
if([+1]>0)

⑤




;
return ans;
}

bool over(hugeint a,hugeint b)
//
若大整数
a>b
则返回
true
，否则返回
false
{
int i;
if(
⑥





)
return false;
if( > )
return true;
for(i=;i>=1;i--){
if([i]<[i])
return false;
if([i]>[i])
return true;
}
return false;
}

int main()
{
string s;
int i;
hugeint target,left,middle,right;
cin>>s;
memset(,0,sizeof());
=();
for(i=1;i<=;i++)
[i]=s[-i]-
⑦




;
memset(,0,sizeof());
=1;
[1]=1;
right=target;


do{
middle=average(left,right);
if(over(






⑧
))
right=middle;
else
left=middle;
}while(!over(plustwo(left),right) );
for(i=;i>=1;i--)
cout<<[i];
return 0;
}

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

【代码】
1
、

[i+j-1]

2
、

[i]%=10
3
、
[i]+[i]

4
、
[i] % 2
5
、
++
6
、
<
7
、
'0'
8
、
times(middle,middle),target

【年份】
2011
年

五、
【题目】
（坐标统计） 输入
n
个整点在平面上的坐标。对于每个点，可以控制所
有位于它左下方的点（即x
、
y
坐标都比它小），它可以控制的点的数目称为“战斗力”。
依次输 出每个点的战斗力，
最后输出战斗力最高的点的编号
（如果若干个点的战斗力并列最
高 ，输出其中最大的编号）。


#include
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;