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

完善程序题总结归纳 By：七（6） yx一、【题目】（哥德巴赫猜想）哥德巴赫猜想是指，任一大于2的偶数都可写成两个质数之和。迄今为止，这仍然是一个著名的世界难题，被誉为数学王冠上的明珠。试编写程序，验证任一大于2且不超过n的偶数都能写成两个质数之和。#includeusing namespace std;int main() const int SIZE=1000; int n,r,pSIZE,i,j,k,ans; bool tmp; cinn; 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+; coutansendl; 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=N1000)和这N个人单独过桥需要的时间,请计算总共最少需要多少时间,他们才能全部到达河左岸. 例如,有3个人甲、乙、丙,他们单独过桥的时间分别为1、2、4,则总共最少需要的时间为7.具体方法是:甲、乙一起过桥到河的左岸,甲单独回到河的右岸将灯带回,然后甲、丙在一起过桥到河的左岸,总时间为2+1+4=7.#include#includeusing 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 ab?a:b;int go(bool stage) int i,j,num,tmp,ans; if(stage=right_to_left) num=0; ans=0; for(i=1;ians) 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(tmpans) 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(tmpn; for(i=1;ihouri; posi=right; coutgoright_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”。#includeusing namespace std;const int SIZE = 50;int n1,m1,n2,m2,aSIZESIZE,bSIZESIZE;int main() int i,j,k1,k2; bool good,haveAns; cinn1m1; for(i=1;i=n1;i+) for(j=1;jaij; cinn2m2; 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) couti jendl; ; if(!haveAns) coutThere is no answerbij;2、m1-m2+1；3、good=1;4、m2;5、haveAns=1;【年份】2011年四、【题目】(大整数开方) 输入一个正整数n（1n10100），试用二分法计算它的平方根的整数部分。#include#includeusing 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;i0) 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.lenb.len) ans.len=a.len; else ans.len=b.len; for(i=1;i0) 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=10) ) ans.numi+1+=ans.numi/10; ans.numi%=10; i+; if(ans.numans.len+10) ; return ans;bool over(hugeint a,hugeint b)/ 若大整数ab则返回true，否则返回false int i; if( ) return false; if( a.lenb.len ) return true; for(i=a.len;i=1;i-) if(a.numib.numi) return true; return false;int main() string s; int i; hugeint target,left,middle,right; cins; memset(target.num,0,sizeof(target.num); target.len=s.length(); for(i=1;i=1;i-) coutleft.numi; return 0;【算法】每二分一次，就判断一下答案在哪个区间，然后在那个区间继续二分，避免不必要的计算。【代码】1、 ans.numi+j-1 2、 ans.numi%=103、a.numi+b.numi 4、ans.numi % 25、ans.len+6、a.lenb.len7、08、times(middle,middle),target【年份】2011年五、【题目】（坐标统计）输入n个整点在平面上的坐标。对于每个点，可以控制所有位于它左下方的点（即x、y坐标都比它小），它可以控制的点的数目称为“战斗力”。依次输出每个点的战斗力，最后输出战斗力最高的点的编号（如果若干个点的战斗力并列最高，输出其中最大的编号）。#include using namespace std;const int SIZE =100;int xSIZE,ySIZE,fSIZE;int n,i,j,max_f,ans;int main()cinn;for(i=1;ixiyi;max_f=0;for(i=1;i=n;i+)fi= ;for(j=1;j=n;j+)if(xjxi & ) ;if( )max_f=fi; ;for(i=1;i=n;i+) coutfiendl;coutansendl;return 0;【算法】依次进行战斗力的计算，找出最大的一个【代码】1、0 2、yj1）& (fifi-1)（我写的是fimax_f） 5、ans=max_f（我写的是ans=i）其实我做的是对的，正确答案有bug；【年份】2012年六、【题目】（排列数）输入两个正整数n，m（1n20,1mn），在1n中任取m个数，按字典序从小到大输出所有这样的排列。例如： 输入：3 2 输出：1 21 3 2 1 2 33 1 3 2#include #include using namespace std;const int SIZE =25;bool usedSIZE;int dataSIZE;int n,m,i,j,k;bool flag;int main()cinnm;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+) coutdatai ;coutdatam=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 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;cinn;for (i = 1; i ai.valueai.left_childai.right_child;coutis_bst(5) , -INFINITE, INFINITE)endl;/（2分） return 0;【算法】 就是遍历一遍。【代码】1、j-i；2、cur1；3、count1-;4、count2-;5、cur1=aj；【年份】2013年八、【题目】(数字删除)下面程序的功能是将字符串中的数字字符删除后输出。请填空。(每空3分，共12分)#include using namespace std; int delnum(char *s) int i, j; j = 0; for(i = 0; si != 0; i+) if(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 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 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 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 #include 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(0m231)之间，请使用二分法求这n个整数的中位数。所谓中位数，是指将这n个数排序之后，排在正中间的数。(第五空2分，其余3分)#include 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 xi;lbound = 0;rbound = m;while( )mid = (lbound + rbound) / 2; ;for(i = 0; i n / 2)lbound = mid + 1;else ;cout mid lbound rbound count endl;cout rbound endl;return 0;【算法】用二分的方法，一步步缩小范围，当两根指针重合时，就一定是正确答案（“cout mid lbound rbound count endl;”这一句是打酱油的吗？）【代码】lbound = mid) count+ rbound = mid - 1【年份】2015年