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

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