第一屆浙江師范大學(xué)C語言程序設(shè)計(jì)競賽解題報(bào)告

1、第一屆浙江師范大學(xué)C語言程序設(shè)計(jì)競賽解 題報(bào)告（羅方煒，lfw256529512& com，浙師大10計(jì)軟）比賽概述首先是本屆比賽的題目:Contest -第一屆浙江師范人學(xué)C語言程序設(shè)計(jì)竟賽2010-12-1? 12 12 12 End time- 2O1O-12-12 5T 1Z12 0亡urprr 占yh已nn i；rrm ?r： - ： - f7 -； ：?Status第一屆新江P血大竽甬言程序設(shè)tt見痂屈LucklProbit Idi齢Title1001 Problem A歡樂衛(wèi)子陀1 (JO? PrnhlrBi K筍單.上半均1003 Probleu C建鈿馮罰I1004 Prob

2、lem D哦悅旳馬崗II10Q5 Prnblrn T.碼頭1006 Prubltu F拿丄SIB100T Rrnblfiii C卑芥干書LOOB Prnblen B字忖由替換StandiriEsl St a-us (StaiiaticE本次比賽的提交統(tǒng)計(jì):Congest Stat.isti 一第 屆浙江師范大學(xué)C語書程宇設(shè)計(jì)競賽|AC PE WA TLE 1J Kwh ai kCHll I hrTSTnt a 1； G+f OCU Pm=sra.lJ nvaVC + +AJ-5G3JB94 432E121134sg614155 1G訂7 93H222350I)呂5IIS510ES4 2珂161

3、03354F42 B宅23111153IQlG3IS21爾5311H41 19 飛 31胡価lLETTotal217311齡201027w115520308 1Jw匸mtOCi其中B，F(xiàn)，H相對簡單，C,E, G為中等題，A,D為稍難題 本次比賽前十名的情況：s you,juSow 1Lh Rw tBBKBT-Contest Standing-.一屆浙遼怖范大學(xué)盲程安沒計(jì)兗咯it check ihes and click the buttonShw ：Dn:-$rTwd ibuhi- Cp * J-牠ml WIlACiiJfN】$g：炬MW耳(-1* 吧:嚴(yán)0l;呱以eC-3)i血山礬汕迎財(cái)

4、igTlQW鱗(-1) (-)y 朗鏟Q】4矽：l(3目insmii-Liiiwr55OH!OL8：OTW：01 -;CMM：鍛盒虹書03zO2: D1C-i)ai: 060： 03d01;Q2i：0oi：oad：og Et(hC-3g朋KOE；0L$：000:031呻：g有：砂3同E叩：r?T;QP(-2)C.-2I-3?T5C0?：OL3：O3C-3J的:啊MO般嚴(yán)C.-6JB10L列】曲I：畫祁E0EID1D432DZEoi0+：ceaWL4: tlOlfin_as! D3! Q32- (2Jfi5iOfl3iD9ZgiHdin心皋神Q01104:045聞：吟:如(-11E4：qj5：&

5、llQI： Ml 汕諄! 2 ；二 i(-P如;Cl覧:瓏0iraiiYiiiw4CVlQ 誨:Q*UBiaaiEr3(-1)QIna a?!0E3-SJ有兩名同學(xué)成功解出6道，還有6名同學(xué)解出5道,4道的還有些，同時(shí)恭喜前5 名獲得本次比賽的一等獎題目講解A :歡樂五子棋Time Limit :1000MS Memory Limit :65536KTotal Submissions:8 Accepted :3Descripti on五子棋是一種兩人對弈的純策略型棋類游戲， 是起源于中國古代的傳統(tǒng)黑白棋種 之一.發(fā)展于日本，流行于歐美。容易上手，老少皆宜，而且趣味橫生，引人入 勝；不僅能增強(qiáng)思

6、維能力，提高智力，而且富含哲理，有助于修身養(yǎng)性.傳統(tǒng)五子棋的棋具與圍棋相同，棋子分為黑白兩色，棋盤為19X19,棋子放置于棋 盤線交叉點(diǎn)上。兩人對局，各執(zhí)一色，輪流下一子，先將橫、豎或斜線的5個(gè)或5 個(gè)以上同色棋子連成不間斷的一排者為勝。Alice和Bob的五子棋游戲和傳統(tǒng)的五子棋有一些不一樣就是他們使用的棋盤被 更改成為9X9。由于Alice是女生,所以每局比賽都由Alice執(zhí)黑先走.現(xiàn)在給定一個(gè)9X9的棋盤，問下一步走的那個(gè)人是否能獲勝，你能編程告訴我嗎？In put數(shù)據(jù)的第一行是一個(gè)整數(shù)N (Nchar g 1515;int dx =-1 ，1,-1,0,1,1,1，0；int dy=1

7、，0，1,1,1,0,-1,-1；bool chk （int x,int y,int t ） int i,tx,ty ，ct8 ;char p=t?w ：b ； for（i=0 ；i 8;i+） cti=0 ； tx=x+dx i ， ty=y+dy i ; while（tx=0& tx9ty=0&ty9gtxty =p） ct i+ ；tx=tx+dxi ， ty=ty+dy i; for（i=0 ；i 4;i+ ） if（ct i+ct i+4 =4） printf （”sn,t ？Bob win ?。骸盇lice win ?。?； return 1;return 0;int main（ ）

8、int i ，j,r=1 ，Cas,cb,cw ，tie; scanf（ d, Cas） ;while （ Cas-） for （i=0；i 9；i+） scanf（ s”，gi ）； printf （ Case %d： ，r+） ； cb=cw=0；for（i=0;i 9； i+） for （ j=0;j 9；j+）if（g ij=b） cb+ ；if （ gi j=w ） cw+； tie=1 ；for （ i=0;i 9 tie ； i+）for（j=0;j 9&tie ； j+） if （gi j=.&chk（i ，j ，cb-cw） tie=0 ； break ；if（tie） pr

9、intf（Tien） ；B :簡單求平均Time Limit ： 1000MS Memory Limit: 65536KTotal Submissions: 615 Accepted : 95Description我們都知道求平均數(shù)吧，即（A1+A2+An ）/ n。這顯然是很簡單的。不過一般一些比賽中各個(gè)評分要去掉最高分和最低分 ,然后對剩下的求平均。我的問 題也是如此，你要對輸入的數(shù)去 掉最高分和最低分 后在求平均，并輸出。Input第一行一個(gè)整數(shù)case表示下面有case組數(shù)據(jù)。每組數(shù)據(jù)兩行，第一行一個(gè)數(shù)N （3 N 10005 ），表示有N個(gè)評分.接下來一行有N個(gè)實(shí)數(shù)，表示得分Outp

10、ut每一行對應(yīng)一組答案即平均得分 （保留小數(shù)點(diǎn)后 2位） 。Sample Input151.1 1。 9 3。 1 4.0 5.1Sample Output3.00思路: 此題比較簡單，線性的掃描每個(gè)數(shù)，然后記錄最大值，和最小值，同時(shí)把每個(gè)數(shù) 之和加起來，那么最后的結(jié)果就是（總和 -最大值最小值 ）/（ 個(gè)數(shù)-2）參考代碼： includex ）m1=x; if （m2 x） m2=x; printf（%.2lfn，（s-m1m2）/（n 2）;C :逃稅的懲罰ITime Limit ： 1000MS Memory Limit ： 65536K Total Submissions:88 Acc

11、epted : 15Description現(xiàn)在是每年集訓(xùn)隊(duì)收保護(hù)費(fèi)的時(shí)間 .每個(gè)集訓(xùn)隊(duì)隊(duì)員每年這個(gè)時(shí)候需要交納兩塊獎牌給韓 BOSS,其他多余獎牌留給 自己做紀(jì)念，但有一個(gè)隊(duì)員只交了一塊獎牌，琪琪受命于韓BOSS，要揪出這一個(gè) 隊(duì)員。琪琪想起了霍格沃茲戰(zhàn)斗分隊(duì)的隊(duì)長在第一節(jié)學(xué)員培訓(xùn)課上就講述過 “百萬軍中 揪逃稅者如探囊取物 ”的知識 ,但是琪琪打瞌睡沒有認(rèn)真聽。 現(xiàn)在,她非常需要你的 幫忙！【位運(yùn)算小知識】與&或|非!異或A左移 右移 如：探測a的第i位是否為1,可用if ( (1 0);計(jì)算a與b的運(yùn)算結(jié)果賦值給a,使用a=aAb；據(jù)說:同時(shí)做出 C、D 兩題的同學(xué)能召喚神龍,好運(yùn) .In

12、put集訓(xùn)隊(duì)里一共有N人(N=1,000, 000)，兩位隊(duì)員可能有相同的編號 no(0二no =1,000,000,000),他們所交的獎牌就以上交隊(duì)員的編號作為區(qū)分,共有 2*N 1塊獎牌編號作為輸入,每個(gè)測試文件只有一組數(shù)據(jù)。Output漏繳保護(hù)費(fèi)的隊(duì)員的編號Sample Input51 3 5 0 1 5 3 5 5Sample Output0Hint兩個(gè)編號為 5的隊(duì)員都交了兩塊獎牌 ,而編號為 0的隊(duì)員只交了一塊 .思路：題目意思有點(diǎn)拗口, 但意思其實(shí)很簡單 , 給你 2n-1 個(gè)數(shù),讓你找出哪個(gè)數(shù)只出 現(xiàn)了奇數(shù)次,這個(gè)利用位運(yùn)算就很簡單了, 用異或操作 (A), 相同的數(shù)異或則為

13、 0, 0 異或任何數(shù)都是任何數(shù),所以,初始一個(gè)0,然后去異或所有的數(shù),則這個(gè)結(jié)果就是答案。參考代碼 :#include stdio.h int main()int n,c , d； scanf(d”, &n);c=0；n=2n-1;while (n) scanf ( %d”,&d)；cA=d;printf(”%dn”,c) ；D :逃稅的懲罰IITime Limit ：1000MS Memory Limit ： 65536KTotal Submissions ： 22 Accepted ： 1Description又到了每年集訓(xùn)隊(duì)收保護(hù)費(fèi)的時(shí)間了。每個(gè)集訓(xùn)隊(duì)隊(duì)員每年這個(gè)時(shí)候需要交納兩塊獎牌給

14、韓BOSS,其他多余獎牌留給自己做紀(jì)念，但和去年不一樣， 這次有兩個(gè)隊(duì)員只交了一塊獎牌， 琪琪受命于韓 BOSS，要揪出這兩個(gè)隊(duì)員。琪琪想起了霍格沃茲戰(zhàn)斗分隊(duì)的隊(duì)長在第一節(jié)學(xué)員培訓(xùn)課上就講述過 “百萬軍中 揪逃稅者如探囊取物 ”的知識，但是琪琪打瞌睡沒有認(rèn)真聽?，F(xiàn)在，她非常需要 你的幫忙！Input集訓(xùn)隊(duì)里一共有N人(N=1, 000,000),任意兩位隊(duì)員可能有相同的編號 no(0=noint a2000005 ;int p50 ；int main ()int i ， n;p0=0；p1=1;for(i=2; ir2) int tmp=r1 ； r1=r2 ； r2=tmp;printf(

15、”%d %dn ，r1,r2) ；E:碼頭Time Limit ： 1000MS Memory Limit: 65536KTotal Submissions: 107 Accepted: 25Description甲乙兩艘輪船駛向一個(gè)不能同時(shí)停泊兩艘輪船的碼頭 ,它們在一晝夜內(nèi)到達(dá)的時(shí)間是等可能的。如果甲船的停泊時(shí)間是 x (0v=xv=24)小時(shí)，乙船的停泊時(shí)間是 y(0v=y=24)小時(shí),求它們中任何一艘都不需要等候碼頭空出的概率是多少 ？Input輸入一個(gè)t =30,接下來有t行，每行代表一個(gè)case每行共有2個(gè)整數(shù) x(0=xy。所以 事件 A 可表示為 A= (t1,t2): (t2

16、11)x 或 t1-t2y其面積為 Sa=( (24x) * (24-x) +(24-y) *(24 y)/2.所以 P(A)= Sa/S如圖紅色部分：z z v-x+x參考代碼：# includevstdio 。hint mai n()int x ，y,n ;double s;scanf(%d ”，& n)；while (n) scanf(” d% d，& x， &y)；s=1.0* (24x) *(24 x) +(24-y)*(24y)/2/24/24 ;printf (” % 3lfn,s );return 0 ；個(gè)人收集整理 勿做商業(yè)用途F:掌上SMSTime Limit:1000MS

17、Memory Limit ： 65536KTotal Submissions ： 146 Accepted ： 44Description大家都會用手機(jī)發(fā)短信吧？會？ 那么你馬上可以做這道題目了 ,下面描述可以跳過。 不會？很多人用手機(jī)發(fā)短信的時(shí)候都是用手機(jī)上 1-9 的鍵盤來打出自己想要打的字母； 可以發(fā)現(xiàn)手機(jī)上的按鍵對應(yīng)著不同的字母如下：1：無2：abc3：def4：ghi5：jkl6：mno7：pqrs8：tuv9：wxyz比如你需要打一個(gè)字母 k 那么你需要按 2 下5； 那么現(xiàn)在給你一串字母希望你能用程序給出我依次需要按哪些鍵才能打出這串 字母。Input數(shù)據(jù)的第一行是一個(gè)整數(shù) N（

18、N 50）,表示一共有 N 組數(shù)據(jù)； 接著從第 2 行到第 N+1 行每一行表示一個(gè)測試數(shù)據(jù) ;測試數(shù)據(jù)只包括到z勺小寫字母，不包括任何其他字符。Output輸出答案，按照Sample Output的格式，注意中間的空格。2acmnameSample OutputCase 1:22226Case 2： 662633思路：這道題引進(jìn)了打表的思想，把各個(gè)字符需要哪些數(shù)字組成的列出一個(gè)表： in t code 30= 2,22,222 ，3 ，33， 333,4 ，44， 444,5 ，55,555 ，6 ，66， 666，7 ，77,777 ，7777，8,88,888,9 ，99， 999，99

19、99；這樣對于讀入的一串?dāng)?shù)字，相應(yīng)的輸出就行了 參考代碼：#includevstdio 。h#include string 。 hchar name20 ；int code 30= 2,22 ， 222，3 ，33,333 ，4 ， 44,444,5,55,555 ，6,66,666,7 ，77， 777,7777,8,88,888 ，9,99 ， 999,9999；void main （） int cas,i，o;scanf （”%d,&cas） ； for（o=1;o=cas ； o+） scanf（s”， name）；int l=strlen（name）;printf（ ”Case %d

20、： ,o ）；for（ i=0 ； i l ； i+ ） printf（%d， code namei - a） ；puts （”） ;G :整齊序列Time Limit: 1000MS Memory Limit: 65536KTotal Submissions: 24 Accepted : 3Description定義一個(gè)序列的整齊度為這個(gè)序列最長的連續(xù)子串的長度 ,這個(gè)子串滿足每一個(gè) 數(shù)比它前一個(gè)數(shù)大C （如果這個(gè)數(shù)前面有數(shù)）.現(xiàn)在給你一個(gè)長度為N的序列， 你可以刪除最多 K 個(gè)數(shù)，使得這個(gè)序列的整齊度最大。Input第一行一個(gè)整數(shù)表示測試數(shù)據(jù)的組數(shù)，對于每組測試數(shù)據(jù)，首先是三個(gè)整數(shù)N，K，

21、C （表示題目描述中的數(shù)），接下來一行 N個(gè)數(shù)字，表示這個(gè)序列。其中（200 =N=500,0=K=N， 0=C=10）Output對于每組測試數(shù)據(jù)，輸出可以得到的最大整齊度。Sample Input26 3 12 4 6 5 2 14 4 16 3 5 2Sample OutputHint第一組測試數(shù)據(jù)子串為 4,5(6 被刪去) 思路：這道題直接的方法好像沒有，但數(shù)據(jù)范圍N在500以內(nèi)，所以可以枚舉，假如我 們知道了子串從哪個(gè)點(diǎn)開始，那么以后的數(shù)，就相應(yīng)的加C就可以了，這部分用 到了談心的思想，就是找到最近的數(shù) , 中間隔多少數(shù)，我們就刪多少，刪了超過 K個(gè)就不行了，反之可以。所以枚舉起點(diǎn)，枚舉中選一個(gè)最長的序列，其長度就是答案。參考代碼：#include stdio 。 hint main () int n ， N,K,C,a 500,i ， j ， num1， num， b， c；scanf ( %d”,&n) ；while ( n)scanf( d%dd”, N， &K，C) ;for(i=0;iN ；i+ )scanf ( d,&ai) ;for(i=0 ， num=0;i N； i+) num1=1 ；for(j=i+1,c=K,b=i;jN；j+)if