资源描述：
《NOIP2014 普及组 解题报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、NOIP2014普及组解题报告ByyearwhkpǔjízǔjiětíbàoɡàoNOIP2014普及组解题报告Byyearwhk合肥市第四十五中学王翰坤2014.11（完整试题可点此下载）第1页共13页NOIP2014普及组解题报告Byyearwhk1.珠心算测试(count)【问题简述】已知一个正整数集合，集合中的数各不相同，求：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？【问题分析】历年普及组第一题总是很水，但今年的这一题的题意很多人理解错误，导致很多同学都只得了30分。他们错把把题意理解为：求有多少对数
2、的和正好是集合中的另一个数。如，对于集合{1,2,3,4,5}，题目要求的是3=1+2,4=2+2=1+3,5=1+4=2+3，共3个数．．；而按照错误的理解，求的便是1+2=3,1+3=4,1+4=5,2+3=5，共4对数．．。所以读题就显得多么重要！明确了题意，接下来设计算法。注意到“测验题给出的正整数大小不超过104”这个条件，我们可以采用模拟的办法。具体算法如下：①将每两个不同的数穷举相加求和，再将这个和打上标记；②扫描所有集合中的数，统计所有被打上标记的数的数量。简表：时间复杂度空间复杂度得分O(n2)O(max
3、{ai})（max{ai}是集合中最大的数）100这个方法和某年的普及组试题“明明的随机数”方法类似，能做到不遗漏、不重复。-代码见下页-第2页共13页NOIP2014普及组解题报告Byyearwhk【参考代码】Programcount;varn,i,j,ans:longint;b:array[0..20001]ofboolean;//注意用于打标记的b数组要开到2*max{ai}a:array[0..101]oflongint;Beginassign(input,'count.in');reset(input);assi
4、gn(output,'count.out');rewrite(output);readln(n);fori:=1tondoread(a[i]);fillchar(b,sizeof(b),false);fori:=1ton-1doforj:=i+1tondob[a[i]+a[j]]:=true;ans:=0;fori:=1tondoifb[a[i]]theninc(ans);writeln(ans);close(input);close(output)End.第3页共13页NOIP2014普及组解题报告Byyearwhk2.
5、比例简化(ratio)【问题简述】给出两个整数A、B，以及一个上限L，要求将A比B化简为A'比B'（A'和B'均不大于L，A'和B'互质，A'/B'≥A/B），使得A'/B'-A/B的值尽可能小。【问题分析】这题用于包装的背景很贴切——至少是有一定实用价值的。一道看似无从下手的题目，把它的包装皮撕开以后，发现又可以以“1≤L≤100”这个较小的数据范围作为突破口，枚举所有合法的A’和B’即可。具体算法如下：①从1~L分别枚举A’、B’；对于每一对A’、B’，判断是否满足“A'和B'互质且A'/B'≥A/B”，若满足，则②，
6、否则继续枚举；②判断A'/B'-A/B是否比当前差值小，若是，更新A’、B’和差值，否则①。简表:时间复杂度空间复杂度得分O(L2)O(1)100-代码见下页-第4页共13页NOIP2014普及组解题报告Byyearwhk【参考代码】Programratio;vara,b,l,i,j,x,y:longint;k,t,min:real;functiongcd(a,b:longint):longint;//欧几里得辗转相除，求最大公约数beginifamodb=0thenexit(b);gcd:=gcd(b,amodb)end
7、;Beginassign(input,'ratio.in');reset(input);assign(output,'ratio.out');rewrite(output);readln(a,b,l);t:=a/b;min:=1e+9;fori:=1toldoforj:=1toldoifgcd(i,j)=1thenbegin//也可以先对所有数对的互质情况打个表，但对于本题的数据范围没必要k:=i/j-t;if(k>=0)and(k<=min)thenbeginx:=i;y:=j;min:=x/y-tendend;writ
8、eln(x,'',y);close(input);close(output)End.第5页共13页NOIP2014普及组解题报告Byyearwhk3.螺旋矩阵(matrix)【问题简述】给出一个螺旋矩阵的大小n以及i和j，求该矩阵中第i行第j列的数。【问题分析】把这种小学僧题目放在第三题，实在不知道CC
