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

《NOIP2014普及组复赛试题讲解(c++版本).ppt》由会员分享，可在线阅读，更多相关《NOIP2014普及组复赛试题讲解(c++版本).ppt（19页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、2017.07.28试题分析NOIP2014普及组复赛题解NOIP2014普及组C+-2-第1题“珠心算测验”简述某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？直接三重循环穷举外层循环枚举和，两个内层循环分别枚举两个加数，如果有两个数之和对应外层循环的枚举值，退出两个内层循环注意：找到满足等式的必须退出两个内循环。注意看清题意：其中有多少个数，恰好等于集合中另外两个(不同的)数之和。-3-参考程序C+#includeusingnamespacestd;intma

2、in()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,避免精度问题，转换成乘法A*B=A*B判断互质，最大公约数为1判断A和B最小A*ansB=ansA*B找到更小的A和B设置为ansA和ansB-6-主程序#includeusingnamespacestd;intgcd(intx,inty)intt;t=x%y;if(t=0)ret

3、urny;elsereturngcd(y,t);intmain()inta,b,l,a1,b1,ansa,ansb;cinabl;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;coutansaansb;return0;-7-第3题“螺旋矩阵”简述一个n行n列的螺旋矩阵可由如下方法生成：从矩阵的左上角（第1行第1列）出发，初始时向右移动；如果前方是未曾经过的格子，则继续前进，否则右转；重复上述操作直至经过矩阵中所有

4、格子。根据经过顺序，在格子中依次填入1,2,3,.,n2，便构成了一个螺旋矩阵。下图是一个n=4时的螺旋矩阵。现给出矩阵大小n以及i和j，请你求出该矩阵中第i行第j列的数是多少。-8-确定解题思路思想：剥洋葱皮（分成一个个口）先找出这个点在第几个口中。口的边长就是n-2*c+2。c表示层一个个口,整行整列处理u表示最上行，d表示最下行，l表示最左列，r表示最右列,计算出起始数值，判断目标行、列是否在这个口中，按u-r-d-l的顺序判断。没有找到，目标行、列，则收缩一圈，循环执行-9-参考程序#includeusingnamespacestd;intmain()longintn,u,d,l,r,

5、s=0,x,y;cinnxy;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

6、=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;j=col;j+)for(inti=1;inmrowcol;for(inti=1;i=n;i+)for(intj=1;jaij;w(1);coutans;return0;-16-确定解题思路AC思路：搜索+DP枚举出选那些行算出j列各行之间的分数wj，k,j两列之间的分数vkj。fij表示已经选了i(数量)列，最后一列是j(下标)的最小分数

7、且第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

8、=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);for(inti=col;i=m;i+)ans=min(ans,fcoli);2017.07.28试题分析BYETheEND温馨提示：温馨提示：本题解内的程序都已经本题解内的程序都已经ACAC，由，由于代码较长，可以查看于代码较长，可以查看CPPCPP文件文件