NOIP2014復(fù)賽普及組第一題題解

活動園地NOIP2014復(fù)賽普及組第一題題解原題全國信息學(xué)眞林匹克聯(lián)賽(NOIP20L4)笈賽 普艮組1-珠心算測驗(count*cpp/a/pas}【問題描述】珠心算是一種通過在腦中模擬算盤變化宋完成快速運算的一種計算技術(shù)U珠心-算訓(xùn)練T既能夠開發(fā)智力’又能夠再日常生活帶來很蚩便利「因而在很參學(xué)校得到普及.某學(xué)控的珠心算老師采用一種快速考察珠心算加法能力的測驗方法■他隨機(jī)生成一個正整數(shù)集合.集合屮的數(shù)齊不相同.然后要求學(xué)主回答：具中有多少亍數(shù).恰好等于集合屮另外兩個(不同的)數(shù)之和？豈近老師出了一些測驗融‘請禰幫忙求出答案?！据斎搿枯斎胛募賑ount.in^輸入共兩行‘第一行包含一個整數(shù)叭表示測試題中給出的正整數(shù)亍數(shù)口第.：行有丹個正整數(shù)?毎兩個正整數(shù)之間用一個空格隔開■舂示測試題屮蛤出的正整【輸出】輸出文杵名為eount.cut^輸出共一行‘包含一個整數(shù)‘表示測驗題答案?！据斎胼敵鰳永縌cun七■inccun七■out421234【樣例說明】由］+2=3,1+3^,故滿足測試要求的答案為2.注意，加數(shù)和被加數(shù)必■幼是集合中的兩個不同的數(shù)?！緮?shù)掘說明】時于100%的數(shù)搖，孑魚h魚100.測驗題給出的正整數(shù)大小不超過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個正數(shù)中有多少個數(shù)是這些數(shù)中其它兩個數(shù)的和。3<=N<=100;每個正整數(shù)M：1<=M<=10000;二、 過程分析：試題顯然可以分成三個步驟求解：1、先求出N個數(shù)中每兩個數(shù)的和；2、判斷這些和中有沒有重復(fù)，重復(fù)的數(shù)只留下一個；3、N個數(shù)中的每一個數(shù)都與這些和比較，若相等些記下，比較完成，即得其解。三、 算法與策略：三個步驟都采用一一列舉所有可能的方法，是典型的枚舉。四、 程序設(shè)計思路：1、一維數(shù)組A存放N個數(shù)，一維數(shù)組B存放兩兩相加的和；求和、判斷重復(fù)、比較兩數(shù)是否相等，都采用兩重循環(huán)，i控制外循環(huán)，j控制內(nèi)循環(huán)，k表示數(shù)組B的下標(biāo)變化，ans表示題目答案。數(shù)組a最多100個元素，考慮到用循環(huán)，為防止下標(biāo)越界，可適當(dāng)把數(shù)組開大一些，a[0??101]；數(shù)組b中元素數(shù)是N個數(shù)兩個數(shù)兩兩相加的和的個數(shù)，由于N最大是100,所以和的個數(shù)最多是1+2+3+……99=4950個,則b[0..5000]五、 程序設(shè)計：read(a[i]);fillchar(b,sizeof(b),0);**下面開始步驟1：a中的數(shù)兩兩相加放在b中**k:=1;fori:=1ton-1doforj:=i+1tondobeginb[k]:=a[i]+a[j];inc(k);fori:=1tondo**下面開始步驟2fori:=1tondo**下面開始步驟2：篩掉b中的重復(fù)數(shù)據(jù)：**fori:=復(fù)數(shù)據(jù)：**fori:=1to(k-1)-1doforj:=i+1tok-1dobegin

ifb[i]:=b[j]then

b[j]:=0;end;**下面開始步驟3：比較a數(shù)組中有多少個數(shù)與b數(shù)組中的數(shù)相等：**ans:=0;fori:=1tondoforj:=1tok-1dobeginif(a[i]=b[j])theninc(ans);end;**比較結(jié)束，結(jié)果已得出，下面輸出結(jié)果，關(guān)閉文件，結(jié)束程序**write(ans);close(input)close(output);end.六、時間復(fù)雜度分析：三個步驟采用了三個雙重循環(huán)，每個雙重循環(huán)運行約N?蘭ii=1次，若N=100,則整個程序運行約150萬次操作，T(N)=0(N3)理論上講，還可以忍受。第二步的任務(wù)是排除B中的重復(fù)數(shù)值，以免第三步統(tǒng)計時重復(fù)計算，使結(jié)果不正確。從原題提供的數(shù)據(jù)來看，N個正整數(shù)中每個都不超過10000，這就是說，B中的最大數(shù)值就是20000，開一個［1..20000］的數(shù)組，A中兩個數(shù)的和等于幾，就把這個數(shù)放在B中的第幾個位置上，即：讓B數(shù)組的下標(biāo)跟A中這兩個數(shù)的和相同。寫到這里，如果你還不明白，那，那算我沒說明白，舉個粟子捋一捋：3+5=8，則B［8］：=8；1500+1000=2500則這個結(jié)果放在B［2500］中，即：B［2500］：=2500；問：如果有2+6=8，這個結(jié)果放在哪里？這樣處理，B數(shù)組中還有重復(fù)數(shù)據(jù)嗎？答案是：肯定有，那些重復(fù)的都是些啥？答：0這樣，上面的第二步驟就省去了……優(yōu)化后的程序：魯弓：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