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

完善程序题总结归纳By：七（6）yx一、【题目】（哥德巴赫猜想）哥德巴赫猜想是指，任一大于2的偶数都可写成两个质数之和。迄今为止，这仍然是一个著名的世界难题，被誉为数学王冠上的明珠。试编写程序，验证任一大于2且不超过n的偶数都能写成两个质数之和。#includeiostreamusingnamespacestd;intmain(){constintSIZE=1000;intn,r,p[SIZE],i,j,k,ans;booltmp;cinn;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++;}coutansendl;return0;}若输入n为2010，则输出⑤时表示验证成功，即大于2且不超过2010的偶数都满足哥德巴赫猜想。【算法】先for一遍，找出质数，然后对每一个偶数进行一一匹配（2除外），效率O（n^3）【代码】1、tmp=1；2、p[j];3、p[r]=j;4、p[j]+p[k]5、1004【年份】2010年二、【题目】(过河问题)在一个月黑风高的夜晚,有一群人在河的右岸,想通过唯一的一根独木桥走到河的左岸.在伸手不见五指的黑夜里,过桥时必须借照灯光来照明,不幸的是,他们只有一盏灯.另外,独木桥上最多能承受两个人同时经过,否则将会坍塌.每个人单独过独木桥都需要一定的时间,不同的人要的时间可能不同.两个人一起过独木桥时,由于只有一盏灯,所以需要的时间是较慢的那个人单独过桥所花费的时间.现在输入N(2=N1000)和这N个人单独过桥需要的时间,请计算总共最少需要多少时间,他们才能全部到达河左岸.例如,有3个人甲、乙、丙,他们单独过桥的时间分别为1、2、4,则总共最少需要的时间为7.具体方法是:甲、乙一起过桥到河的左岸,甲单独回到河的右岸将灯带回,然后甲、丙在一起过桥到河的左岸,总时间为2+1+4=7.#includeiostream#includecstringusingnamespacestd;constintsize=100;constintinfinity=10000;constboolleft=1;constboolright=0;constboolleft_to_right=1;constboolright_to_left=0;intn,hour[size];boolpos[size];intmax(inta,intb){returnab?a:b;}intgo(boolstage){inti,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(①)returnans;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(tmpans)ans=tmp;pos[i]=right;pos[j]=right;}returnans;}if(stage==left_to_right){ans=infinity;for(i=1;i=n;i++)if(③){pos[i]=right;tmp=④;if(tmpans)ans=tmp;⑤;}returnans;}return0;}intmain(){inti;cinn;for(i=1;i=n;i++){cinhour[i];pos[i]=right;}coutgo[right_to_left)endl;return0;}【算法】利用深搜，左右交替寻找最优解（maybe是动态规划）【代码】1、num=2;2、go[1];3、pos[j]==1;4、hour[i]+go[0];5、pos[i]=1;【年份】2010年三、【题目】（子矩阵）给输入一个n1*m1的矩阵a，和n2*m2的矩阵b，问a中是否存在子矩阵和b相等。若存在，输出所有子矩阵左上角的坐标：若不存在输出“Thereisnoanswer”。#includeiostreamusingnamespacestd;constintSIZE=50;intn1,m1,n2,m2,a[SIZE][SIZE],b[SIZE][SIZE];intmain(){inti,j,k1,k2;boolgood,haveAns;cinn1m1;for(i=1;i=n1;i++)for(j=1;j=m1;j++)cina[i][j];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(a[i+k1-1][j+k2-1]!=b[k1][k2])good=false;}if(good){couti''jendl;⑤;}}if(!haveAns)coutThereisnoanswerendl;return0;}【算法】枚举每一条对角线，进行判断。【代码】1、cinb[i][j];2、m1-m2+1；3、good=1;4、m2;5、haveAns=1;【年份】2011年四、【题目】(大整数开方)输入一个正整数n（1≤n≤10100），试用二分法计算它的平方根的整数部分。#includeiostream#includestringusingnamespacestd;constintSIZE=200;structhugeint{intlen,num[SIZE];};//其中len表示大整数的位数；num[1]表示个位，num[2]表示十位，以此类推hugeinttimes(hugeinta,hugeintb)//计算大整数a和b的乘积{inti,j;hugeintans;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;elseans.len=a.len+b.len-1;returnans;}hugeintadd(hugeinta,hugeintb)//计算大整数a和b的和{inti;hugeintans;memset(ans.num,0,sizeof(ans.num));if(a.lenb.len)ans.len=a.len;elseans.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++;returnans;}hugeintaverage(hugeinta,hugeintb)//计算大整数a和b的平均数的整数部分{inti;hugeintans;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--;returnans;}hugeintplustwo(hugeinta)//计算大整数a加2之后的结果{inti;hugeintans;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)⑤;returnans;}boolover(hugeinta,hugeintb)//若大整数ab则返回true，否则返回false{inti;if(⑥)returnfalse;if(a.lenb.len)returntrue;for(i=a.len;i=1;i--){if(a.num[i]b.num[i])returnfalse;if(a.num[i]b.num[i])returntrue;}returnfalse;}intmain(){strings;inti;hugeinttarget,left,middle,right;cins;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;elseleft=middle;}while(!over(plustwo(left),right));for(i=left.len;i=1;i--)coutleft.num[i];return0;}【算法】每二分一次，就判断一下答案在哪个区间，然后在那个区间继续二分，避免不必要的计算。【代码】1、ans.num[i+j-1]2、ans.num[i]%=103、a.num[i]+b.num[i]4、ans.num[i]%25、ans.len++6、a.lenb.len7、'0'8、times(middle,middle),target【年份】2011年五、【题目】（坐标统计）输入n个整点在平面上的坐标。对于每个点，可以控制所有位于它左下方的点（即x、y坐标都比它小），它可以控制的点的数目称为“战斗力”。依次输出每个点的战斗力，最后输出战斗力最高的点的编号（如果若干个点的战斗力并列最高，输出其中最大的编号）。#includeiostreamusingnamespacestd;constintSIZE=100;intx[SIZE],y[SIZE],f[SIZE];intn,i,j,max_f,ans;intmain(){cinn;for(i=1;i=n;i++)cinx[i]y[i];max_f=0;for(i=1;i=n;i++){f[i]=①;for(j=1;j=n;j++){if(x[j]x[i]&&②)③;}if(④){max_f=f[i];⑤;}}for(i=1;i=n;i++)coutf[i]endl;coutansendl;return0;}【算法】依次进行战斗力的计算，找出最大的一个【代码】1、02、y[j]y[i]3、f[i]++;4、（i1）&&(f[i]f[i-1])（我写的是f[i]max_f）5、ans