NOIP2014复赛普及组第一题题解

活动园地NOIP2014复赛普及组第一题题解原题全国信息学眞林匹克联赛(NOIP20L4)笈赛 普艮组1-珠心算测验(count*cpp/a/pas}【问题描述】珠心算是一种通过在脑中模拟算盘变化宋完成快速运算的一种计算技术U珠心-算训练T既能够开发智力’又能够再日常生活带来很蚩便利「因而在很參学校得到普及.某学控的珠心算老师采用一种快速考察珠心算加法能力的测验方法■他随机生成一个正整数集合.集合屮的数齐不相同.然后要求学主回答：具中有多少亍数.恰好等于集合屮另外两个(不同的)数之和？豈近老师出了一些测验融‘请祢帮忙求出答案。【输入】输入文件名再count.in^输入共两行‘第一行包含一个整数叭表示测试题中給出的正整数亍数口第.：行有丹个正整数•毎两个正整数之间用一个空格隔开■舂示测试题屮蛤出的正整【输出】输出文杵名为eount.cut^输出共一行‘包含一个整数‘表示测验题答案。【输入输出样例】Qcun七■inccun七■out421234【样例说明】由］+2=3,1+3^,故满足测试要求的答案为2.注意，加数和被加数必■幼是集合中的两个不同的数。【数掘说明】时于100%的数摇，孑鱼h鱼100.测验题给出的正整数大小不超过10,000.programcount;programcount;vara:array[0..101]oflongint;b:array[0..5000]oflongint;n,ans,i,j,k:longint;beginassign(input,'count.in');reset(input);assign(output,'count.out');rewrite(output);readln(n);一、 题目简化：求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]五、 程序设计：read(a[i]);fillchar(b,sizeof(b),0);**下面开始步骤1：a中的数两两相加放在b中**k:=1;fori:=1ton-1doforj:=i+1tondobeginb[k]:=a[i]+a[j];inc(k);fori:=1tondo**下面开始步骤2fori:=1tondo**下面开始步骤2：筛掉b中的重复数据：**fori:=复数据：**fori:=1to(k-1)-1doforj:=i+1tok-1dobegin

ifb[i]:=b[j]then

b[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.六、时间复杂度分析：三个步骤采用了三个双重循环，每个双重循环运行约N•兰ii=1次，若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这样，上面的第二步骤就省去了……优化后的程序：鲁弓：FreePascalIDEFileEditSearchRunCompileDebugToolsOptionsWindou=[t] D：\FPC\2™4.0\binVi386-win32\count.paspposrramcount;uara:array[..jJoflonglnt；b:array[ •，- ]誦芦longint；i,j>k,n>ans：longint；begink：=；ans：=；readln<n>；fillchar<a,siEeof<a>,>；fillchap<b,siHeof<b>,>;fi：ri；=tondoread<ati]>；fori：= t(.n-forj；=i1-tondobeginb[a[i]+a[j]]：>a[i]+a[j]；inc<k>；end；fori：:=tondofor=tok-dobeginiftheninc<ans>；end；write<ans>；endc:CompiliiMainfile:D：\-.Xj.386-win32\count-：pasDeme.Target:Uin32for1386Linenum