NOIP2014复赛普及组第一题题解

活动园地

NOIP2014复赛普及组第一题题解

原题

一、 题目简化：求N个正数中有多少个数是这些数中其它两个数的和。

3<=N<=100; 每个正整数M：1<=M<=10000;

二、 过程分析：试题显然可以分成三个步骤求解：1、先求出N个数中每两个数的

和；2、判断这些和中有没有重复，重复的数只留下一个；3、N个数中的每一个数都与这些和比较，若相等些记下，比较完成，即得其解。

三、 算法与策略：三个步骤都采用一一列举所有可能的方法，是典型的枚举。 四、 程序设计思路：1、一维数组A存放N个数，一维数组B存放两两相加的和；

求和、判断重复、比较两数是否相等，都采用两重循环，i 控制外循环，j 控制内循环，k表示数组B的下标变化，ans表示题目答案。

数组a最多100个元素，考虑到用循环，为防止下标越界，可适当把数组开大一些，a[0..101]；数组b中元素数是N个数两个数两两相加的和的个数，由于N最大是100，所以和的个数最多是1+2+3+……99＝4950个，则b[0..5000] 五、程序设计： program count; var

a:array[0..101] of longint; b:array[0..5000] of longint; n,ans,i,j,k:longint; begin

assign(input,'count.in'); reset(input);

assign(output,'count.out'); rewrite(output); readln(n); for i:=1 to n do

read(a[i]); fillchar(b,sizeof(b),0);

**下面开始步骤1：a中的数两两相加放在b中** k:=1;

for i:=1 to n-1 do for j:=i+1 to n do begin

b[k]:=a[i]+a[j]; inc(k); end;

**下面开始步骤2：筛掉b中的重

复数据：**

for i:= 1 to (k-1)-1 do for j:=i+1 to k-1 do begin if b[i]:=b[j] then b[j]:=0; end;

**下面开始步骤3：比较a数组中有多少个数与b数组中的数相等：** ans:=0; for i:=1 to n do

for j:=1 to k-1 do begin if (a[i]=b[j]) then inc(ans); end;

**比较结束，结果已得出，下面输出结果，关闭文件，结束程序** write(ans); close(input) close(output); end.

n?1i?1六、时间复杂度分析：三个步骤采用了三个双重循环，每个双重循环运行约N·?i 次，若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＝2500 则这个结果放在B[2500]中，即：B[2500]：＝2500；问：如果有2+6＝8，这个结果放在哪里？这样处理，B数组中还有重复数据吗？答案是：肯定有，那些重复的都是些啥？答：0

这样，上面的第二步骤就省去了…… 优化后的程序：

输入数据运行一下验证程序：

如果你还有更好的算法，请你告诉我，以及，其它人……