編程競賽題(超牛題目,留下做研究).doc

AACMer不得不知道的事兒(二)Time Limit:1000MS Memory Limit:65535K題型: 編程題語言: 無限制描述 作為一個(gè)入門的ACMer，在參加比賽之前，你勢必要了解算法的一些基本概念，比如復(fù)雜度。 ACM的題目，只要不是a+b級別的，總會(huì)需要一定的算法來解決，即使是枚舉， 也是叫做窮舉算法。 一個(gè)算法的好壞，由它的復(fù)雜度來衡量，復(fù)雜度越高，算法越低效。 復(fù)雜度包括不限于時(shí)間復(fù)雜度、空間復(fù)雜度和編碼復(fù)雜度，即其花費(fèi)的時(shí)間、空間（即內(nèi)存使用等）還有實(shí)現(xiàn)的難度。第三個(gè)在做研究的時(shí)候不一定會(huì)考慮，但ACM賽制是5個(gè)小時(shí)內(nèi)決勝負(fù)，編碼復(fù)雜度也是至關(guān)重要的一個(gè)因素。 一、時(shí)間復(fù)雜度 通俗講時(shí)間復(fù)雜度就是用來衡量算法執(zhí)行的時(shí)間的，它和問題的規(guī)模(通常用n表示，如果問題規(guī)模和不止一個(gè)變量有關(guān)，那用n,m,k等等表示)有關(guān)，規(guī)模越大，所花費(fèi)的時(shí)間越長。越高效的算法，在n增長的時(shí)候，執(zhí)行時(shí)間增加的越少。例如求1.n的和，下面有三種寫法：普通寫法是：int sum=0,i;for(i=1;i=n;i+)sum+=i; 我們說它的時(shí)間復(fù)雜度是O(n)。因?yàn)檫\(yùn)行一次，必須執(zhí)行一次n長度的循環(huán)，n越大時(shí)間越大。對于每次循環(huán)，它需要執(zhí)行一次i+，一次sum+=i，一次判斷是否i=n，可以說復(fù)雜度是O(3n)，但是通常常數(shù)不被計(jì)入到復(fù)雜度的計(jì)算中，所以簡化為O(n)。文藝寫法：int sum=n*(n+1)/2;復(fù)雜度O(1)，很明顯運(yùn)行一次只需要執(zhí)行一次運(yùn)算操作。2B寫法：int sum=0,i,j;for(i=1;i=n;i+)for(j=1;j=i;j+)sum+; 嗯，很暴力很2B的O(n2)復(fù)雜度，你懂的。 說到這里相信你已經(jīng)對時(shí)間復(fù)雜度有了一定的了解了。二、空間復(fù)雜度 所謂空間復(fù)雜度就是你用的內(nèi)存的大小，簡單說就是你用了多少變量開了多大的數(shù)組，malloc了多少內(nèi)存，綜合起來就是了，這點(diǎn)比較簡單，就不一一贅述。三、編碼復(fù)雜度 編碼復(fù)雜度和你實(shí)現(xiàn)算法所需要的時(shí)間有關(guān)，而且有時(shí)候和時(shí)間復(fù)雜度也有一定關(guān)系，但不是越高級的算法越難實(shí)現(xiàn)，像剛才的例子就是時(shí)間復(fù)雜度高了，編碼復(fù)雜度也跟著高了。 當(dāng)你對算法有了一定了解，在ACM上收獲了不少知識之后，你甚至能在一些場合很輕松地解決掉一些問題，并BS一些動(dòng)手能力不強(qiáng)的人。 就好比某個(gè)牛津計(jì)算機(jī)系從本科讀到博士還經(jīng)?？嫉谝坏娜?，可以花15分鐘的時(shí)間寫出類似這樣的代碼，來求一個(gè)數(shù)組里面，有多少數(shù)比它左邊的數(shù)都要大：cnt=0;for(i=0;in;i+) for(j=0;ji;j+) if(aiaj) break; if(j=i) bi=1; else bi=0;for(i=0;in;i+) if(bi=1) cnt+;printf(%dn,cnt); 這樣寫法的復(fù)雜度相信大家可以估算的出來，那么，我要你寫出一個(gè)比這個(gè)的時(shí)間復(fù)雜度、代碼復(fù)雜度都要低的代碼來，另外，我還要你求出有多少個(gè)數(shù)比它右邊都要小，同時(shí)，從小到大輸出他們的下標(biāo)（從0開始）。輸入格式第一行，是一個(gè)數(shù)T(T=500)，表示有多少組測試數(shù)據(jù)。第二行乃至結(jié)束，是T組數(shù)據(jù)，對于每組數(shù)據(jù)：第一行是一個(gè)數(shù)n(1=n=100000)，表示這個(gè)數(shù)組的長度。第二行是n個(gè)整數(shù)，有空格分隔。輸出格式對于每組數(shù)據(jù)，輸出四行：第一行，一個(gè)數(shù)A，表示有多少個(gè)數(shù)比它左邊都大第二行，A個(gè)整數(shù)，表示比它左邊都大的數(shù)的下標(biāo)第三行，一個(gè)數(shù)B，表示有多少個(gè)數(shù)比它右邊都小第四行，B個(gè)整數(shù)，表示比它右邊都小的數(shù)的下標(biāo)輸入樣例241 3 1 451 2 3 2 1輸出樣例30 1 322 330 1 214Hint數(shù)組太大要開成全局變量，即放在函數(shù)體外，因?yàn)槎x在函數(shù)體內(nèi)部是占用函數(shù)棧的空間的，而函數(shù)?？臻g比較小，放里面很容易造成爆棧然后得到“運(yùn)行時(shí)錯(cuò)誤”的結(jié)果。另外，輸入流和輸出流是分開的，就是說，處理完一組數(shù)據(jù)，輸出答案，再處理第二組數(shù)據(jù)，再輸出第二組數(shù)據(jù)的答案，再處理第三組.，這樣和處理完所有數(shù)據(jù)，再一次性輸出，是完全等價(jià)的。并且，系統(tǒng)評判的題目都是這樣，不需要保存所有答案一并輸出。之所以這題是(二)滴原因是去年有道一的了喲，看看有助于解決題目喲親BXYM-入門之道Time Limit:1000MS Memory Limit:65535K題型: 編程題語言: 無限制描述 在華農(nóng)的ACM界中，也有一對聞名古今的雙胖師徒組合XYM和BM. BM師父有一個(gè)特殊的癖好，BM肚子很大，因?yàn)樗芟矚g吃西瓜，但是BM的嘴很小，一次只能吃下大小不超過K的西瓜。剛進(jìn)門的XYM為了能拜入BM大神的門下，他買來一個(gè)大小為N的巨型西瓜請BM大神吃。但這個(gè)西瓜太大了，BM是不可能一次就吃完的，于是他讓XYM將西瓜切開。為了簡化問題，每切一刀，大小為N的西瓜就為分成大小分別為N/2的兩塊小西瓜，如果N為奇數(shù)，則被分為一塊大小為N/2，一塊大小為（N/2 + 1）的西瓜。（此處 “/” 為整除） BM為了考驗(yàn)下XYM是否有資格成為他的徒弟，于是他就問XYM，這個(gè)大小為N的西瓜他一共要吃多少次才能全部吃完？ 可是XYM要忙著切西瓜，于是他決定向你求助，你能幫他回答這個(gè)問題嗎？輸入格式 第一行只有一個(gè)正整數(shù)T，表示題目共有T組數(shù)據(jù) 接下來一共有T行， 每行有兩個(gè)正整數(shù)n, k，分別代表XYM買來的西瓜的大小和BM一次能吃下最大的西瓜的大小。 （輸入數(shù)據(jù)保證n, k全部為正整數(shù)， 2= n =100000, 1= k = n-1）輸出格式 對于每組數(shù)據(jù)每行輸出一個(gè)整數(shù)，代表BM一共要吃多少次才把整個(gè)西瓜全部吃完。輸入樣例314 315 11024 5輸出樣例615256Hint對于第一組數(shù)據(jù)：第一次切開后西瓜被分成兩塊大小為7的西瓜，對于每塊大小為7的西瓜再切一刀就變成了一個(gè)大小為3和一塊大小為4的西瓜，大小為3的BM就能直接吃掉了，然后對于大小為4的西瓜再切一刀，就變成兩塊大小為2的西瓜。這時(shí)一共有6塊西瓜，他們的大小分別為2，2，2，2，3，3，所以BM一共要吃6次才能把西瓜全部吃完。CPKKJ的生日禮物Time Limit:1000MS Memory Limit:65535K題型: 編程題語言: 無限制描述 寫下這題目的時(shí)間是11.24，美國時(shí)間也是11.24，以此題祝遠(yuǎn)在美帝的PKKJ彭教主生日快樂。 生日嘛，自然少不了生日禮物的啦。這天彭教主收到來自中國的一份神秘的生日禮物（傳說中是個(gè)漂亮的MM o(_)o 哈哈）。可是禮物卻被一個(gè)密碼鎖鎖了起來（pkkj大叫一聲：坑爹啊，哪個(gè)家伙這么缺德-_-b）。在禮物箱上還附著一張紙條：嘿嘿想知道密碼嗎？那就把下面的題目解出來，答案就是密碼啦！ 對于一個(gè)字符串，定義它的前綴就是指字符串的任意首部。例如字符串a(chǎn)bc的前綴有空串，a，ab，abc。 對于一個(gè)字符串集合，如果集合中任一個(gè)元素都不是其他元素的前綴的話，我們稱之為完美非前綴集合。舉個(gè)例子：”happy”, “birthday”, “to”, “pkkj”就是一個(gè)完美非前綴集合，而“happy”, “hat”, “h”就不是完美非前綴集合。 現(xiàn)在問題來了，給你一個(gè)字符串集合，你要找出一個(gè)該集合的子集，使得該子集是一個(gè)完美非前綴集合，且包含最多的元素。問你這個(gè)完美非前綴子集最多包含多少個(gè)元素？ 由于彭教主一心只想著禮物里面的神秘MM，正所謂一心不能二用，所以他想讓你幫他來解決這個(gè)難題。輸入格式 第一行只有一個(gè)正整數(shù)T，表示題目共有T組數(shù)據(jù) 對于每組數(shù)據(jù)，輸入一個(gè)整數(shù)n （ 0 n = 50 ）， 接下來有n行，每行輸入一個(gè)字符串，字符串由小寫字母（az）組成，且長度不超過50輸出格式 對于每組數(shù)據(jù)每行輸出一個(gè)整數(shù)，代表一個(gè)完美非前綴子集最多包含多少個(gè)元素。輸入樣例24happybirthdaytopkkj4happyhathha輸出樣例42Hint對于第一組數(shù)據(jù)：該集合本身就是一個(gè)完美非前綴集合，所以包含最多元素的完美非前綴子集就是它本身，一共有4個(gè)元素對于第二組數(shù)據(jù)，”happy”,”hat”是其中一個(gè)的包含最多元素的完美非前綴子集，其元素個(gè)數(shù)為2DXYM-AC之路Time Limit:1000MS Memory Limit:65535K題型: 編程題語言: 無限制描述 在華農(nóng)的眾ACMers中，有著一位家喻戶曉、人稱一鳴驚人的DP神牛XYM。由于XYM太出名了，他的仰慕者決定給XYM寫一部個(gè)人傳奇以傳承他光輝的AC之路。為了使故事更加真實(shí)，特派記者Y決定去采訪XYM教主。由于XYM太出名了，而且時(shí)間很忙，他對于每個(gè)問題只會(huì)回答Yes或No。由于這是記者Y第一次跟XYM教主面對面訪談，他十分緊張，所以他可能會(huì)重復(fù)問同一個(gè)問題，但對于相同的問題XYM都會(huì)是相同的回答。記者Y有個(gè)特殊的癖好，每問完一個(gè)問題，他都會(huì)把這個(gè)問題和XYM教主的回答分開記下來。 然而，不幸的是，Y在回去的路上不小心把記有XYM的回答的紙條弄丟了，只剩下一些問題?？蓱z的記者Y決定將XYM教主所有可能的回答的組合全部寫出來。這樣，他就有可能認(rèn)出那個(gè)才是XYM的回答。 不過Y不知道一共要寫多少才行，所以他想向聰明的你求救，一共有多少組可能的回答組合他需要寫出來的？輸入格式第一行只有一個(gè)正整數(shù)T，表示題目共有T組數(shù)據(jù) 接下來是T組數(shù)據(jù)。 每組數(shù)據(jù)第一行輸入一個(gè)整數(shù)n（1= n = 50）, 接下來有n行，每行輸入一個(gè)問題quei,表示Y第i個(gè)問的問題是什么。 每個(gè)問題最多由50個(gè)字符組成，每個(gè)問題只包含小寫字母 (a-z),大寫字母 (A-Z), 問號 (?) 或者下劃線 (_).兩個(gè)問題問題被認(rèn)為相同當(dāng)且僅當(dāng)組成問題的所有字符一一對應(yīng) 相同。輸出格式 對于每組數(shù)據(jù)輸出一個(gè)整數(shù)，表示所有可能的回答的組合的方案數(shù)。輸入樣例33How_are_you_doing?How_do_you_like_our_country?How_are_you_doing?1 Whazzup?4Do_you_like_my_story?Do_you_like_my_storyDO_YOU_LIKE_MY_STORY?Do_you_like_my_story?輸出樣例4216Hint對于第一組數(shù)據(jù)，一個(gè)有四種可能的回答組合Yes, Yes, Yes;Yes, No, Yes;No, Yes, No;No, No, No.E我們?nèi)晕粗滥翘焖匆姷幕ǖ拿諸ime Limit:1000MS Memory Limit:65535K題型: 編程題語言: 無限制描述 芽間、仁太、波波、安鳴、雪集、鶴見是昔日孩童時(shí)期總是一起結(jié)伴同玩的6位好朋友。自從小時(shí)候的一次意外后，大家的關(guān)系漸行漸遠(yuǎn)。隨著時(shí)間的流逝，大家都為了自己的生活和理想各奔東西。 某天，芽間要離開大家了，她給大家各留下了一封電子郵件。這時(shí)候，在名牌高中讀書的雪集，仗著自己的電腦知識，把給仁太電子郵件內(nèi)容（一句話）加密了。然后他留下了一段加密程序，因?yàn)樗肟纯醋x普通學(xué)校的仁太能不能解密出來的。 但事實(shí)證明，學(xué)校的名牌與否不是最重要的，重要的是自己個(gè)人的努力。為了看到芽間給自己的信，仁太專門去學(xué)了C語言，然后把那句話解密出來了。你也能做到嗎？輸入格式以下是雪集的加密代碼：void Encrypt(char msg)char key = sleepiforest;int msgLen = strlen(msg);int keyLen = strlen(key);int offset;for(offset=0;offsetmsgLen;+offset)msgoffset = keyoffset%keyLen; / 是異或運(yùn)算for(offset=0;offsetmsgLen;+offset)printf(%02x ,msgoffset); /%x是十六進(jìn)制芽間的郵件里的內(nèi)容msg傳入上面的函數(shù)后，得到以下的輸出。53 30 39 59 0e 48 18 4f 34 0a 01 13 16 18 48 28 15 44 28 00 06 45 0d 55 0d 52 4a 4a 50你能把msg的原文輸出解密出來嗎？輸出格式根據(jù)加密程序，把這句話解密，然后輸出出來即可。例如：假設(shè)解密出來的這句話是“WELCOME TO THE TEAM OF SCAU_ACM”。那么你只需要把這句話輸出就可以了。提供一個(gè)模板:#include int main()char msg = WELCOME TO THE TEAM OF SCAU_ACM;puts(msg);return 0;只需要把msg里的內(nèi)容換成你解密出來的內(nèi)容，提交即可通過。輸入樣例無輸出樣例根據(jù)題目要求輸出Hint一個(gè)字符也不能漏，不能錯(cuò)哦所以呢最好還是在解密程序里把解密后的串輸出吧提供一個(gè)錄入數(shù)據(jù)的代碼：char bin = 53 30 39 59 0e 48 18 4f 34 0a 01 13 16 18 48 28 15 44 28 00 06 45 0d 55 0d 52 4a 4a 50;char msg50;int len = (strlen(bin)+1)/3;for(int i=0;ilen;+i)這里可以用sscanf把bin內(nèi)的數(shù)據(jù)錄入到msg具體用法大家查資料吧F俄羅斯方塊Time Limit:1000MS Memory Limit:65535K題型: 編程題語言: 無限制描述 某個(gè)ACMer很喜歡玩游戲。這天，他在一個(gè)網(wǎng)站上看到一個(gè)關(guān)于俄羅斯方塊能否無限玩下去的帖子，于是很感興趣的把這問題轉(zhuǎn)述給了其余的ACMer，結(jié)果無人問津 這時(shí)恰好新生賽也到了，這個(gè)ACMer于是靈機(jī)一動(dòng)，想出一個(gè)俄羅斯系列題目！但是被強(qiáng)大的lyd鄙視了一把，認(rèn)為這樣出的題目難度會(huì)很大，于是某人就一再保證，該題目一定會(huì)很簡單很簡單的！所以，就有了這樣的一個(gè)很簡單的問題：有一個(gè)A*B大小的框，往里面放入N條1*M的長條，能否放入？ 怎么樣，這問題很簡單吧？輸入格式第一行輸入T作為case數(shù)，第二行到第T+1行分別輸入整數(shù)A，B，N，M作為框的長寬和長條的數(shù)目和長度。(0A,B,N,M1000000)輸出格式對每個(gè)case輸出一行，能放入輸出YES，不能放入輸出NO。輸入樣例21 1 2 33 3 2 2輸出樣例NOYESGDeathGod不知道的事情Time Limit:1000MS Memory Limit:65535K題型: 編程題語言: 無限制描述 螞蟻是很強(qiáng)大的動(dòng)物，除了DeathGod知道的事情外還有很多不知道的！例如 根據(jù)某種理論，時(shí)間方向上有無數(shù)個(gè)平行世界，有的世界螞蟻很多，有的世界螞蟻很少，有的世界螞蟻會(huì)繁殖，有的世界螞蟻不會(huì)繁殖。 DeathGod沒有時(shí)空穿梭的能力，因此他無法知道所有的螞蟻加起來到底有多少。但他知道未來的ACMer非常厲害，可以暫時(shí)拋棄肉體，以思維進(jìn)行時(shí)空旅行。因此他留下一段話給未來的ACMer，讓他們幫他數(shù)一數(shù)，所有的平行世界總共有幾只螞蟻。 由于時(shí)間旅行是不可逆的，因此DeathGod只能讓ACMer逆向推算出在DeathGod的那個(gè)時(shí)間點(diǎn)上所有的平行世界總共有多少只螞蟻。 此時(shí)，未來的ACMer，就是你，已經(jīng)在無數(shù)個(gè)平行世界中搜索過了（只用了一瞬間），在你所處的時(shí)間點(diǎn)上，第0，1，2，3N-1個(gè)平行世界上的螞蟻數(shù)目分別為A0,A1,A2,A3.AN-1，為了簡化計(jì)算，所以每個(gè)平行世界上的螞蟻數(shù)目都是當(dāng)作整數(shù)計(jì)算。而已知每兩只螞蟻每過時(shí)間t，就會(huì)生出一只螞蟻。如果有八只螞蟻，那么過了時(shí)間t后就會(huì)變成十二只螞蟻，再過時(shí)間t就會(huì)變成十八只螞蟻。如果螞蟻數(shù)目是單數(shù)，比如有七只螞蟻，那么過了時(shí)間t后就會(huì)變成十只螞蟻。再過時(shí)間t就會(huì)變成十五只螞蟻。有的世界里面的螞蟻是不會(huì)繁衍的，因此螞蟻的個(gè)數(shù)就不會(huì)變化，不會(huì)遵從這個(gè)定律。假設(shè)所有的螞蟻不會(huì)死亡。那么你應(yīng)該可以計(jì)算出在DeathGod所在的時(shí)間點(diǎn)上，最少可能存在幾只螞蟻（如果只有一只螞蟻，是不會(huì)繁衍的，如果螞蟻會(huì)繁衍，那么一定遵從上面的定律。如果不遵從上面定律的，那么一定不會(huì)繁衍。且螞蟻只能跟和自己同一個(gè)世界里的螞蟻交配。） 不過，最囧的事情就是，即使你算出來了，由于信息無法逆時(shí)間方向傳遞，因此DeathGod還是無法知道。不過為了培養(yǎng)未來的ACMer的耐心和毅力，以及面對惡心模擬題時(shí)不至于雙眼發(fā)昏腦袋發(fā)脹