NOIP2022复赛普及组第一题题解.docx

本文格式为Word版，下载可任意编辑NOIP2022复赛普及组第一题题解 活动园地 NOIP2022复赛普及组第一题题解 原题 一、 题目简化：求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 这样，上面的其次步骤就省去了…… 优化后的程序： 输入数据运行一下验证程序： 假设你还有更好的算法，请你报告我，以及，其它人…… — 4 —。