NOIP2014普及组复赛试题讲解(c++版本).ppt

NOIP2014普及组复赛题解,NOIP2014普及组C+,-2-,第1题“珠心算测验”简述,某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？直接三重循环穷举外层循环枚举和，两个内层循环分别枚举两个加数，如果有两个数之和对应外层循环的枚举值，退出两个内层循环注意：找到满足等式的必须退出两个内循环。注意看清题意：其中有多少个数，恰好等于集合中另外两个(不同的)数之和。,-3-,参考程序C+,#includeusingnamespacestd;intmain()intn,i,j,k,ans=0;inta105;cinn;for(i=1;iai;for(i=1;i=n;i+)/和为Aiboolf=false;for(j=1;jn;j+)for(k=j+1;k=n;k+),if(ai=aj+ak)f=true;ans+;break;if(f)break;cout=A*B判断互质，最大公约数为1判断A和B最小A*ansBabl;ansa=100;ansb=1;,for(a1=l;a1=1;a1-)for(b1=l;b1=1;b1-)if(a1*b=a*b1)if(gcd(a1,b1)=1)if(ansa*b1ansb*a1)ansa=a1;ansb=b1;coutansanxy;u=l=1;d=r=n;while(1)if(x=u)s=s+y-l+1;break;elses=s+r-l;if(y=r)s=s+x-u+1;break;elses=s+d-u;if(x=d),s=s+r-y+1;break;elses=s+r-l;if(y=l)s=s+d-x+1;break;elses=s+d-u;u+;l+;d-;r-;cout=row-k+1)for(inti=rk-1+1;i=n;i+)rk=i;w(k+1);,-13-,暴力搜索程序模块,voidh(intg)if(g=col+1)intt=pd();if(t=col-g+1)for(inti=cg-1+1;i=m;i+)cg=i;h(g+1);,-14-,暴力搜索程序模块,intpd()intsum=0;for(inti=1;i=row;i+)for(intj=1;jcol;j+)sum+=abs(aricj-aricj+1);for(intj=1;jnmrowcol;for(inti=1;iaij;w(1);coutans;return0;,-16-,确定解题思路AC,思路：搜索+DP枚举出选那些行算出j列各行之间的分数wj，k,j两列之间的分数vkj。fij表示已经选了i(数量)列，最后一列是j(下标)的最小分数且第i列是j状态转移方程：fij=min(fi-1k+wj+vkj)。,-17-,数据结构,amaxnmaxn/存放原数据n行m列的矩阵rmaxn/c存放枚举出的行号vxmaxnmaxnmaxn/vxIKJ记录i行k列与j列之间的差值的绝对值wmaxn/j列各行之间的分数vmaxnmaxn/k,j两列之间的分数fmaxnmaxn/i列，最后一列是j的最小分数且第i列是j,-18-,参考程序(DP部分),voiddp()memset(w,0,sizeof(w);memset(v,0,sizeof(v);memset(f,127,sizeof(f);for(intj=1;j=m;j+)for(inti=2;i=row;i+)wj+=abs(arij-ari-1j);for(intj=1;j=m;j+)f1j=wj;for(intj=2;j=m;j+)for(intk=1;kj;k+)for(inti=1;i=m;i+)vkj+=vxrikj;for(inti=2;i=col;i+)for(intj=i;j=m;j+)for(intk=i-1;k=j-1;k+)fij=min(fij,fi-1k+vkj+wj