Noip2014解题报告.pdf

Noip2014普及组解题报告 --slzxxjd ZJ 注：数据分析中的数据均为 评测结果 1. 珠心算测验 (count.cpp/c/pas) 【问题描述】 珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技 。珠 心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校 得到普及。 某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机 生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个 数，恰好等于集合中另外两个（不同的）数之和？ 最近老师出了一些测验题，请你帮忙求出答案。 【输入】 输入文件名为count.in。 输入共两行，第一行包含一个整数n，表示测试题中给出的正整数个数。 第二行有n个正整数，每两个正整数之间用一个空格隔开，表示测试题中给 出的正整数。 【输出】 输出文件名为count.out。 输出共一行，包含一个整数，表示测验题答案。 【输入输出样例】 count.in count.out 4 2 1 2 3 4 【样例说明】 由1+2=3，1+3=4，故满足测试要求的答案为2。注意，加数和被加数必须是 集合中的 两个不同的数。 【数据说明】 对于100%的数据，3≤n≤100，测验题给出的正整数大小不超过10,000。 【题目分析】 对于一个正整数集合，求出这个正整数集合中有多少个数恰好等于集合中另 外两个（不同的）数之和。 【算法分析】 继承了历年Noip 的传统，第一题都是模拟题。这道题目的算法不难发现。 2 我们可以用O （n）的方法确定这个正整数集合中的其中一个数，然后用O （n ） 算法找出另外两个不同的数 （注意了，题目强调了不同的！尽管这个细节不注意 连连样例都不会过的~）。非常值得注意的是，很多同学这道简单的模拟题仅仅 只拿了30分，问题出在审题不清，题目叙述中要求求的是有几个数恰好等于集 合中另外两个数之和，也就是说如果一个数恰好等于集合中不同的两（或者两组 以上）组数，那么这样的只能算作一种。 【Code】 01 var 02 i,j,k,m,n,s,t,ans:longint; 03 a:array[1..1000] of longint; 04 begin 05 assign(input,count.in); 06 assign(output,count.ou ); 07 reset(input); 08 rewrite(output); 09 read(n); 10 for i:=1 to n do 11 read(a[i]); 12 ans:=0; 13 for i:=1 to n do 14 begin 15 t:=0; 16 for j:=1 to n do 17 begin 18 for k:=1 to n do 19 if (ij)and (jk)and (ik) then 20 if a[j]+a[k]=a[i] then begin t:=1;break; end; 21 if t=1 then break; 22 end; 23 if t=1 then inc(ans); 24 end; 25 writeln(ans); 26