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

2017.07.28试题分析NOIP2014普及组复赛题解NOIP2014普及组C++-2-第1题“珠心算测验”简述某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？直接三重循环穷举外层循环枚举和，两个内层循环分别枚举两个加数，如果有两个数之和对应外层循环的枚举值，退出两个内层循环注意：找到满足等式的必须退出两个内循环。注意看清题意：其中有多少个数，恰好等于集合中另外两个(不同的)数之和。-3-参考程序C++#includeiostreamusingnamespacestd;intmain(){intn,i,j,k,ans=0;inta[105];cinn;for(i=1;i=n;i++)cina[i];for(i=1;i=n;i++)//和为A[i]{boolf=false;for(j=1;jn;j++){for(k=j+1;k=n;k++)if(a[i]==a[j]+a[k]){f=true;ans++;break;}if(f)break;}}coutans;return0;}-4-第2题“比例简化”简述在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某一观点表示支持的有1498人，反对的有902人，那么赞同与反对的比例可以简单的记为1498: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’判断互质，最大公约数为1判断A’和B’最小A’*ansB=ansA*B’找到更小的A’和B’设置为ansA和ansB-6-主程序#includeiostreamusingnamespacestd;intgcd(intx,inty){intt;t=x%y;if(t==0)returny;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列）出发，初始时向右移动；如果前方是未曾经过的格子，则继续前进，否则右转；重复上述操作直至经过矩阵中所有格子。根据经过顺序，在格子中依次填入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-参考程序#includeiostreamusingnamespacestd;intmain(){longintn,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;break;}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-暴力搜索程序模块voidw(intk){if(k==row+1){h(1);//进入列搜索return;}if(n-r[k-1]=row-k+1){for(inti=r[k-1]+1;i=n;i++){r[k]=i;w(k+1);}}}-13-暴力搜索程序模块voidh(intg){if(g==col+1){intt=pd();if(tans)ans=t;return;}if(m-c[g-1]=col-g+1){for(inti=c[g-1]+1;i=m;i++){c[g]=i;h(g+1);}}}-14-暴力搜索程序模块intpd(){intsum=0;for(inti=1;i=row;i++)for(intj=1;jcol;j++)sum+=abs(a[r[i]][c[j]]-a[r[i]][c[j+1]]);for(intj=1;j=col;j++)for(inti=1;irow;i++)sum+=abs(a[r[i]][c[j]]-a[r[i+1]][c[j]]);returnsum;}-15-暴力搜索程序模块intmain(){cinnmrowcol;for(inti=1;i=n;i++)for(intj=1;j=m;j++)cina[i][j];w(1);coutans;return0;}-16-确定解题思路AC思路：搜索+DP枚举出选那些行算出j列各行之间的分数w[j]，k,j两列之间的分数v[k][j]。f[i][j]表示已经选了i(数量)列，最后一列是j(下标)的最小分数且第i列是j状态转移方程：f[i][j]=min(f[i-1][k]+w[j]+v[k][j])。-17-数据结构a[maxn][maxn]//存放原数据n行m列的矩阵r[maxn]//c存放枚举出的行号vx[maxn][maxn][maxn]//vx[I][K][J]记录i行k列与j列之间的差值的绝对值w[maxn]//j列各行之间的分数v[maxn][maxn]//k,j两列之间的分数f[maxn][maxn]//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++)w[j]+=abs(a[r[i]][j]-a[r[i-1]][j]);for(intj=1;j=m;j++)f[1][j]=w[j];for(intj=2;j=m;j++)for(intk=1;kj;k++)for(inti=1;i=m;i++)v[k][j]+=vx[r[i]][k][j];for(inti=2;i=col;i++)for(intj=i;j=m;j++)for(intk=i-1;k=j-1;k++)f[i][j]=min(f[i][j],f[i-1][k]+v[k][j]+w[j]);for(inti=col;i=m;i++)ans=min(ans,f[col][i]);}2017.07.28试题分析BYETheEND温馨提示：本题解内的程序都已经AC，由于代码较长，可以查看CPP文件