NOIP普及组复赛试题讲解c版本.pptx

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

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

2、1页/共19页第二页，共19页。-3-参考参考参考参考(cnk(cnk o)o)程序程序程序程序 C+C+n n#include#include n nusing namespace std;using namespace std;n nint main()int main()n n n nint n,i,j,k,ans=0;int n,i,j,k,ans=0;n nint a105;int a105;n ncinn;cinn;n nfor(i=1;i=n;i+)for(i=1;iai;cinai;n nfor(i=1;i=n;i+)/for(i=1;i=n;i+)/和为和为Ai Ai n n

3、 n n bool f=false;bool f=false;n nfor(j=1;jn;j+)for(j=1;jn;j+)n n n nfor(k=j+1;k=n;k+)for(k=j+1;k=n;k+)n n if(ai=aj+ak)f=true;ans+;break;if(f)break;cout=A/B,避免精度问题，转换成乘法n nA*B=A*B n n判断(pndun)互质，最大公约数为1n n判断(pndun)A和B最小n nA*ansB=ansA*B 找到更小的A和Bn n设置为ansA和ansB第4页/共19页第五页，共19页。-6-主程序主程序主程序主程序n n#inclu

4、de#include n nusing namespace std;using namespace std;n nint gcd(int x,int y)int gcd(int x,int y)n n n nint t;int t;n nt=x%y;t=x%y;n nif(t=0)if(t=0)n nreturn y;return y;n nelse return gcd(y,t);else return gcd(y,t);n n n nint main()int main()n n n nint a,b,l,a1,b1,ansa,ansb;int a,b,l,a1,b1,ansa,ansb;

5、n ncinabl;cinabl;n nansa=100;ansb=1;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;coutansa ansb;return 0;第5页/共19页第六页，共19页。-7-第第第第3 3题题题题“螺旋螺旋螺旋螺旋(luxun)(luxun)矩阵矩阵矩阵矩阵”简述简述简述简述n n一个一个n n行行n n列的螺旋矩阵可由如下方法生成：列的螺旋矩阵可由如下方法生成：n n从矩阵的左上角

6、（第从矩阵的左上角（第1 1行第行第1 1列）出发，初始时向右移动；如果前方是未曾经过的列）出发，初始时向右移动；如果前方是未曾经过的格子，则继续前进，否则右转；重复上述操作直至经过矩阵中所有格子。根据经格子，则继续前进，否则右转；重复上述操作直至经过矩阵中所有格子。根据经过顺序过顺序(shnx)(shnx)，在格子中依次填入，在格子中依次填入1,2,3,.,n21,2,3,.,n2，便构成了一个螺旋矩阵。，便构成了一个螺旋矩阵。n n下图是一个下图是一个n=4 n=4 时的螺旋矩阵。时的螺旋矩阵。n n现给出矩阵大小现给出矩阵大小n n以及以及i i和和j j，请你求出该矩阵中第，请你求出该

7、矩阵中第i i行第行第j j列的数是多少。列的数是多少。第6页/共19页第七页，共19页。-8-确定确定确定确定(qudng)(qudng)解题思路解题思路解题思路解题思路n n思想：剥洋葱皮（分成一个个口）n n先找出这个点在第几个口中。n n口的边长就是n-2*c+2。c表示层n n一个个口,整行整列处理n nu表示最上行，d表示最下行，l表示最左列，r表示最右列,计算出起始数值，判断目标(mbio)行、列是否在这个口中，按u-r-d-l的顺序判断。n n没有找到，目标(mbio)行、列，则收缩一圈，循环执行第7页/共19页第八页，共19页。-9-参考参考参考参考(cnk(cnk o)o)

8、程序程序程序程序n n#include#includen nusing namespace std;using namespace std;n nint main()int main()n n n nlong int n,u,d,l,r,s=0,x,y;long int n,u,d,l,r,s=0,x,y;n ncinnxy;cinnxy;n nu=l=1;d=r=n;u=l=1;d=r=n;n nwhile(1)while(1)n nif(x=u)if(x=u)n ns=s+y-l+1;break;s=s+y-l+1;break;n nelseelsen ns=s+r-l;s=s+r-l;n

9、 nif(y=r)if(y=r)n ns=s+x-u+1;s=s+x-u+1;break;break;n nelseelsen ns=s+d-u;s=s+d-u;n nif(x=d)if(x=d)n ns=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)n nfor(int i=rk-1+1;i=n;i+)n nrk=i;n nw(k+1);n nn n第11页/共19页第十二页，共19页。-13-暴力暴力暴力暴力(bol)(bol)搜索程序模块搜索程序模块搜索程序模块搜

10、索程序模块n nvoid h(int g)n n if(g=col+1)n nint t=pd();n nif(t=col-g+1)n nfor(int i=cg-1+1;i=m;i+)n ncg=i;n nh(g+1);n nn n第12页/共19页第十三页，共19页。-14-暴力暴力暴力暴力(bol)(bol)搜索程序模块搜索程序模块搜索程序模块搜索程序模块n nint pd()n nn nint sum=0;n nfor(int i=1;i=row;i+)n n for(int j=1;jcol;j+)n n sum+=abs(aricj-aricj+1);n nfor(int j=1;

11、j=col;j+)n n for(int i=1;inmrowcol;n nfor(int i=1;i=n;i+)n n for(int j=1;jaij;n n w(1);n n coutans;n n return 0;n n第14页/共19页第十五页，共19页。-16-确定确定确定确定(qudng)(qudng)解题思路解题思路解题思路解题思路ACACn n思路：搜索思路：搜索+DP+DPn n枚举出选那些枚举出选那些(nxi)(nxi)行行n n算出算出j j列各行之间的分数列各行之间的分数wjwj，k,jk,j两列之间的分数两列之间的分数vkjvkj。n nfijfij表示已经选了表

12、示已经选了i(i(数量数量)列，最后一列是列，最后一列是j(j(下标下标)的最小分数的最小分数n n且第且第i i列是列是j jn n状态转移方程：状态转移方程：fij=min(fi-1k+wj+vkj)fij=min(fi-1k+wj+vkj)。第15页/共19页第十六页，共19页。-17-数据结构数据结构数据结构数据结构(sh j ji(sh j ji u)u)n namaxnmaxn/存放原数据n行m列的矩阵n nrmaxn/c存放枚举出的行号n nvxmaxnmaxnmaxn/vxIKJ 记录i行k列与j列之间的差值的绝对值n nwmaxn/j列各行之间的分数(fnsh)n nvmax

13、nmaxn/k,j两列之间的分数(fnsh)n nfmaxnmaxn/i列，最后一列是j 的最小分数(fnsh)n n且第i列是j第16页/共19页第十七页，共19页。-18-参考程序参考程序参考程序参考程序(chngx)(DP(chngx)(DP部分部分部分部分)n nvoid dp()void dp()n n n nmemset(w,0,sizeof(w);memset(w,0,sizeof(w);n nmemset(v,0,sizeof(v);memset(v,0,sizeof(v);n nmemset(f,127,sizeof(f);memset(f,127,sizeof(f);n n

14、for(int j=1;j=m;j+)for(int j=1;j=m;j+)n n for(int i=2;i=row;i+)for(int i=2;i=row;i+)n n wj+=abs(arij-ari-1j);wj+=abs(arij-ari-1j);n nfor(int j=1;j=m;j+)for(int j=1;j=m;j+)n n f1j=wj;f1j=wj;n nfor(int j=2;j=m;j+)for(int j=2;j=m;j+)n n for(int k=1;kj;k+)for(int k=1;kj;k+)n n for(int i=1;i=m;i+)for(int

15、 i=1;i=m;i+)n n vkj+=vxrikj;vkj+=vxrikj;n n for(int i=2;i=col;i+)for(int i=2;i=col;i+)n n for(int j=i;j=m;j+)for(int j=i;j=m;j+)n n for(int k=i-1;k=j-1;k+)for(int k=i-1;k=j-1;k+)n n fij=min(fij,fi-1k+vkj+wj);fij=min(fij,fi-1k+vkj+wj);n n for(int i=col;i=m;i+)for(int i=col;i=m;i+)n n ans=min(ans,fcoli);ans=min(ans,fcoli);n n n n 第17页/共19页第十八页，共19页。BYEBYEThe END温馨提示：温馨提示：本题解内的程序都已经本题解内的程序都已经ACAC，由于代，由于代码较长，可以码较长，可以(ky)(ky)查看查看CPPCPP文件文件第18页/共19页第十九页，共19页。