NOIP2014复赛普及组第一题题解.doc

活动园地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个元素，考虑到用循环，为防止下标越界，可适当把数组开大一些，a0.101；数组b中元素数是N个数两个数两两相加的和的个数，由于N最大是100，所以和的个数最多是1+2+3+994950个，则b0.5000五、程序设计：program count; var a:array0.101 of longint; b:array0.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(ai); 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 bk:=ai+aj; inc(k); end; *下面开始步骤2：筛掉b中的重复数据：* for i:= 1 to (k-1)-1 do for j:=i+1 to k-1 do begin if bi:=bj then bj:=0; end; *下面开始步骤3：比较a数组中有多少个数与b数组中的数相等：* ans:=0; for i:=1 to n do for j:=1 to k-1 do begin if (ai=bj) then inc(ans); end; *比较结束，结果已得出，下面输出结果，关闭文件，结束程序* write(ans); close(input) close(output); end.六、时间复杂度分析：三个步骤采用了三个双重循环，每个双重循环运行约N 次，若N100，则整个程序运行约150万次操作，T（N）0（N3）理论上讲，还可以忍受。第二步的任务是排除B中的重复数值，以免第三步统计时重复计算，使结果不正确。从原题提供的数据来看，N个正整数中每个都不超过10000，这就是说，B中的最大数值就是20000，开一个1.20000的数组，A中两个数的和等于几，就把这个数放在B中的第几个位置上，即：让B数组的下标跟A中这两个数的和相同。写到这里，如果你还不明白，那，那算我没说明白，举个粟子捋一捋：3+58，则B8：8；1500+10002500 则这个结果放在B2500中，即：B2500：2500；问：如果有2+68，这个结果放在哪里？这样处理，B数组中还有重复数据吗？答案是：肯