《noip2014年普与组复赛试题讲解(c++版本)》由会员分享，可在线阅读，更多相关《noip2014年普与组复赛试题讲解(c++版本)（19页珍藏版）》请在金锄头文库上搜索。
1、NOIP2014 普及组复赛题解,NOIP2014普及组C+,- 2 -,第1题 “珠心算测验”简述,某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？ 直接三重循环穷举 外层循环枚举和，两个内层循环分别枚举两个加数，如果有两个数之和对应外层循环的枚举值，退出两个内层循环 注意：找到满足等式的必须退出两个内循环。 注意看清题意：其中有多少个数，恰好等于集合中另外两个(不同的)数之和。,- 3 -,参考程序 C+,#include using namespace st
2、d; int main() int n,i,j,k,ans=0; int a105; cinn; for(i=1;iai; for(i=1;i=n;i+)/和为Ai bool f=false; for(j=1;jn;j+) for(k=j+1;k=n;k+),if (ai=aj+ak) f=true; ans+; break; if(f) break; coutans; return 0; ,- 4 -,第2题 “比例简化”简述,在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某一观点表示支持的有1498 人，反对的有902 人，那么赞同与反对的比例可以简单的记为14
3、98:902。 不过，如果把调查结果就以这种方式呈现出来，大多数人肯定不会满意。因为这个比例的数值太大，难以一眼看出它们的关系。对于上面这个例子，如果把比例记为5:3，虽然与真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。 现给出支持人数A，反对人数B，以及一个上限L，请你将A比B化简为A比B，要求在A和B均不大于L且A和B互质（两个整数的最大公约数是1）的 前 下 ，A/B A/B且A/B - A/B的值尽可能小。,- 5 -,确定解题思路,L很小，还是枚举 分别枚举化简之后的A和B 判断A/B =A/B,避免精度问题，转换成乘法 A*B=A*B 判断互质，最大公
4、约数为1 判断A和B最小 A*ansB=ansA*B 找到更小的A和B 设置为ansA和ansB,- 6 -,主程序,#include using namespace std; int gcd(int x,int y) int t; t=x%y; if(t=0) return y; else return gcd(y,t); int main() int a,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(a
5、nsa*b1ansb*a1) ansa=a1; ansb=b1; coutansa“ “ansb; return 0; ,- 7 -,第3题 “ 螺旋矩阵”简述,一个n行n列的螺旋矩阵可由如下方法生成： 从矩阵的左上角（第1行第1列）出发，初始时向右移动；如果前方是未曾经过的格子，则继续前进，否则右转；重复上述操作直至经过矩阵中所有格子。根据经过顺序，在格子中依次填入1, 2, 3, . , n2，便构成了一个螺旋矩阵。 下图是一个n = 4 时的螺旋矩阵。 现给出矩阵大小n以及i和j，请你求出该矩阵中第i行第j列的数是多少。,- 8 -,确定解题思路,思想：剥洋葱皮（分成一个个口 ） 先找出
6、这个点在第几个口中。 口的边长就是n-2*c+2。c表示层 一个个口,整行整列处理 u表示最上行，d表示最下行，l表示最左列，r表示最右列,计算出起始数值，判断目标行、列是否在这个口中，按u-r-d-l的顺序判断。 没有找到，目标行、列，则收缩一圈，循环执行,- 9 -,参考程序,#include using namespace std; int main() long int n,u,d,l,r,s=0,x,y; cinnxy; u=l=1;d=r=n; while(1) if(x=u) s=s+y-l+1;break; else s=s+r-l; if(y=r) s=s+x-u+1; br
7、eak; else s=s+d-u; if(x=d),s=s+r-y+1; break; else s=s+r-l; if(y=l) s=s+d-x+1;break; else s=s+d-u; u+;l+; d-;r-; couts; ,- 10 -,第4题 “子矩阵”简述,- 11 -,暴力搜索（预计得分50分）,构造出行（DFS) 构造出列（DFS) 计算目前的子矩阵的分值,- 12 -,暴力搜索程序模块,void w(int k) if(k=row+1) h(1);/进入列搜索 return; if(n-rk-1=row-k+1) for(int i=rk-1+1;i=n;i+) rk
8、=i; w(k+1); ,- 13 -,暴力搜索程序模块,void h(int g) if(g=col+1) int t=pd(); if(t=col-g+1) for(int i=cg-1+1;i=m;i+) cg=i; h(g+1); ,- 14 -,暴力搜索程序模块,int pd() int sum=0; for(int i=1;i=row;i+) for(int j=1;jcol;j+) sum+=abs(aricj-aricj+1); for(int j=1;j=col;j+) for(int i=1;irow;i+) sum+=abs(aricj-ari+1cj); return
9、sum; ,- 15 -,暴力搜索程序模块,int main() cinnmrowcol; for(int i=1;iaij; w(1); coutans; return 0; ,- 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
10、记录i行k列与j列之间的差值的绝对值 wmaxn/ j列各行之间的分数 vmaxnmaxn/ k,j两列之间的分数 fmaxnmaxn/i列，最后一列是j 的最小分数 且第i列是j,- 18 -,参考程序(DP部分),void dp() memset(w,0,sizeof(w); memset(v,0,sizeof(v); memset(f,127,sizeof(f); for(int j=1;j=m;j+) for(int i=2;i=row;i+) wj+=abs(arij-ari-1j); for(int j=1;j=m;j+) f1j=wj; for(int j=2;j=m;j+) for(int k=1;kj;k+) for(int i=1;i=m;i+) vkj+=vxrikj; for(int i=2;i=col;i+) for(int j=i;j=m;j+) for(int k=i-1;k=j-1;k+) fij=min(fij,fi-1k+vkj+wj); for(int i=col;i=m;i+) ans=min(ans,fcoli); ,BYE,The END,温馨提示： 本题解内的程序都已经AC，由于代码较长，可以查看CPP文件,
