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

.完善程序题总结归纳 By：七（6） yx一、【题目】（哥德巴赫猜想）哥德巴赫猜想是指，任一大于2的偶数都可写成两个质数之和。迄今为止，这仍然是一个著名的世界难题，被誉为数学王冠上的明珠。试编写程序，验证任一大于2且不超过n的偶数都能写成两个质数之和。#include<iostream>using namespace std;int main() const int SIZE=1000; int n,r,pSIZE,i,j,k,ans; bool tmp; cin>>n; r=1; p1=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<<ans<<endl; return 0;若输入n为2010，则输出 时表示验证成功，即大于2且不超过2010的偶数都满足哥德巴赫猜想。【算法】先for一遍，找出质数，然后对每一个偶数进行一一匹配（2除外），效率O（n3）【代码】1、tmp=1；2、pj;3、pr=j;4、pj+pk5、1004【年份】2010年二、【题目】(过河问题) 在一个月黑风高的夜晚,有一群人在河的右岸,想通过唯一的一根独木桥走到河的左岸.在伸手不见五指的黑夜里,过桥时必须借照灯光来照明,不幸的是,他们只有一盏灯.另外,独木桥上最多能承受两个人同时经过,否则将会坍塌.每个人单独过独木桥都需要一定的时间,不同的人要的时间可能不同.两个人一起过独木桥时,由于只有一盏灯,所以需要的时间是较慢的那个人单独过桥所花费的时间.现在输入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=1;const bool right =0;const bool left_to_right=1;精品.const bool right_to_left=0;int n,hoursize;bool possize;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(posi=right) num+; if( houri>ans) ans=houri; if( ) return ans; ans=infinity; for(i=1;i<=n-1;i+) if(posi=right) for(j=i+1;j<=n;j+) if(posj=right) posi=left; posj=left; tmp=max(houri,hourj)+ ; if(tmp<ans) ans=tmp; posi=right; posj=right; return ans; if(stage=left_to_right)精品. ans=infinity; for(i=1;i<=n;i+) if( ) posi=right; tmp= ; if(tmp<ans) ans=tmp; ; return ans; return 0;int main() int i; cin>>n; for(i=1;i<=n;i+) cin>>houri; posi=right; cout<<goright_to_left)<<endl; return 0;【算法】利用深搜，左右交替寻找最优解（maybe是动态规划）【代码】1、num<=2;2、go1;3、posj=1;4、houri+go0;5、posi=1;【年份】2010年三、【题目】精品.（子矩阵）给输入一个n1*m1的矩阵a，和n2*m2的矩阵b，问a中是否存在子矩阵和b相等。若存在，输出所有子矩阵左上角的坐标：若不存在输出“There isno answer”。#include<iostream>using namespace std;const int SIZE = 50;int n1,m1,n2,m2,aSIZESIZE,bSIZESIZE;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>>aij; 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(ai+k1-1j+k2-1!=bk1k2) good=false; if(good) cout<<i<< <<j<<endl; ; if(!haveAns) cout<<"There is no answer"<<endl; return 0;精品.【算法】枚举每一条对角线，进行判断。【代码】1、cin>>bij;2、m1-m2+1；3、good=1;4、m2;5、haveAns=1;【年份】2011年四、【题目】(大整数开方) 输入一个正整数n（1n10100），试用二分法计算它的平方根的整数部分。#include<iostream>#include<string>using namespace std;const int SIZE=200;struct hugeint int len,numSIZE;/其中len表示大整数的位数；num1表示个位，num2表示十位，以此类推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.numi*b.numj; for(i=1;i<=a.len+b.len;i+) ans.numi+1+=ans.numi/10; ; if(ans.numa.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.numi+= ; ans.numi+1+= ans.numi/10; ans.numi%=10; if(ans.numans.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.numi-1+=( )*10; ans.numi/=2; ans.num1/=2; if(ans.numans.len=0) ans.len-; return ans;hugeint plustwo(hugeint a)/ 计算大整数a加2之后的结果精品. int i; hugeint ans; ans=a; ans.num1+=2; i=1; while( (i<=ans.len)&&(ans.numi>=10) ) ans.numi+1+=ans.numi/10; ans.numi%=10; i+; if(ans.numans.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.numi<b.numi) return false; if(a.numi>b.numi) 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.numi=starget.len-i- ;精品. memset(left.num,0,sizeof(left.num); left.len=1; left.num1=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.numi; return 0;【算法】每二分一次，就判断一下答案在哪个区间，然后在那个区间继续二分，避免不必要的计算。【代码】1、 ans.numi+j-1 2、 ans.numi%=103、a.numi+b.numi 4、ans.numi % 25、ans.len+6、a.len<b.len7、08、times(middle,middle),target【年份】2011年五、【题目】（坐标统计）输入n个整点在平面上的坐标。对于每个点，可以控制所有位于它左下方的点（即x、y坐标都比它小），它可以控制的点的数目称为“战斗力”。依次输出每个点的战斗力，最后输出战斗力最高的点的编号（如果若干个点的战斗力并列最高，输出其中最大的编号）。精品.#include <iostream>using namespace std;const int SIZE =100;int xSIZE,ySIZE,fSIZE;int n,i,j,max_f,ans;int main()cin>>n;for(i=1;i<=n;i+) cin>>xi>>yi;max_f=0;for(i=1;i<=n;i+)fi= ;for(j=1;j<=n;j+)if(xj<xi && ) ;if( )max_f=fi; ;for(i=1;i<=n;i+) cout<<fi<<endl;cout<<ans<<endl;return 0;【算法】依次进行战斗力的计算，找出最大的一个【代码】1、0 2、yj<yi3、fi+; 4、（i>1）&& (fi>fi-1)（我写的是fi>max_f） 5、ans=max_f（我写的是ans=i）其实我做的是对的，正确答案有bug；精品.【年份】2012年六、【题目】（排列数）输入两个正整数n，m（1<n<20,1<m<n），在1n中任取m个数，按字典序从小到大输出所有这样的排列。例如： 输入：3 2 输出：1 21 3 2 1 2 33 1 3 2#include <iostream>#include <cstring>using namespace std;const int SIZE =25;bool usedSIZE;int dataSIZE;int n,m,i,j,k;bool flag;int main()cin>>n>>m;memset(used,false,sizeof(used);for(i=1;i<=m;i+)datai=i;usedi=true;flag=true;while(flag)for(i=1;i<=m-1;i+) cout<<datai<<" "cout<<datam<<endl;flag= ;for(i=m;i>=1;i-) ;for(j=datai+1;j<=n;j+)if(!usedj)usedj=true;精品.datai= ;flag=true;break;if(flag)for(k=i+1;k<=m;k+)for(j=1;j<= ;j+)if(!usedj)datak=j;usedj=true;break; ;return 0;【算法】直接进行枚举，一个个进行选择【代码】1、 0 2、useddatai=0 3、j 4、n 5、break【年份】2012年七、【题目】（二叉查找树）二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。试判断一棵树是否为二叉查找树。 输入的第一行包含一个整数n，表示这棵树有n个顶点，编号分别为1, 2, , n，其中编号为1的为根结点。之后的第i行有三个数value, left_child, right_child，分别表示该节点关键字的值、左子节点的编号、右子节点的编号；如果不存在左子节点或右子节点，则用精品.0代替。输出1表示这棵树是二叉查找树，输出0则表示不是。 #include <iostream>using namespace std;const int SIZE = 100;const intINFINITE = 1000000;struct node int left_child, right_child, value;node aSIZE;int is_bst(int root, int lower_bound, int upper_bound)int cur;if (root = 0)return 1;cur = aroot.value;if (cur > lower_bound) && (1) ) &&/（3分）(is_bst(aroot.left_child, lower_bound, cur) = 1) &&(is_bst(2) ,(3) ,(4) ) = 1)/（3分，3分，3分） return 1;return 0;int main()int i, n;cin>>n;for (i = 1; i <= n; i+)cin>>ai.value>>ai.left_child>>ai.right_child;cout<<is_bst(5) , -INFINITE, INFINITE)<<endl;/（2分） return 0;【算法】 就是遍历一遍。【代码】1、j-i；2、cur1；3、count1-;4、count2-;5、cur1=aj；精品.【年份】2013年八、【题目】(数字删除)下面程序的功能是将字符串中的数字字符删除后输出。请填空。(每空3分，共12分)#include <iostream> using namespace std; int delnum(char *s) int i, j; j = 0; for(i = 0; si != 0; i+) if(si < 0 1 si > 9) sj = si; 2; return 3; const int SIZE = 30; int main() char sSIZE; int len, i; cin.getline(s, sizeof(s); len = delnum(s); for(i = 0; i < len; i+) cout << 4）; cout << endl; return 0; 【算法】搜索一遍，把非字母的字符保留。【代码】1、| 2、j+； 3、j 4、si【年份】2014年精品.九、【题目】(最大子矩阵和)给出m行n列的整数矩阵，求最大的子矩阵和(子矩阵不能为空)。 输入第一行包含两个整数m和n，即矩阵的行数和列数。之后m行，每行n个整数，描述整个矩阵。程序最终输出最大的子矩阵和。(最后一空4分，其余3分，共16分) 比如在如下这个矩阵中： 4 4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 拥有最大和的子矩阵为： 9 2 -4 1 -1 8 其和为15 3 3 -2 10 20-1 100 -20 -2 -3最大子矩阵和为128 4 4 0 -2 -9 -9-9 11 5 7-4 -3 -7 -6-1 7 7 5最大子矩阵和为26#include <iostream> using namespace std; const int SIZE = 100; int matrixSIZE + 1SIZE + 1; int rowsumSIZE + 1SIZE + 1; /rowsumij记录第i行前j个数的和 int m, n, i, j, first, last, area, ans; int main() cin >> m >> n; 精品. for(i = 1; i <= m; i+) for(j = 1; j <= n; j+) cin >> matrixij; ans = matrix1; for(i = 1; i <= m; i +) 2; for(i = 1; i <= m; i+) for(j = 1; j <= n; j+) rowsumij =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 << ans << endl; return 0; 【算法】三个for，枚举子矩阵左上，右上和高。遇到目前最大值就记录下来。【代码】1、11（其实可以随便填，比如【2】【3】、【3】【4】、【4】【6】都可以）2、rowsumi0 = 0；3、rowsumij - 1 + matrixij；4、area = 0；5、rowsumilast - rowsumifirst - 1【年份】2014 十、【题目】(打印月历)输入月份m(1m12)，按一定格式打印2015年第m月的月历。精品.(第三、四空2.5分，其余3分)例如，2015年1月的月历打印效果如下(第一列为周日)：S M T W T F S1 2 34 5 6 7 8 9 1011 12 13 14 15 16 1718 19 20 21 22 23 2425 26 27 28 29 30 31#include <iostream>#include <string>using namespace std;const int dayNum = -1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31;int m, offset, i;int main()cin >> m;cout << "StMtTtWtTtFtS" << endl; /t为TAB制表符 ;for(i = 1; i < m; i+)offset = ;for(i = 0; i < offset; i+)精品.cout << t;for(i = 1; i <= ; i+)cout << ;if(i = dayNumm | = 0)cout << endl;elsecout << t;【算法】先判断之前空几格，然后一个个打进去。【代码】offset = 4 (offset + dayNumi) % 7 dayNumm i (offset + i) % 7【年份】2015年十一、【题目】(中位数median)给定n(n为奇数且小于1000)个整数，整数的范围在0m(0<m<231)之间，请使用二分法求这n个整数的中位数。所谓中位数，是指将这n个数排序之后，排在正中间的数。(第五空2分，其余3分)#include <iostream>using namespace std;精品.const int MAXN = 1000;int n, i, lbound, rbound, mid, m, count;int xMAXN;第6页，共7页int main()cin >> n >> m;for(i = 0; i < n; i+)cin >> xi;lbound = 0;rbound = m;while( )mid = (lbound + rbound) / 2; ;for(i = 0; i < n; i+)if( ) ;if(count > n / 2)lbound = mid + 1;else ;cout << mid << " " << lbound << " " << rbound << " " << count << endl;精品.cout << rbound << endl;return 0;【算法】用二分的方法，一步步缩小范围，当两根指针重合时，就一定是正确答案（“cout << mid << " " << lbound << " " << rbound << " " << count << endl;”这一句是打酱油的吗？）【代码】lbound <= rbound) count = 0 xi >= mid) count+ rbound = mid - 1【年份】2015年如有侵权请联系告知删除，感谢你们的配合！精品