noip2014复赛普及组第一题题解

《noip2014复赛普及组第一题题解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、活动园地NOIP2014复赛普及组第一题题解原题一、题目简化：求N个正数中有多少个数是这些数中其它两个数的和。3<=N<=100;每个正整数M：1<=M<=10000;二、过程分析：试题显然可以分成三个步骤求解：1、先求出N个数中每两个数的和；2、判断这些和中有没有重复，重复的数只留下一个；3、N个数中的每一个数都与这些和比较，若相等些记下，比较完成，即得其解。三、算法与策略：三个步骤都采用一一列举所有可能的方法，是典型的枚举。四、程序设计思路：1、一维数组A存放N个数，一维数组B存放两两相加的和；求和、判断重复、比较

2、两数是否相等，都采用两重循环，i控制外循环，j控制内循环，k表示数组B的下标变化，ans表示题目答案。数组a最多100个元素，考虑到用循环，为防止下标越界，可适当把数组开大一些，a[0..101]；数组b中元素数是N个数两个数两两相加的和的个数，由于N最大是100，所以和的个数最多是1+2+3+……99＝4950个，则b[0..5000]五、程序设计：programcount;vara:array[0..101]oflongint;b:array[0..5000]oflongint;n,ans,i,j,k:longin

3、t;beginassign(input,'count.in');reset(input);assign(output,'count.out');rewrite(output);readln(n);fori:=1tondoread(a[i]);fillchar(b,sizeof(b),0);**下面开始步骤1：a中的数两两相加放在b中**k:=1;fori:=1ton-1doforj:=i+1tondobeginb[k]:=a[i]+a[j];inc(k);end;**下面开始步骤2：筛掉b中的重复数据：**fori:=

4、1to(k-1)-1doforj:=i+1tok-1dobeginifb[i]:=b[j]thenb[j]:=0;end;**下面开始步骤3：比较a数组中有多少个数与b数组中的数相等：**ans:=0;fori:=1tondoforj:=1tok-1dobeginif(a[i]=b[j])theninc(ans);end;**比较结束，结果已得出，下面输出结果，关闭文件，结束程序**write(ans);close(input)close(output);end.六、时间复杂度分析：三个步骤采用了三个双重循环，每个双重

5、循环运行约N·次，若N＝100，则整个程序运行约150万次操作，T（N）＝0（N3）理论上讲，还可以忍受。第二步的任务是排除B中的重复数值，以免第三步统计时重复计算，使结果不正确。从原题提供的数据来看，N个正整数中每个都不超过10000，这就是说，B中的最大数值就是20000，开一个[1..20000]的数组，A中两个数的和等于几，就把这个数放在B中的第几个位置上，即：让B数组的下标跟A中这两个数的和相同。写到这里，如果你还不明白，那，那算我没说明白，举个粟子捋一捋：3+5＝8，则B[8]：＝8；1500+1000＝2

6、500则这个结果放在B[2500]中，即：B[2500]：＝2500；问：如果有2+6＝8，这个结果放在哪里？这样处理，B数组中还有重复数据吗？答案是：肯定有，那些重复的都是些啥？答：0这样，上面的第二步骤就省去了……优化后的程序：输入数据运行一下验证程序：如果你还有更好的算法，请你告诉我，以及，其它人……