NOIP真题
（哥德巴赫猜想） 哥德巴赫猜想是指，任一大于 2 的偶数都可写成两个质数之和。迄今 为止， 这仍然是一个著名的世界难题，被誉为数学王冠上的明珠。 试编写程序，验证任一大 于 2 且不超过 n 的偶数都能写成两个质数之和。
#include<iostream>
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 % ② ______) {
tmp = false;
break;
}
if (tmp) {
r++;
③_________
}
}
ans = 0;
for (i = 2; i <= n / 2; i++) { // i=n/2 表示缩小范围，排除重复情况。
tmp = false;
for (j = 1; j <= r; j++)
for (k = j; k <= r; k++)
if (i + i == ④ _______ ) {
tmp = true;
break;
}
if (tmp)
ans++;
}
cout<<ans<<endl;
return 0;
}若输入 n 为 2010 ，则输出 ⑤ _______ 时表示验证成功，即大于 2 且不超过 2010 的偶数都 满足哥德巴赫猜想。（过河问题） 在一个月黑风高的夜晚，有一群人在河的右岸，想通过唯一的一根独木桥 走到河的左岸。 在这伸手不见五指的黑夜里， 过桥时必须借助灯光来照明， 很不幸的是，他 们只有一盏灯。 另外，独木桥上最多承受两个人同时经过，否则将会坍塌。 每个人单独过桥 都需要一定的时间，不同的人需要的时间可能不同。两个人一起过桥时，由于只有一盏灯，所以需要的时间是较慢的那个人单独过桥时所花的时间。现输入 n（ 2≤n≤100）和这 n 个 人单独过桥时需要的时间，请计算总共最少需要多少时间，他们才能全部到达河的左岸。 例如，有 3 个人甲、乙、丙，他们单独过桥的时间分别为 1、 2、4，则总共最少需要 的时间为 7 。具体方法是：甲、乙一起过桥到河的左岸，甲单独回到河的右岸将灯带回，然 后甲、丙再一起过桥到河的左岸，总时间为 2+1+4=7 。
#include<iostream>
using namespace std;
const int SIZE = 100;
const int INFINITY = 10000;
const bool LEFT = true;
const bool RIGHT = false;
const bool LEFT_TO_RIGHT = true;
const bool RIGHT_TO_LEFT = false;
int n, hour[SIZE]; //存放每个人的过河时间
bool pos[SIZE];
int max(int a, int b) {
if (a > b)
return a;
else
return 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++; //人数加1
if (hour[i] > ans)
ans = hour[i]; //ans保留了最长的过桥时间，
}
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)
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)
ans = tmp;
⑤__________ ;
}
return ans;
}
return 0;
}
int main() {
int i;
cin>>n;
for (i = 1; i <=n; i++) {
cin>>hour[i];
pos[i] = RIGHT; //pos是记录每个元素所处的位置。
}
cout<<go(RIGHT_TO_LEFT)<<endl; //初始状态RIGHT_TO_LEFT
return 0;
}LZW 编码是一种自适应词典编码。在编码的过程中，开始时只有一部基础构造元素的编 码词典， 如果在编码的过程中遇到一个新的词条， 则该词条及一个新的编码会被追加到词典 中，并用于后继信息的编码。 举例说明，考虑一个待编码的信息串：“ xyx yy yy xyx ”。初始词典只有 3 个条目， 第一个为 x,编码为 1；第二个为 y，编码为 2；第三个为空格，编码为 3；于是串“ xyx”的 编码为 1-2-1 （其中 -为编码分隔符），加上后面的一个空格就是 1-2-1-3 。但由于有了一个 空格，我们就知道前面的“ xyx”是一个单词，而由于该单词没有在词典中，我们就可以自 适应的把这个词条添加到词典里，编码为 4，然后按照新的词典对后继信息进行编码，以此 类推。于是，最后得到编码： 1-2-1-3-2-2-3-5-3-4 。 我们可以看到，信息被压缩了。压缩好的信息传递到接受方，接收方也只要根据基础 词典就可以完成对该序列的完全恢复。 解码过程是编码过程的逆操作。 现在已知初始词典的 3 个条目如上述，接收端收到的编码信息为 2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6 ，则解码 后的信息串是” ______________________________________________________________ ”。
无向图 G 有 7 个顶点，若不存在奇数条边构成的简单回路，则它至多有 __________ 条 边。
记 T 为一队列初始为空现有 n 个总和不超过 32 的正整数依次入队如果无论这些数具 体为何值都能找到一种出队的方式使得存在某个时刻队列 T 中的数之和恰好为 9 那么 n 的最小值是 ________________。
#include <stdio.h>
#define SIZE 10
int main()
{
int data[SIZE], i, j, cnt, n, m;// 定义 //
scanf("%d %d\n", &n, &m);// 输入 n 和 m，此处我们输入的是 5 和 2//
for(i = 1; i <= n; i++)
scanf("%d", &data[i]);// 再次输入 i 个数 data[1] =96 data[2]=-8 data[3]=0 data[4]=16 data[5]=87//
for(i = 1; i <= n; i++)
{ //n=5//
cnt = 0;
for(j = 1; j<= n; j++)//n=5 ，data[1] =96 data[2]=-8 data[3]=0 data[4]= 16
data[5]=87//
if ((data[i] < data[j]) || (data[j] == data[i] && j< i))// 如果说 data[i]<data[j] ，或者说{data[j] 等于 data[i] ，同时 j 小于 i
cnt++;//cnt 的数目加 1//
if(cnt == m)// 如果说 cnt 等于 m 等于 2，因为 cnt=2 ，即整个程序运行了两遍，也运行两遍，换句话说，只有恰好运行两遍的数字才能满足题意。假设， data[1]=96 ，与
data[2]=-8 data[3]=0 data[4]= 16 data[5]=87 //比较大小时， 显然为最大， 不能比其他的数小，不满足条件 data[i] < data[j] ，同样， data[2]=-8 ，比它大的数有 3 个也不满足题意，
data[3]=0 //比它大的数有 4 个，不合题意 data[4]= 16 ，比它大的数恰恰只有两个，满足题意，为所输出 //
printf("%d\n", data[i]);// 输出 data[i]//
}
getch(); //（此语句在 windows 2000 以上系统用 winTC 编译 C 时需要加入，用以暂停查看屏幕）
return 0;
}输入： 5 2
96 -8 0 16 87
输出： ______
#include <stdio.h>
#define SIZE 100
int main()
{
int na, nb, a[SIZE], b[SIZE], i, j, k;// 定义 //
scanf("%d\n", &na);// 输入 5,即 na=5//
for (i = 1; i <= na; i++)
scanf("%d", &a[i]);// 输入数字， a[1]=1. a[2]=3 a[3]=5 a[4]=7 a[5]=9//
scanf("%d\n", &nb);// 输入数字 4//
for (i = 1; i <= nb; i++)
scanf("%d", &b[i]);// 同理，输入数字 b[1] =2 b[2] =6 b[3] =10 b[4] =14//
i=1;
j=1;
while ((i <= na) && (j <= nb))
{// 当 i 小于等于 na 时，并且 j 小于等于 nb 时候 //
if (a[i] <= b[j])
{// 如果说 a[i]大于 b[j]//
printf("%d ", a[i]);// 输出 a[i]//
i++;//i 增加 1//
}
else {
printf("%d ", b[j]);// 否则输出 b[j]//
j++;
}
}
if (i <= na)// 如果 i 小于等于 na//
for (k = i; k<= na; k++)// 循环 //
printf("%d ", a[k]); //按照上面的循环条件输出数字 //
if (j <= nb)
for (k = j; k<= nb; k++)// 同理 //
printf ("%d ", b[k]);
getch();
return 0;
}输入： 5
1 3 5 7 9
4
2 6 10 14
输出：______
#include<iostream>
using namespace std;
const int NUM=5;
int r(int n)
{
int i;
if(n<=NUM)
return 0;
for(i=1;i<=NUM;i++)
if( r(n-i)<0)
return i;
return -1;
}
int main()
{
int n;
cin>>n;
cout<<r(n)<<endl;
return 0;
}输入： 16
输出： ______________
#include<iostream>
#include<cstring>
using namespace std;
const int SIZE=100;
int n,m,r[SIZE];
bool map[SIZE][SIZE],found;
bool successful()
{
int i;
for(i=1;i<=n;i++)
if(!map[r[i]][r[i%n+1]])
return false;
return true;
}
void swap(int *a,int *b)
{
int t;
t=*a;
*a=*b;
*b=t;
}
void perm(int left,int right)
{
int i;
if(found)
return ;
if(left>right)
{
if(successful())
{
for(i=1;i<=n;i++)
cout<<r[i]<<' ';
found=true;
}
return ;
}
for(i=left;i<=right;i++)
{
swap(r+left,r+i);
perm(left+1,right);
swap(r+left,r+i);
}
}
int main()
{
int x,y,i;
cin>>n>>m;
memset(map,false,sizeof(map));
for(i=1;i<=m;i++)
{
cin>>x>>y;
map[x][y]=true;
map[y][x]=true;
}
for(i=1;i<=n;i++)
r[i]=i;
found=false;
perm(1,n);
if(!found)
cout<<"No solution!"<<endl;
return 0;
}输入： 9 12
1 2
2 3
3 4
4 5
5 6
6 1
1 7
2 7
3 8
4 8
5 9
6 9
输出： _________
( 过河问题 ) 在一个月黑风高的夜晚 , 有一群人在河的右岸 , 想通过唯一的一根独木桥走到 河的左岸 . 在伸手不见五指的黑夜里 , 过桥时必须借照灯光来照明 , 不幸的是 , 他们只有一盏灯 . 另外, 独木桥上最多能承受两个人同时经过 , 否则将会坍塌 . 每个人单独过独木桥都需要一定 的时间 , 不同的人要的时间可能不同 . 两个人一起过独木桥时 , 由于只有一盏灯 , 所以需要的时 间是较慢的那个人单独过桥所花费的时间 . 现在输入 N(2<=N<1000)和这 N 个人单独过桥需要 的时间 , 请计算总共最少需要多少时间 , 他们才能全部到达河左岸 .
例如, 有 3 个人甲、乙、丙 , 他们单独过桥的时间分别为 1、2、4, 则总共最少需要的时 间为 7. 具体方法是 : 甲、乙一起过桥到河的左岸 , 甲单独回到河的右岸将灯带回 , 然后甲、丙 在一起过桥到河的左岸 , 总时间为 2+1+4=7.
#include<iostream>
#include<cstring>
using namespace std;
const int SIZE=100;
const int INFINITY = 10000;
const bool LEFT=true;
const bool RIGHT =false;
const bool LEFT_TO_RIGHT=true;
const bool RIGHT_TO_LEFT=false;
int n,hour[SIZE];
bool pos[SIZE];
int max(int a,int b)
{
if(a>b)
return a;
else
return 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)
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)
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<<go[RIGHT_TO_LEFT)<<endl;
return 0;
}（烽火传递） 烽火台又称烽燧，是重要的军事防御设施，一般建在险要处或交通要道上。 一旦有敌情发生，白天燃烧柴草，通过浓烟表达信息；夜晚燃烧干柴，以火光传递军情。在 某两座城市之间有 n 个烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确地传 递，在连续的 m个烽火台中至少要有一个发出信号。现输入 n、m和每个烽火台发出信号的代 价，请计算总共最少花费多少代价，才能使敌军来袭之时，情报能在这两座城市之间准确传 递。
例如，有 5 个烽火台，他们发出信号的代价依次为 1，2，5，6，2，，且 m为 3，则总共最少 花费代价为 4，即由第 2 个和第 5 个烽火台发出信号。
#include<iostream>
#include<cstring>
using namespace std;
const int SIZE=100;
int n,m,r,value[SIZE],heap[SIZE],
pos[SIZE],home[SIZE],opt[SIZE];
//hep[i] 表示用顺序数组储存的堆 heap 中第 i 个元素的值
//pos[i] 表示 opt[i] 在堆 heap中的位置，即 heap[pos[i]]=opt[i]
//home[i] 表示 heap[i] 在序列 opt 中的位置，即 opt[home[i]]=heap[i]
void swap(int i,int j)// 交换堆中的第 i 个和第 j 个元素
{
int tmp;
pos[home[i]]=j;
pos[home[j]]=i;
tmp=heap[i];
head[i]=head[j];
heap[j]=tmp;
tmp=home[i];
home[i]=home[j];
home[j]=tmp;
}
void add(int k)// 在堆中插入 opt[k]
{
int i;
r++;
heap[r]= ① ;
pos[k]=r;
② ;
i=r;
while( (i>1) && (heap[i]<heap[i/2]) )
{
swap(i,i/2);
i/=2;
}
}
void remove(int k)// 在堆中删除 opt[k]
{
int i,j;
i=pos[k];
swap(i,r);;
r--;
if(i==r+1)
return ;
while( (i>1)&&(heap[i]<heap[i/2]) )
{
swap(i,i/2);
i/=2;
}
while(i+i<=r)
{
if( (i+i+1<=r) && (heap[i+i+1]<heap[i+i]) )
j=i+i+1;
else
③ ;
if(hea[i]>heap[j])
{
④ ;
i=j;
}
else
break;
}
}
int main()
{
int i;
cin>>n>>m;
for(i=1;i<=n;i+++)
cin>>value[i];
r=0;
for(i=1;i<=m;i++)
{
opt[i]=value[i];
add(i);
}
for(i=m+1;i<=n;i++)
{
opt[i]= ⑤ ;
remove( ⑥ );
add(i);
}
cout<<heap[1]<<endl;
return 0;
}每份考卷都有一个 8 位二进制序列号。当且仅当一个序列号含有偶数个 1 时，它才是有效的。例如，00000000、01010011都是有效的序列号，而 11111110 不是。那么，有效的序列号共有____个。
定义字符串的基本操作为：删除一个字符、插入一个字符和将一个字符修改成另一个字符这三种操作。将字符串 A 变成字符串 B 的最少操作步数，称为字符串 A 到字符串 B 的编辑距离。字符串 "ABCDEFG" 到字符串 "BADECG" 的编辑距离为____。
#include <iostream>
using namespace std;
int main(){
int i, n, m, ans;
cin>>n>>m;
i = n;
ans = 0;
while (i <= m){
ans += i;
i++;
}
cout<<ans<<endl;
return 0;
}输入： 10 20
输出： _________
#include <iostream>
#include <string>
using namespace std;
int main(){
string map = "22233344455566677778889999";
string tel;
int i;
cin>>tel;
for (i = 0; i < tel.length(); i++)
if ((tel[i] >= '0') && (tel[i] <= '9'))
cout<<tel[i];
else if ((tel[i] >= 'A') && (tel[i] <= 'Z'))
cout<<map[tel[i] - 'A'];
cout<<endl;
return 0;
}输入： CCF-NOIP-2011
输出： _______________
#include <iostream>
#include <cstring>
using namespace std;
const int SIZE = 100;
int main(){
int n, i, sum, x, a[SIZE];
cin>>n;
memset(a, 0, sizeof(a));
for (i = 1; i <= n; i++) {
cin>>x;
a[x]++;
}
i = 0; sum = 0;
while (sum < (n / 2 + 1)) {
i++;
sum += a[i];
}
cout<<i<<endl;
return 0;
}输入：
11
4 5 6 6 4 3 3 2 3 2 1
输出：________
#include <iostream>
using namespace std;
int solve(int n, int m){Preferences
int i, sum;
if (m == 1) return 1;
sum = 0;
for (i = 1; i < n; i++)
sum += solve(i, m - 1);
return sum;
}
int main(){
int n, m;
cin>>n>>m;
cout<<solve(n, m)<<endl;
return 0;
}输入： 7 4
输出： _________
（子矩阵） 给输入一个 n1*m1 的矩阵 a，和 n2*m2 的矩阵 b，问 a 中是否存在子矩阵和 b 相等。 若存在，输出所有子矩阵左上角的坐标：若不存在输出“ There is no answer ”。
#include <iostream>
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<<i<<' '<<j<<endl;
⑤;
}
}
if (!haveAns)
cout<<"There is no answer"<<endl;
return 0;
}( 大整数开方 ) 输入一个正整数 n（1≤n≤10100），试用二分法计算它的平方根的整数部分。
#include <iostream>
#include <string>
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++)
①+= 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;
return ans;
}
hugeint add(hugeint a, hugeint b){
//计算大整数 a 和 b 的和
int i; hugeint ans;
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++;
return ans;
}
hugeint average(hugeint a, hugeint b){
//计算大整数 a 和 b 的平均数的整数部分
int i; hugeint ans;
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--;
return ans;
}
hugeint plustwo(hugeint a) {
//计算大整数 a 加 2 后的结果
int i; hugeint ans;
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)⑤;
return ans;
}
bool over(hugeint a, hugeint b){
//若大整数 a>b 则返回 true，否则返回 false
int i;
if (⑥) return false;
if (a.len > b.len) return true;
for (i = a.len; i >= 1; i--) {
if (a.num[i] < b.num[i])return false;
if (a.num[i] > b.num[i]) return true;
}
return false;
}
int main(){
string s;
int i;
hugeint target, 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<<left.num[i];
cout<<endl;
return 0;
}平面图是可以画在平面上、且它的边仅在顶点上才能相交的简单无向 图。 4 个顶点的平面图至多有 6 条边，如右图所示。那么， 5 个顶点的平面 图至多有 ________ 条边。
