NOIP初賽試題提高組C語(yǔ)言

1、NOIP初賽試題（提高組C語(yǔ)言）第十屆（2004）三.問題求解（共2題，每題5分，共計(jì)10分）1.75名兒童到游樂場(chǎng)去玩。他們可以騎旋轉(zhuǎn)木馬，坐滑行鐵道，乘宇宙飛船。已知其中20人這三種東西都玩過，55人至少玩過其中的兩種。若每樣乘坐一次的費(fèi)用是5元，游樂場(chǎng)總共收入700，可知有名兒童沒有玩過其中任何一種。分析與解：已知總?cè)藬?shù)為75,總金額是700，玩3項(xiàng)的人數(shù)是20,花費(fèi)的金額是5*3*20=300，玩2項(xiàng)的人數(shù)是55-20=35，花費(fèi)的金額是5*2*35=350，剩余金額是700-300-350=50，只能玩50/5=10項(xiàng)次,即玩1項(xiàng)的人數(shù)是10,所以玩0項(xiàng)的人數(shù)是：75-20-35-1

2、0=10總共玩3項(xiàng)玩2項(xiàng)玩1項(xiàng)玩0項(xiàng)人數(shù)752035？金額70030035002.已知a,b,c,d,e,f,g七個(gè)人中，a會(huì)講英語(yǔ)；b會(huì)講英語(yǔ)和漢語(yǔ)；c會(huì)講英語(yǔ)、意大利語(yǔ)和俄語(yǔ)；d會(huì)講漢語(yǔ)和日語(yǔ)；e會(huì)講意大利語(yǔ)和德語(yǔ)；f會(huì)講俄語(yǔ)、日語(yǔ)和法語(yǔ)；g會(huì)講德語(yǔ)和法語(yǔ)。能否將他們的座位安排在圓桌旁，使得每個(gè)人都能與他身邊的人交談？如果可以，請(qǐng)以“ab”開頭寫出你的安排方案：a-b-d-yg-密答：abdfgec第十一屆（2005）三.問題求解（請(qǐng)?jiān)诳崭裉幪钌洗鸢?，每?分，共計(jì)10分）1.將數(shù)組32,74,25,53,28,43,86,47中的元素按從小到大的順序排列，每次可以交換任意兩個(gè)元素，最少需

3、要交換次。32,74,25,53,28,43,86,4725,74,32,53,28,43,86,4725,28,32,53,74,43,86,4725,28,32,43,74,53,86,4725,28,32,43,47,53,86,7425,28,32,43,47,53,74,862.取火柴游戲的規(guī)則如下：一堆火柴有N根，A、B兩人輪流取出。每人每次可以取1根或2根，最先沒有火柴可取的人為敗方，另一方為勝方。如果先取者有必勝策略則記為1，先取者沒有必勝策略記為0。當(dāng)N分別為100，200，300，400，500時(shí)，先取者有無必勝策略的標(biāo)記順序?yàn)椋ɑ卮饝?yīng)為一個(gè)由0和/或1組成的字符串）。分析

4、與解：當(dāng)火柴的根數(shù)為3或3的整數(shù)倍時(shí)，先取者沒有必勝的策略；而當(dāng)火柴的根數(shù)不為3的整數(shù)倍時(shí)，先取者有必勝的策略：取后使得剩余火柴的根數(shù)為3的整數(shù)倍。所以答案為11011相似的游戲：A、B兩人輪流往同一儲(chǔ)蓄罐存錢并記錄每次存入的金額，每人每次可存入的金額為1元至5元間的任一整數(shù)（包括1和5）,誰(shuí)某次存完錢后使得儲(chǔ)蓄罐里的總金額大于等于100即獲勝利（獲得儲(chǔ)蓄罐里所有的存錢的獎(jiǎng)勵(lì)）。若讓你參加該游戲并為第一個(gè)存錢者，你有必勝的策略嗎？第十二屆（2006）三.問題求解（共2題，每題5分，共計(jì)10分）1將2006個(gè)人分成若干不相交的子集，每個(gè)子集至少有3個(gè)人，并且：（1）在每個(gè)子集中，沒有人認(rèn)識(shí)該子集

5、的所有人。（2）同一子集的任何3個(gè)人中，至少有2個(gè)人互不認(rèn)識(shí)。（3）對(duì)同一子集中任何2個(gè)不相識(shí)的人，在該子集中恰好只有1個(gè)人認(rèn)識(shí)這兩個(gè)人。則滿足上述條件的子集最多能有個(gè)？分析：要使子集數(shù)最多，每一子集的人數(shù)應(yīng)最少。每一子集的人數(shù)為3，不符合要求，為4也不符合要求，為5可符合要求。2將邊長(zhǎng)為n的正三角形每邊n等分，過每個(gè)分點(diǎn)分別做另外兩邊的平行線，得到若干個(gè)正三角形，我們稱為小三角形。正三角形的一條通路是一條連續(xù)的折線，起點(diǎn)是最上面的一個(gè)小三角形，終點(diǎn)是最下面一行位于中間的小三角形。在通路中，只允許由一個(gè)小三角形走到另一個(gè)與其有公共邊的且位于同一行或下一行的小三角形，并且每個(gè)小三角形不能經(jīng)過兩次

6、或兩次以上（圖中是n=5時(shí)一條通路的例子）。設(shè)n=10,則該正三角形的不同的通路的總數(shù)為。分析與解：如果n=2，存在的不同的通路總數(shù)為1如果n=3，存在的不同的通路總數(shù)為2=1*2=2!如果n=4,存在的不同的通路總數(shù)為6=1*2*3=3！如果n=5,存在的不同的通路總數(shù)為24=1*2*3*4=4！如果n=10，存在的不同的通路總數(shù)為9！第十三屆（2007）三問題求解(共2題，每題5分，共計(jì)10分)給定n個(gè)有標(biāo)號(hào)的球，標(biāo)號(hào)依次為1,2,，n。將這n個(gè)球放入r個(gè)相同的盒子里，不允許有空盒，其不同放置方法的總數(shù)記為S(n,r)。例如，S(4,2)=7，這7種不同的放置方法依次為(1),(234),

7、(2),(134),(3),(124),(4),(123),(12),(34),(13),(24),(14),(23)。當(dāng)n=7,r=4時(shí)，S(7,4)=分析與解：方法一：4個(gè)盒子放7個(gè)球的情況依每個(gè)盒子所放球的個(gè)數(shù)不同可分為以下情形：4,1，1，1；共有C(7，4)=7*6*5*4/(4*3*2*1)=35種3,2，1，1；共有C(7，3)*C(4，2)=35*6=210種2,2，2，1。共有C(7，2)*C(5，2)*C(3，2)/A(3，3)=21*10*3/6=105種共計(jì)：35+210+105=350種方法二：S(n,r)=S(n-1,r)Xr+S(n-1,r-1)因?yàn)椋嘁粋€(gè)球的放

8、法：若空盒沒有增多，則往r個(gè)盒子的任何一個(gè)盒子放入該球都是一種放法。所以共有S(n-1,r)Xr種放法，若空盒有增加1個(gè)，則增加的球只能放在該盒，放法有S(n-1,r-1)種。另：S(n,n)=1；S(n,1)=1,依S(n,r)=S(n-1,r)Xr+S(n-1,r-1)填下表：123111121314456711111N個(gè)人在操場(chǎng)里圍成一圈，將這N個(gè)人按順時(shí)針方向從1到N編號(hào)，然后，從第一個(gè)人起，每隔一個(gè)人讓下一個(gè)人離開操場(chǎng)，顯然，第一輪過后，具有偶數(shù)編號(hào)的人都離開了操場(chǎng)。依次做下去，直到操場(chǎng)只剩下一個(gè)人，記這個(gè)人的編號(hào)為J(N)，例如，J(5)=3，J(10)=5，等等。則J(400)=

9、。提示：對(duì)N=2m+r進(jìn)行分析，其中0rWE(G),則u在線性序列中出現(xiàn)在v之前，這樣的線性序列成為拓?fù)湫蛄?。如下的有向無環(huán)圖，對(duì)其頂點(diǎn)作拓?fù)渑判颍瑒t所有可能的拓?fù)湫蛄械膫€(gè)數(shù)為。由AOV網(wǎng)構(gòu)造拓?fù)湫蛄械耐負(fù)渑判蛩惴ㄖ饕茄h(huán)執(zhí)行以下兩步，直到不存在入度為0的頂點(diǎn)為止。選擇一個(gè)入度為0的頂點(diǎn)并輸出之；從網(wǎng)中刪除此頂點(diǎn)及所有出邊循環(huán)結(jié)束后，若輸出的頂點(diǎn)數(shù)小于網(wǎng)中的頂點(diǎn)數(shù)，則輸出“有回路”信息，否則輸出的頂點(diǎn)序列就是-種拓?fù)湫蛄小?.某個(gè)國(guó)家的錢幣面值有1,7,72,73共計(jì)四種，如果要用現(xiàn)金付清10015元的貨物，假設(shè)買賣雙方各種錢幣的數(shù)量無限且允許找零，那么交易過程中至少需要流通張錢幣。(答案:

10、1、432；2、35)第十六屆（2010）三、問題求解1.LZW編碼是一種自適應(yīng)詞典編碼。在編碼的過程中，開始時(shí)只有一部基礎(chǔ)構(gòu)造元素的編碼詞典，如果在編碼的過程中遇到一個(gè)新的詞條，則該詞條及一個(gè)新的編碼會(huì)被追加到詞典中，并用于后繼信息的編碼。舉例說明，考慮一個(gè)待編碼的信息串：“xyxyyyyxyx”。初始詞典只有3個(gè)條目，第一個(gè)為x,編碼為1;第二個(gè)為y，編碼為2；第三個(gè)為空格，編碼為3；于是串“xyx”的編碼為1-2T（其中-為編碼分隔符），加上后面的一個(gè)空格就是1-2-1-3。但由于有了一個(gè)空格，我們就知道前面的“xyx”是一個(gè)單詞，而由于該單詞沒有在詞典中，我們就可以自適應(yīng)的把這個(gè)詞條添

11、加到詞典里，編碼為4，然后按照新的詞典對(duì)后繼信息進(jìn)行編碼，以此類推。于是，最后得到編碼：1-2-1-3-2-2-3-5-3-4。我們可以看到，信息被壓縮了。壓縮好的信息傳遞到接受方，接收方也只要根據(jù)基礎(chǔ)詞典就可以完成對(duì)該序列的完全恢復(fù)。解碼過程是編碼過程的逆操作?，F(xiàn)在已知初始詞典的3個(gè)條目如上述，接收端收到的編碼信息為2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6，則解碼后的信息串是:“yyxyxxyyxyxyxxxxyx”。無向圖G有7個(gè)頂點(diǎn)，若不存在奇數(shù)條邊構(gòu)成的簡(jiǎn)單回路，則它至多有_12_條邊。記T為一隊(duì)列，初始時(shí)為空，現(xiàn)有n個(gè)總和不超過32的正整數(shù)依次入隊(duì)。如果無論

12、這些數(shù)具體為何值，都能找到一種出隊(duì)的方式，使得存在某個(gè)時(shí)刻隊(duì)列T中的數(shù)之和恰好為9,那么n的最小值是_18。本題可用抽屜原理求解。設(shè)ai為各正整數(shù)值，則T的隊(duì)列順序?yàn)閍1,a2,a3an,設(shè)bi為前i項(xiàng)數(shù)之和，則bO=O,b1=a1，b2=a1+a2，b3=a1+a2+a3。如隊(duì)列T中的數(shù)之和恰好為9,實(shí)際上即是找到某個(gè)bj和bi，使得bj-bi=9。由題意可知bi取值范圍為1-32,現(xiàn)將這32個(gè)數(shù)構(gòu)造為集合1,10,2,11,8,17,18,27,19,28,.,23,32,24,25,26,這17個(gè)集合中的任一個(gè)集合不能包含兩個(gè)或兩個(gè)以上的，否則它們的差為9。例如設(shè)n=17時(shí)，隊(duì)列T為11

13、1111111011111111，即b1=1,b2=2,.b8=8,b9=18,b10=19,b1仁20b17=26,它們中沒有任意兩個(gè)數(shù)是在同一集合內(nèi)的，所以不存在數(shù)之和恰好等于9。故根據(jù)抽屜原理可得，當(dāng)n=18時(shí)，至少存在兩個(gè)在同一個(gè)集合，即它們的差為9。因此，答案為n=18。第十七屆（2011，1.平面圖是可以畫在平面上，且它的邊僅在頂點(diǎn)上才能相交的簡(jiǎn)單無向圖。4個(gè)頂點(diǎn)的平面圖至多有6跳邊，如右圖所示。那么，5個(gè)頂點(diǎn)的平面圖至多有條邊。2.定義一種字符串操作，一次可以將其中一個(gè)元素一道任意位置。距離說明，對(duì)于字符串“BCA”，可以將A移到B之前，變成字符串“ABC”，如果要將字符串”DA

14、CHEBGIF”變成”ABCDEFGHI”，最少需要4次操作。第十八屆（2012）三、問題求解（共2題，每題5分，共計(jì)10分）1.本題中，我們約定布爾表達(dá)式只能包含p,q,r三個(gè)布爾變量，以及“與“3）、”或“（v）、”非“（）三種布爾運(yùn)算。如果無論p,q,r如何取值，兩個(gè)布爾表達(dá)式的值總是相同，則稱它們等價(jià)。例如，（pVq）Vr和pV（qVr）等價(jià)，pVp和qVq也等價(jià)，而pVq和pAq不等價(jià)。那么，兩兩不等價(jià)的布爾表達(dá)式最多有個(gè)。解答：對(duì)于p、q、r三個(gè)變量，每個(gè)變量可取0,1兩種取值，共有8種組合。對(duì)于每種組合，代入表達(dá)式只有0和1兩種答案。因此兩兩不等價(jià)的表達(dá)式只有2八8=256種。2

15、.對(duì)于一棵二叉樹，獨(dú)立集是指兩兩互不相鄰的節(jié)點(diǎn)構(gòu)成的集合。例如圖1有5個(gè)不同的獨(dú)立集（1個(gè)雙點(diǎn)集合，3個(gè)單點(diǎn)集合，1個(gè)空集），圖2有14個(gè)不同的獨(dú)立集，那么圖3有個(gè)不同的獨(dú)立集。答案：1、256；2、5536）解答：設(shè)m(i)為以i個(gè)為根結(jié)點(diǎn)的樹的獨(dú)立集總個(gè)數(shù)f(i)為選i的總個(gè)數(shù)g(i)表示不選i的總個(gè)數(shù)，顯然有m(i)=f(i)+g(i)對(duì)于二叉樹，如果根節(jié)點(diǎn)選，則兒子節(jié)點(diǎn)不能選，有f(i)=g(left_childi)*g(right_childi)如果根節(jié)點(diǎn)不選，則解與根節(jié)點(diǎn)無關(guān)，直接為左右兒子的解相乘，有g(shù)(i)=m(left_childi)*m(right_childi)具體用動(dòng)態(tài)

16、規(guī)劃求解如下(計(jì)算的時(shí)候是從下往上算，這里設(shè)樹的節(jié)點(diǎn)總數(shù)為根節(jié)點(diǎn)編號(hào))，顯然該題就是求m(17)，m(17)=f(17)+g(17)=1936+3600=5536f(17)=g(8)*g(8)=44*44=1936g(17)=m(8)*m(8)=60*60=3600m(8)=f(8)+g(8)=16+44=60f(8)=g(1)*g(6)=1*16=16g(8)=m(1)*m(6)=2*22=44m(6)=f(6)+g(6)=6+16=22f(6)=g(1)*g(4)=1*6=6g(6)=m(1)*m(4)=2*8=16m(4)=f(4)+g(4)=2+6=8f(4)=g(1)*g(2)=1*

17、2=2g(4)=m(1)*m(2)=2*3=6m(2)=f(2)+g(2)=3f(2)=g(1)=1g(2)=m(1)=2m(1)=2f(1)=1g(1)=1第十九屆(2013)1某系統(tǒng)自稱使用了一種防竊聽的方式驗(yàn)證用戶密碼。密碼是n個(gè)數(shù)s1,s2,sn，均為0或1。該系統(tǒng)每次隨機(jī)生成n個(gè)數(shù)al,a2,，an,均為0或1,請(qǐng)用戶回答(sial+s2a2+snan)除以2的余數(shù)。如果多次的回答總是正確，即認(rèn)為掌握密碼。該系統(tǒng)認(rèn)為,即使問答的過程被泄露,也無助于破解密碼因?yàn)橛脩舨]有直接發(fā)送密碼。然而,事與愿違。例如,當(dāng)n=4時(shí),有人竊聽了以下5次問答：?jiǎn)柎鹁幪?hào)系統(tǒng)生成的n個(gè)數(shù)掌握密碼的用戶的回答

18、a1a2a3a4111001200110301100411100510000就破解出了密碼si=，s2=，s3=，s4=。(0111)2現(xiàn)有一只青蛙，初始時(shí)在n號(hào)荷葉上。當(dāng)它某一時(shí)刻在k號(hào)荷葉上時(shí)，下一時(shí)刻將等概率地隨機(jī)跳到1,2,k號(hào)荷葉之一上，直至跳到1號(hào)荷葉為止。當(dāng)n=2時(shí),平均一共跳2次；當(dāng)n二3時(shí)，平均一共跳2.5次。則當(dāng)n二5時(shí)，平均一共跳_次。答案：1、0111；2、37/12)解：記青蛙從n號(hào)荷葉平均一共跳f(n)次會(huì)到1號(hào)荷葉上，則f(2)=2,f(3)=2.5,求f(5)。f(2)=(l/2)*1+(1/2)*(1+f(2)9f(2)=2f(3)=(l/3)*1+(1/3)

19、*(l+f(2)+(1/3)*(l+f(3)9f(3)=2.5同理可得：f(4)=(1/4)*1+(1/4)*(1+f(2)+(1/4)*(1+f(3)+(1/4)*(1+f(4)9f(4)=17/6f(5)=(1/5)*1+(1/5)*(1+f(2)+(1/5)*(1+f(3)+(1/5)*(1+f(4)+(1/5)*(1+f(5)解得：f(5)=37/122014（20屆）1.有數(shù)字1,1,2,4,8,8所組成的不同的四位數(shù)的個(gè)數(shù)是2015（21屆）在1和2015之間（包括1和2015在內(nèi)）不能被4、5、6三個(gè)數(shù)任意一個(gè)數(shù)整除的數(shù)有個(gè)。結(jié)點(diǎn)數(shù)為5的不同形態(tài)的二叉樹一共有種。（結(jié)點(diǎn)數(shù)為2的二

20、叉樹一共有2種：一種是根結(jié)點(diǎn)和左兒子，另一種是根結(jié)點(diǎn)和右兒子。）（答案:1、1075；2、42）2016提高組（22屆）一個(gè)1X8的方格圖形（不可旋轉(zhuǎn)）用黑、白兩種顏色填涂每個(gè)方格。如果每個(gè)方格只能填涂一種顏色，且不允許兩個(gè)黑格相鄰，共有種填涂方案。某中學(xué)在安排期末考試時(shí)發(fā)現(xiàn)，有7個(gè)學(xué)生要參加7門課程的考試，下表列出了哪些學(xué)生參加哪些考試（用丁表示要參加相應(yīng)的考試）。問最少要安排個(gè)不同的考試時(shí)間段才能避免沖突？考試學(xué)生1學(xué)生2學(xué)生3學(xué)生4學(xué)生5學(xué)生6通用技術(shù)VV物理VV化學(xué)VV生物VVV歷史VVV地理VV政治VV答案：1、55；2、3）2017提高組（23屆）1如圖所示，共有13個(gè)格子。對(duì)任何

21、一個(gè)格子進(jìn)行一次操作，會(huì)使得它自己以及與它上下左右相鄰的格子中的數(shù)字改變（由1變0,或由0變1）。現(xiàn)在要使得所有的格子中的數(shù)字都變?yōu)?,至少需要3次操作。10010100101102如圖所示，A到B是連通的。假設(shè)刪除一條細(xì)的邊的代價(jià)是1,刪除一條粗的邊的代價(jià)是2，要讓A、B不連通，最小代價(jià)是4（2分），最小代價(jià)的不同方案數(shù)是9（3分）。（只要有一條刪除的邊不同，就是不同的方案）答案：13；24、9)1.某系統(tǒng)自稱使用了一種防竊聽的方式驗(yàn)證用戶密碼。密碼是n個(gè)數(shù)s,s,，s,12n均為0或1。該系統(tǒng)每次隨機(jī)生成n個(gè)數(shù)a,a,a，均為0或1，請(qǐng)用戶回答(sa+sa+12n1122+sa)除以2的余

22、數(shù)。如果多次的回答總是正確，即認(rèn)為掌握密碼。該系統(tǒng)認(rèn)為，即使問nn答的過程被泄露，也無助于破解密碼因?yàn)橛脩舨]有直接發(fā)送密碼。然而，事與愿違。例如，當(dāng)n=4時(shí)，有人竊聽了以下5次問答：1234分析：(s*1+s*1+s*0+s*0)mod2=11234(s*0+s*0+s*1+s*1)mod2=01234(s*0+s*1+s*1+s*0)mod2=01234(s*1+s*1+s*1+s*0)mod2=01234(s*1+s*0+s*0+s*0)mod2=01234解得：s=0，s=1，s=1，s=112342現(xiàn)有一只青蛙，初始時(shí)在n號(hào)荷葉上，當(dāng)它某一時(shí)刻在K號(hào)荷葉上時(shí)，下一時(shí)刻將等概率地隨機(jī)跳

23、到1,2，k號(hào)荷葉之一上，直至跳到1號(hào)荷葉為止。當(dāng)n=2時(shí)，平均一共跳2次；當(dāng)n=3時(shí)，平均一共跳2.5次。則當(dāng)n=5時(shí)，平均一共跳次。分析與解：記青蛙從n號(hào)荷葉跳到1號(hào)荷葉上平均一共跳fn次，貝V：f1=1f2=1*(1/2)+(1+f2)*(1/2)f3=1*(1/3)+(1+f2)*(1/3)+(1+f3)*(1/3)fn=1*(1/n)+(1+f2)*(1/n)+(1+fn)*(1/n)即fn=(1+1+f2+1+fn)*(1/n)=(f1+f2+fn)/nfn=l+(fl+f2+fnT)/(nT)1.某系統(tǒng)自稱使用了一種防竊聽的方式驗(yàn)證用戶密碼。密碼是芒個(gè)數(shù)耳52.剳均宵0或1O該系統(tǒng)每欽隨機(jī)生成八數(shù)販住血均為0或1，請(qǐng)用尸冏答住曲-g-.-砧0除攻戈的余數(shù)。如果多炭的回答總是正確，即認(rèn)為拿握密碼。該系統(tǒng)認(rèn)