第一题 哥德巴赫猜想
题目描述
输入一个偶数 N，验证 4 ∼ N 所有偶数是否符合哥德巴赫猜想：任一大于 2的偶数都可写成两个质数之和。如果一个数不止一种分法，则输出第一个加数相比其他分法最小的方案。例如 10 ，10 = 3 + 7 = 5 + 5，则 10 = 5 + 5 是错误答案。
输入格式
第一行输入一个正偶数 N
输出格式
首先先输出正偶数 2 i + 2 ，然后输出等号，再输出加和为 2 i + 2且第一个加数最小的两个质数，以加号隔开。
样例 #1
样例输入 #1
10
样例输出 #1
4=2+2 6=3+3 8=3+5 10=3+7
提示
数据保证，$ 4 \leq N\leq10000$。
解题思路
1）欧拉筛法，筛选出素数。
2）双重循环，第一层 i 穷举4到n，第二层 j 从2到n/2穷举两数之和。
3）如果 j 是素数，就输出 j 和 i-j 并退了出当前的 j 循环，继续下一个i数。
参考代码
#include <bits/stdc++.h> using namespace std; int np[10010],p[5000]; int n,x,cnt; void prime() { for(int i=2;i<=n;i++) { if(!np[i])p[cnt++]=i; for(int j=0;i*p[j]<=n&&j<cnt;j++) { np[i*p[j]]=1; if(!i%p[j]) break; } } } int main() { scanf("%d",&n); prime(); for(x=4;x<=n;x+=2) { for(int i=0;i<cnt;i++) { if(!np[x-p[i]]) { printf("%d=%d+%d\n",x,p[i],x-p[i]); break; } } } return 0; }
第二题 [NOIP2007 普及组] 奖学金
题目描述
某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前 5名学生发奖学金。期末，每个学生都有 3门课的成绩:语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学 排在前面，这样，每个学生的排序是唯一确定的。
任务：先根据输入的 3 门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。注意，在前 5 名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据(每行输出两个数:学号、总分) 是:
7 279
5 279
这两行数据的含义是:总分最高的两个同学的学号依次是 7 号、5号。这两名同学的总分都是 279(总分等于输入的语文、数学、英语三科成绩之和) ，但学号为 7 的学生语文成绩更高一些。如果你的前两名的输出数据是:
5 279
7 279
则按输出错误处理，不能得分。
输入格式
共 n + 1 行。
第 1行为一个正整数n ( ≤ 300 )，表示该校参加评选的学生人数。
第 2 到 n + 1 行，每行有 3个用空格隔开的数字，每个数字都在 0到 100之间。第 j行的 3 个数字依次表示学号为 j − 1的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为 1 ∼ n （恰好是输入数据的行号减 1 ）。
所给的数据都是正确的，不必检验。
//感谢 黄小U饮品 修正输入格式
输出格式
共 5 行，每行是两个用空格隔开的正整数，依次表示前 5名学生的学号和总分。
样例 #1
样例输入 #1
6 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98
样例输出 #1
6 265 4 264 3 258 2 244 1 237
样例 #2
样例输入 #2
8 80 89 89 88 98 78 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98
样例输出 #2
8 265 2 264 6 264 1 258 5 258
解题思路
1）创立结构体，储存学生信息。
2）输入学生信息，并进行排序。
3）输出。
参考代码
#include<bits/stdc++.h> using namespace std; struct student{ int num; int chinese; int math; int english; int sum; }a[310]; int cmp(student a,student b) { if(a.sum!=b.sum) return a.sum>b.sum; else if(a.chinese!=b.chinese) return a.chinese>b.chinese; else return a.num<b.num; } int main() { int n; cin>>n; for(int i=1;i<=n;i++) { a[i].num=i; cin>>a[i].chinese>>a[i].english>>a[i].math; a[i].sum=a[i].chinese+a[i].english+a[i].math; } sort(a+1,a+n+1,cmp); for(int i=1;i<=5;i++) { cout<<a[i]. num<<" "<<a[i].sum<<endl; } return 0; }
第三题 填涂颜色
题目描述
由数字 0组成的方阵中，有一任意形状闭合圈，闭合圈由数字 1 构成，围圈时只走上下左右 4 个方向。现要求把闭合圈内的所有空间都填写成 2。例如：6 × 6的方阵（n = 6 ），涂色前和涂色后的方阵如下：
0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 2 2 1 1 1 2 2 2 1 1 2 2 2 2 1 1 1 1 1 1 1
输入格式
每组测试数据第一行一个整数 n ( 1 ≤ n ≤ 30 )。
接下来 n 行，由 0 和 1 组成的 n × n的方阵。
方阵内只有一个闭合圈，圈内至少有一个 0。
//感谢黄小U饮品指出本题数据和数据格式不一样. 已修改(输入格式)
输出格式
已经填好数字 2的完整方阵。
样例 #1
样例输入 #1
6 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1
样例输出 #1
0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 2 2 1 1 1 2 2 2 1 1 2 2 2 2 1 1 1 1 1 1 1
提示
对于 100 %的数据，1 ≤ n ≤ 30 。
解题思路
1）深度优先搜索进行染色。
2）这道题目其实就是求连通块。
3）将连通块中的数字换成2。
参考代码
#include <bits/stdc++.h> using namespace std; int a[32][32],b[32][32]; int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1}; int n,i,j; void dfs(int p,int q){ int i; if (p<0||p>n+1||q<0||q>n+1||a[p][q]!=0) return; a[p][q]=1; for (i=0;i<4;i++) dfs(p+dx[i],q+dy[i]); } int main(){ cin>>n; for (i=1;i<=n;i++) for (j=1;j<=n;j++){ cin>>b[i][j]; if (b[i][j]==0) a[i][j]=0; else a[i][j]=2; } dfs(0,0); for (i=1;i<=n;i++){ for (j=1;j<=n;j++) if (a[i][j]==0) cout<<2<<' '; else cout<<b[i][j]<<' '; cout<<'\n'; } }
第四题 投资的最大效益
题目背景
约翰先生获得了一大笔遗产，他暂时还用不上这一笔钱，他决定进行投资以获得更大的效益。银行工作人员向他提供了多种债券，每一种债券都能在固定的投资后，提供稳定的年利息。当然，每一种债券的投资额是不同的，一般来说，投资越大，收益也越大，而且，每一年还可以根据资金总额的增加，更换收益更大的债券。
题目描述
例如：有如下两种不同的债券：
输入格式
第一行为三个正整数 s , n , d，分别表示最初的总资产、年数和债券的种类。
接下来 d行，每行表示一种债券，两个正整数 a , b 分别表示债券的投资额和年利息。
输出格式
仅一个整数，表示 n 年后的最大总资产。
样例 #1
样例输入 #1
10000 4 2 4000 400 3000 250
样例输出 #1
14050
提示
解题思路
1）完全背包问题
2）要注意每一年的钱是上一年的本钱加上利息。
参考代码
#include<bits/stdc++.h> using namespace std; int s,n,m,f[10000000]; struct node{ int w; int v; }a[10000]; int main() { cin>>s>>n>>m; for (int i=1;i<=m;i++) cin>>a[i].w>>a[i].v; for (int k=1;k<=n;k++) { for (int i=1;i<=m;i++) for (int j=a[i].w;j<=s;j++) f[j]=max(f[j],f[j-a[i].w]+a[i].v); s+=f[s]; } printf("%d\n",s); return 0; }
