1、Research for National Training Team of China, IOI2009在模擬中思考前言模擬，即模仿、效仿。它被廣泛地運(yùn)用于的生產(chǎn)生活當(dāng)中。模擬炒股，可以幫股民更好分析動(dòng)態(tài)，可以讓考生查漏補(bǔ)缺并適應(yīng)考場(chǎng)氛圍； 模擬演練，可以修正中的，使之更加在信息學(xué)奧賽（Olympiad in Informatics，簡稱 OI）中，它則是將算法以程序的形式加以實(shí)現(xiàn)的過程。做一道題，需要先思考出一個(gè)算法，再通過模擬使其成為程序代碼。而陶瓷的制作，先是將合適的黏土打造成型，之后進(jìn)行燒制。陶瓷在燒制時(shí)必須掌握好火候，才可能成為歷代行家們的愛寵。同樣，任何程序都離不開模擬，而程序員

2、的模擬功底直接關(guān)系著其工作效率及其作品的優(yōu)良。現(xiàn)在，就讓來看看，通過對(duì) OI 的學(xué)時(shí)常見的模擬，能帶來哪些思考。1 of 23Huaxing DONGProvinceShaoxing Onior High School inResearch for National Training Team of China, IOI2009目錄前言.1目錄.2正文.3注意細(xì)節(jié).3例一例二文件解壓.3. 3數(shù)字翻譯.4. 5小結(jié).6優(yōu)化算法.7例三例四乘法運(yùn)算.7. 7跳動(dòng)的水珠.8. 9小結(jié).10重新思考.11例五設(shè)計(jì).11一.12二.12三.13小結(jié).14總結(jié).15感謝.15附錄.16文件解壓.16Nu

3、mbers to Numbers.17跳動(dòng)的水珠.19解題. 20Chip Designing.22香北求職記后記.232 of23Huaxing DONGProvinceShaoxing Onior High School inResearch for National Training Team of China, IOI2009正文注意細(xì)節(jié)生活中的點(diǎn)滴匯成了注意。寶貴的生命。算法的模擬，當(dāng)然也離不開對(duì)細(xì)節(jié)的例一 文件解壓有一個(gè)文本文件，可以含有除數(shù)字（“0”至“9”）和左右小括號(hào)（“（”與“）”）以外的所有字符?，F(xiàn)在它被“壓縮”了：1.2.3.若“壓縮”后的內(nèi)容 P不含數(shù)字和小括號(hào)，則將

4、 P解壓后還是 P；用 Numb)表示將其解壓，需將 P重復(fù)解壓 Number次；用 P1P2表示將其解壓，需要先將 P1解壓，再將 P2解壓。給出文本被“壓縮”后的內(nèi)容，讓你還原整個(gè)文本，保證還原出來的內(nèi)容不超過 1MByte。輸入格式若干字符描述“壓縮”后的文本。輸出格式若干字符描述原文內(nèi)容。輸入樣例r2(a4(b)t2(e)輸出樣例rabbbbabbbbtee這道題目的算法非常簡單，分治處理即可：r2(a4(b)t2(e)r2(a4(b)t2(e)a4(b)eb3 of 23Huaxing DONGShaoxing Onior High School inProvinceResearch

5、 for National Training Team of China, IOI2009即，遞歸處理一個(gè)串。一開始堆棧層數(shù)設(shè)定為 0，接著按順序枚舉串中的每個(gè)字符，假設(shè)是左括號(hào)，則堆棧層數(shù)加 1，假設(shè)是右括號(hào)，堆棧層數(shù)減 1。如果當(dāng)前堆棧層數(shù)是 0 并且是一個(gè)需要解壓的字符，則將其輸出；如果當(dāng)前是一個(gè)數(shù)字 k，則遞歸處理這個(gè)數(shù)字之后的對(duì)應(yīng)的那層括號(hào)中的內(nèi)容，并反復(fù)處理 k 次。 雖然算法如此簡單，但在模擬的時(shí)候還是應(yīng)該注意到一些問題：1. 可能“壓縮”后的內(nèi)容中有這個(gè)字符但實(shí)際上并不存在，例如“0(ab)”表示的是空。這是需要考慮的；2. 雖然題目說輸出內(nèi)容不會(huì)超過 1MByte，但是“壓縮

6、”后的內(nèi)容還是有可能類似“999999999(0(ab)”的樣子。如果盲目地直接寫循環(huán)，難免會(huì)發(fā)生超時(shí)的情況，而只要對(duì)解壓的內(nèi)容為空時(shí)進(jìn)行特判即可輕松避免發(fā)生這種情況；3. 既然用于表示解壓次數(shù)的數(shù)字可能很大類型或者用其他方式加以處理，避免發(fā)生類型溢出就需要合理選擇。數(shù)字的許多題目不僅在算法模擬時(shí)，在審題和思考時(shí)都存在著不少容易忽視的細(xì)節(jié)。有些時(shí)候，細(xì)節(jié)之間可能存在著某種連帶關(guān)系，只要發(fā)現(xiàn)一個(gè)，其他的也會(huì)自然在你面前出現(xiàn)。而忽視細(xì)節(jié)的代價(jià)可能會(huì)比較慘痛。在 2008 年“AMD”杯競(jìng)賽（National Olympiad in Informatics，簡稱第二十五屆信息學(xué)NOI，2008 年的

7、 NOI 即 NOI2008）中，有道叫做假面舞會(huì)的題，其輸出內(nèi)容分別是最大可能的面具類數(shù)和最小可能的。由于樣例輸出兩個(gè)數(shù)字是一樣的，再加部分同學(xué)不仔細(xì)審題，當(dāng)時(shí)有不少認(rèn)為第一個(gè)數(shù)字是最小，而第二個(gè)數(shù)字是最大。這樣一來，那些同學(xué)的比賽得分就可能大打折扣了。有理由自己是否認(rèn)真對(duì)待了手中的題目，思考是否注意到了這些應(yīng)該注意到的細(xì)節(jié)問題，不應(yīng)讓出題者小小的掩蓋了自己發(fā)生的錯(cuò)誤。例二 數(shù)字翻譯有一篇用英文寫的文章，請(qǐng)你將和數(shù)字（非負(fù)基數(shù)詞，所表示的數(shù)字最多 9 位）相關(guān)的詞組翻譯成數(shù)字。如果一篇文章有多種翻譯方法，則先滿足被翻譯出來的單詞盡可能多，再滿足越先被翻譯出來的數(shù)字越大。輸入格式一篇文章，只含

8、有空格、回車、各種標(biāo)點(diǎn)，以及大小寫英文字母。輸出格式4 of 23Huaxing DONGProvinceShaoxing Onior High School inResearch for National Training Team of China, IOI2009一篇經(jīng)過翻譯的文章。樣例輸入From three thousand onefrom one thousand fourdred and fifty teamecteddred and eleven universitiesin seventy five countries competing at onedred andtwen

9、ty seven sites anddreds more competing atpreliminary contests worldwide, seventy three teamsof students competed for bragging rights and prizesat The Twenty Eighnnual ACMernational CollegiateProgramming Contest World Finals sponsored by IBM onMarch Thirty One, Two Thousand Four, and hosted at thei D

10、um, Prague by Czech Technicaiversity in Prague.樣例輸出From 3150 teamectedfrom 1411 universitiesin 75 countries competing at 127 sites and preliminary contests worldwide, 73 teamsdreds more competing atof students competed for bragging rights and prizesat The 20 Eighnnual ACMernational CollegiateProgram

11、ming Contest World Finals sponsored by IBM onMarch 31, 2004, and hosted at thei Dum, Prague by Czech Technicaiversity in Prague.這題的任務(wù)非常明確，只要將數(shù)字翻譯出來即可。不過這道題目容易讓人走入“按順序翻譯下來，能翻則翻”的貪心誤區(qū)。只要仔細(xì)加以思考就會(huì)發(fā)現(xiàn)“one thousand one thousand”應(yīng)該翻成“1000 1000”，而“one thousand one thousandone”應(yīng)該翻成“1000 1001”；“onedred and one

12、”應(yīng)該翻譯成“101”，“onedreddredand oneand onedred and one”應(yīng)該翻譯成“100 and 101”，“onedred and onedred”應(yīng)該翻成“101dred and 100”；另外，別忘“zero”必須單獨(dú)翻成“0”才行雖然考慮到的貪心反例這么多，不過只需要用動(dòng)態(tài)規(guī)劃即可解決：狀態(tài) f i表示逆序翻譯到第 i 個(gè)單詞，翻譯出的單詞最多是幾個(gè)。按長5 of 23Huaxing DONGProvinceShaoxing Onior High School inResearch for National Training Team of China,

13、 IOI2009度從大到小枚舉到目前為止最后一個(gè)需要整體翻譯成一個(gè)數(shù)字的連續(xù)的單詞是哪些，判斷一下是否可以整體翻譯。如果可以整體翻譯就轉(zhuǎn)移：如果后面的狀態(tài)比我原先轉(zhuǎn)移出來的好，那直換；如果一樣，則不替換，因?yàn)閷?duì)于相同前綴的單詞串，單詞數(shù)目越多它所表示的數(shù)字越大；如果后面的狀態(tài)更劣就不用管了 。判斷一個(gè)單詞串是否可以整體翻譯，只要將串按“million”或“thousand”分成最多三部分，每部分最多即一個(gè)三位數(shù)，而它的種類也不是很多，一一判斷即可。當(dāng)然對(duì)“zero”需要單獨(dú)判斷。根據(jù)題目，一個(gè)數(shù)字最多用類似“onedred and one million onedred andone thou

14、sand onedred and one”14 個(gè)單詞表示，故動(dòng)態(tài)規(guī)劃時(shí)間也可以寫得很一下路徑。低。當(dāng)然還得有時(shí)，如果對(duì)題目考慮不周，整個(gè)算法都會(huì)完全。所以，在做題的任何時(shí)候，必須對(duì)細(xì)節(jié)加以盡可能充分的思考。盡可能抓住一些算法中的共同點(diǎn)，有時(shí)候還能讓的代碼寫得又短又清楚。小結(jié)宋代鶴中便有“一日一錢，千日千錢；繩鋸木斷，水滴石穿”的說法。細(xì)節(jié)的總和便是問題本身，注意題目相關(guān)的各種細(xì)節(jié)，可以使更好地解決問題。而對(duì)細(xì)節(jié)的忽視往往體現(xiàn)在下面幾個(gè)方面：沒有仔細(xì)審題。審題是做題的第一步，認(rèn)清問題才能更好解決問題；沒有仔細(xì)思考，或是來不及思考。比賽中有時(shí)會(huì)因?yàn)闀r(shí)間的限制，不能讓充分思考問題。因此，應(yīng)該合理安

15、排審題、思考并設(shè)計(jì)算法，以及模擬的時(shí)間讓問題的解決最大化；沒有良好的心態(tài)或狀態(tài)。在比賽中應(yīng)該調(diào)整好自己的狀態(tài)至最佳，讓自己的大腦在緊張的氣氛中得以更好思考。這些，并不是一朝一夕可以避免的，且每個(gè)人的情況也會(huì)有所不同。但是我們相信“實(shí)踐是檢驗(yàn)真理最好的方法”，于自己的方法。每個(gè)人都應(yīng)該在實(shí)踐中探尋并調(diào)整屬6 of 23Huaxing DONGProvinceShaoxing Onior High School inResearch for National Training Team of China, IOI2009優(yōu)化算法一個(gè)好程序，只是算法優(yōu)美那僅僅不夠，還要能跑得快。這不僅是許多題目本身

16、的規(guī)定，也是生產(chǎn)生活中所必須的。想象一下，在一個(gè)低效的世界，的生活會(huì)變得多么糟糕交通的不便、 通訊的緩慢很難實(shí)現(xiàn)自己的物質(zhì)需求和精神追求。為了擺脫效率的低下，社會(huì)實(shí)踐中應(yīng)該大力發(fā)展生產(chǎn)力，加快經(jīng)濟(jì)發(fā)展。而考慮程序的運(yùn)行速度，正如這項(xiàng)競(jìng)賽所被賦予的“寫程序，也應(yīng)充分”的精神。要讓我們的程序跑得更快，不僅可以通過在思考之初直接改進(jìn)算法，也可以在算法的模擬中找到突破并對(duì)其進(jìn)行優(yōu)化。例三 乘法運(yùn)算給出兩個(gè)非負(fù)整數(shù) a 和 b，讓你求他們的積。輸入格式一行兩個(gè)非負(fù)整數(shù)。輸出格式一個(gè)數(shù)字，表示兩數(shù)之積。樣例輸入1 2 樣例輸出3這是一個(gè)很基礎(chǔ)的高精度乘法，對(duì)于每個(gè)數(shù)字用一個(gè)數(shù)組存下其每一位，模擬小學(xué)豎式的

17、運(yùn)算即可。不過別忘記本文之前提到的“注意細(xì)節(jié)”，例如， 一個(gè)很大的數(shù)字乘以 0，你就可能需要對(duì)于去除一下多余的前導(dǎo) 0。顯然，為了加快程序運(yùn)行速度，可以在模擬的時(shí)候用萬進(jìn)制乘法代替十1進(jìn)制乘法，這樣程序運(yùn)行的時(shí)間就可以縮短到原先的。16像這類簡單的常數(shù)優(yōu)化還有很多：1.2.使用位運(yùn)算；程序中過程和函數(shù)調(diào)用時(shí)的參數(shù)，有時(shí)可以用一些內(nèi)存的地址來大數(shù)7 of 23Huaxing DONGProvinceShaoxing Onior High School inResearch for National Training Team of China, IOI2009組。比如使用變參而不用值參；這些常數(shù)

18、優(yōu)化，并不需要進(jìn)行很多的思考，也不需要花很多的時(shí)間，只要在算法的模擬時(shí)加以使用，便可以達(dá)到所期望的目的，何樂而不為呢。例四 跳動(dòng)的水珠有一個(gè) N*M的矩陣。矩陣中每個(gè)位置有單獨(dú)的成循環(huán)的指令序列，且循環(huán)節(jié)長度 Li,j為 3、7 或 9。指令有在當(dāng)前位置增加 X粒水珠（C），把當(dāng)前位置水珠全部上移（U）、下移（ D）、（ L）、右移（ R），共五種。已知初始每個(gè)位置上都沒有水珠，讓你求 T 時(shí)刻的局面，輸出時(shí)所有數(shù)字對(duì) P取模 。時(shí)刻 0時(shí)刻 1時(shí)刻 2時(shí)刻 3注釋 每個(gè)時(shí)刻左邊的是當(dāng)時(shí)每個(gè)單元上的水珠數(shù)目，右邊的是當(dāng)時(shí)的指令輸入格式第一行五個(gè)正整數(shù) N，M，X，P和 T接下來 N行，每行 M

19、項(xiàng)內(nèi)容。每項(xiàng)內(nèi)容先是一個(gè)整數(shù) Li,j，然后是長度 為 Li,j的一個(gè)由 C、U、D、L、R 組成的字符串，描述指令序列的循環(huán)節(jié)，串的第一個(gè)字符是時(shí)刻 0 時(shí)所對(duì)應(yīng)的指令。輸出格式N行，每行 M個(gè)數(shù)，描述 T時(shí)刻局面。樣例輸入2 2 1 100 33 CDC 3 UUL3 CRC 7 UCDLULL樣例輸出1 02 08 of23Huaxing DONGProvinceShaoxing Onior High School in1020CLCD0012DURC1010CUCU0000TypeBigNum =Array0.1000of Long;Procedure Calc(Var A:BigNu

20、m);.Research for National Training Team of China, IOI2009這道題目乍眼一看，發(fā)現(xiàn)只要按照題目所說的內(nèi)容一個(gè)時(shí)刻一個(gè)時(shí)刻模擬下去即可，能不能讓程序更快些呢？在紙上模擬一番并作思考，不難發(fā)現(xiàn)，原本在某個(gè)位置上的水珠，經(jīng)過一定時(shí)間后它們所去的目的地是唯一的、確定的，因?yàn)槿我晃恢迷谌我鈺r(shí)刻它的指令是唯一的。先對(duì)其所有位置進(jìn)行標(biāo)號(hào)，再建一張一維表 Link，表示水的去于某一時(shí)刻內(nèi)，如果標(biāo)號(hào)為 i位置的水珠會(huì)跳到標(biāo)號(hào)為 j位置，則設(shè) Linki為 j，如 果水走出了大矩陣，則為 0，特別的 Link0為 0。比如樣例時(shí)刻 2 內(nèi)的 Link可以這樣寫

21、：用 Linki表示時(shí)刻 i內(nèi)水的去向，Succi,j表示時(shí)刻 i開始到時(shí)刻 j結(jié)束最終水的去向，則有 Succi,j=Linki$Linki+1$.$Linkj。這里 Ret=A$B表示種運(yùn)算，即 Reti=BAi。定義的一對(duì)于指令 C 產(chǎn)生的水，也用一張一維表 Create表示水的產(chǎn)生情況。對(duì)于某一時(shí)刻內(nèi)，如果標(biāo)號(hào)為 i 的位置的水珠產(chǎn)生了 X粒，則設(shè) Createi為 X。比如樣例時(shí)刻 1 內(nèi)的 Create可以這樣寫：并且用 Valuei,j 表示時(shí)刻 i 開始到時(shí)刻 j 結(jié)束最終水的產(chǎn)生情況， 則有Valuei,j=Createi$Createi+1$.$Createj。這里$運(yùn)算也

22、是新定義的，并且它的運(yùn)算還要借助上面提到的 Link。運(yùn)算 Ret=Createi$Createj，對(duì)于 Reti，首先，它得包含 Createji；然后如果有 Linkjk=i，則還要包含 Createik，因?yàn)樵?Createi產(chǎn)生的水通過時(shí)刻j即 Linkj的作用，位置會(huì)發(fā)生改變最終要求的便是 Value1,t。設(shè) Lcm為輸入中所有 Li,j的最小公倍數(shù)，因?yàn)?Create和 Link每 Lcm個(gè)成一個(gè)循 環(huán)，故可以將一個(gè)循環(huán)節(jié)合在一起考慮：這里設(shè) k是 2 的若干次，所有的Create都一樣，Link也一樣。因?yàn)镾ucc1,k和Succk+1,2k是一樣的，Value也滿足這 點(diǎn)，可

23、以先按題目模擬出 Succ1,k 和 Value1,k， 然后去求 Succ1,2k 和Value1,2k這里就可以用到平時(shí)比較熟悉的快速冪了。那么最后的復(fù)雜度也可以從一開始的 O(NMT)變成 O(NMlog2T)。說到這里，發(fā)現(xiàn)：這題最后的算法和一開始的算法本質(zhì)上并沒有發(fā)生改9 of 23Huaxing DONGProvinceShaoxing Onior High School in01234值01010123401234值030441234Research for National Training Team of China, IOI2009變，都是在按題目所說的模擬，只不過通過邊模

24、擬邊思考，尋找到了可以優(yōu)化的突破口，應(yīng)用對(duì)應(yīng)的策略，使得其模擬起來更快。讀入題目中的算法 一秒一秒模擬得到結(jié)果O(NMT)讀入快速乘冪得到結(jié)果O(NMLog2T)VS小結(jié)競(jìng)賽中，常常由于比賽時(shí)間的限制，不能充分思考，只能得出一些比較低效的算法。但是，可以在算法的模擬中略微思考，尋找優(yōu)化的突破口，在有限的做題時(shí)間中讓自己比較低效的算法也能跑出較快的速度。優(yōu)化算法，不單體現(xiàn)在讓程序跑得快，也可以體現(xiàn)在讓程序?qū)懫饋砀奖?。這將在之和的文章中提到。10 of 23Huaxing DONGProvinceShaoxing Onior High School in1. Lcm為2. 目的地唯一Resear

25、ch for National Training Team of China, IOI2009重新思考平時(shí)，對(duì)事物的看法總是會(huì)局限于一個(gè)方面。但是，很顯然的事實(shí)是，任何事物都有其相對(duì)的兩面，每個(gè)人身上都有自己的優(yōu)點(diǎn)和。當(dāng)?shù)目捶ㄏ萑胨姥h(huán)的時(shí)候，重新思考應(yīng)該是最好的選擇。同樣，去思考一個(gè)題，也很容易走入死胡同。即使一個(gè)算法是正確的，好地模擬出來。那么，模擬一個(gè)算法就成為了也并不一定能在規(guī)定時(shí)間內(nèi)很完成一道題目時(shí)最大的。對(duì)于在剩下所規(guī)定的時(shí)間內(nèi)辛苦、緊張，甚至還繁瑣地去模擬，有時(shí)還不如讓我們重新思考，找到讓模擬起來更輕松的算法。例五設(shè)計(jì)平面上有上下兩排點(diǎn)，他們位于坐標(biāo)(0,0)、(1,0)、(n-

26、1,0)以及(0,1)、 (1,1)、(n-1,1)。已知下排的每個(gè)點(diǎn)和上排的某個(gè)點(diǎn)相配對(duì)，共 n 對(duì)?，F(xiàn)在讓你給出一種點(diǎn)對(duì)之間的用折線段連接方案，使得折線段的折角為直角且沒有兩條折線段相交的情況出現(xiàn)。輸入格式第一行，一個(gè)數(shù)字 n。第二行，1 至 n 的一個(gè)排列，描述下排點(diǎn)與上排點(diǎn)的對(duì)應(yīng)關(guān)系。輸出格式共 n 部分：每部分第一行是一個(gè)數(shù)字 m，表示折線中的線段數(shù)目，接著 m 行按順序輸出每條折線段。折線段中的每個(gè)點(diǎn)的坐標(biāo)的兩維均用一個(gè)既約分?jǐn)?shù)表示。樣例輸入22 1 樣例輸出30/1 0/10/1 1/21/1 1/211 of 23Huaxing DONGProvinceShaoxing Oni

27、or High School inResearch for National Training Team of China, IOI20091/1 1/141/1 0/13/2 0/13/2 3/20/1 3/20/1 1/1這道題目給人的初步感覺是比較難的，但大致應(yīng)該就是隨便設(shè)計(jì)一種連線的方法，然后模擬一下即可。一設(shè)(-1,-1) 至(n,2) 為可以設(shè)計(jì)如下這種算法：的連線區(qū)域。先用 1 * 1 的正方形切割這塊區(qū)域，正22方形的邊即為邊，題目中所說的 2n 個(gè)點(diǎn)除了需要連線的兩個(gè)端點(diǎn)都不存在，然后去為第一對(duì)點(diǎn)找一條最短路或是拐彎次數(shù)比較少的路。接著用 1 * 1 的正方形切割這塊區(qū)域，和

28、44剛才一樣，并去掉和我已經(jīng)連的折線所重合的邊， 再找一條路 直到最后， 用11*的小正方形切割，再做即可。2n2n但是這個(gè)算法直接模擬起來，越到最后，區(qū)域內(nèi)點(diǎn)和邊的數(shù)量越是巨大，有必要對(duì)算法做進(jìn)一步處理。而且讓人感覺到，即使處理完這些問題，這題用這個(gè)算法模擬起來也相當(dāng)繁瑣。如果按這個(gè)算法的方向繼續(xù)，可能會(huì)花費(fèi)新思考。二非常多的時(shí)間和精力，那不妨對(duì)這個(gè)題目重不妨將算法往簡單點(diǎn)的考慮，按順序處理每一對(duì)點(diǎn)，都從下排的點(diǎn)出發(fā)， 最后連到上排的。12 of 23Huaxing DONGProvinceShaoxing Onior High School inResearch for National

29、Training Team of China, IOI2009一對(duì)點(diǎn)，從下出發(fā)如果上方?jīng)]有，就先向上走，到中間向右折一下，到對(duì)應(yīng)的位置向上再折一次即可。否則，就先向上走，然后向右折，貼著之前所連的折線走即可：發(fā)現(xiàn)，其實(shí)對(duì)于連線區(qū)域的上半部分，每次連完之后都類似一把梳子。每次連線，這個(gè)“梳子”即可。這個(gè)算法，思路比較簡單，而且讓人覺得，模擬也方便多了。說到這里，回想一下本文上一章內(nèi)容中所一個(gè)遺留的內(nèi)容“優(yōu)化算法，不單體現(xiàn)在讓程序跑得快，也可以體現(xiàn)在讓程序?qū)懫饋砀奖恪＝酉聛韺?huì)有所說明?！比槍?duì)本題，原本算法過于復(fù)雜，模擬過于繁瑣，重新思考后得到了這些模擬起來較容易的算法的。那來更得心應(yīng)手。不妨

30、再去優(yōu)化一下剛才的算法，使模擬起可以先在上下兩排點(diǎn)之間放一塊隔板，并且在連線的時(shí)候按順序針對(duì)每一條折線設(shè)定一個(gè)固定偏移量，第一對(duì)點(diǎn)是 delta1，第二對(duì)點(diǎn)是 delta2，如下圖所示去做：13 of 23Huaxing DONGProvinceShaoxing Onior High School inResearch for National Training Team of China, IOI2009到此，就可以很容易地寫出既正確，又高效，且簡短的程序了。小結(jié)重新思考，在 OI 中，它可以幫助找到正確的算法，也可以幫助找到更容易模擬的算法；而現(xiàn)實(shí)中，它可以在一個(gè)就業(yè)的冬天重新樹立人們的擇

31、業(yè)觀，幫助畢業(yè)的大學(xué)生們盡快找到自己的所能香北求職記中，管理學(xué)學(xué)士香北經(jīng)過漫長的一次又一次的求職失敗，在朋友的提醒下，重新思考自己的就業(yè)問題，最終找到了合適自己的工作，并寫下了這樣的后記：“現(xiàn)在的我，竟然找到了工作，竟然做了一名，竟然可以賺錢了，如果知道現(xiàn)實(shí)會(huì)是這樣美好，我當(dāng)初為何要因?yàn)檎也坏焦ぷ鞫鴾I流滿面，直到欲哭無淚呢？”重新思考，這是生活和學(xué)習(xí)中必須學(xué)會(huì)應(yīng)用的。它可以帶給，可以帶給理智14 of 23Huaxing DONGProvinceShaoxing Onior High School in枚舉下排所有點(diǎn)讀入目標(biāo)點(diǎn)并設(shè)定偏移量 輸出隔板下半部分連線情況枚舉隔板上半部分在目標(biāo)點(diǎn)之后的

32、已配對(duì)點(diǎn)輸出凸起的一段折線輸出折線的最后一段Research for National Training Team of China, IOI2009總結(jié)模擬能帶給人的思考可能還不止這些，但是我已經(jīng)能夠感受其中的力量，不僅是在 OI 學(xué)習(xí)中，還滲透在生活的各個(gè)角落。對(duì)于后者，也不再具體展開了。回顧一下本文的全部內(nèi)容吧：在OI 學(xué)習(xí)中，由模擬得到的最多的思考就在于本文所提的三個(gè)方面：注意細(xì)節(jié)、優(yōu)化算法、重新思考。而這面都是為了更好地解決問題注意細(xì)節(jié)，讓問題的解決更全面；優(yōu)化算法，使程序運(yùn)行效率和程序員的工作效率有所提高；重新思考，助思維敏捷、并提高時(shí)間利用率。不過這些內(nèi)容，還是要基于平時(shí)的努力和

33、自身的修養(yǎng)，都不是瞬間能夠養(yǎng)成的。并且，平時(shí)做題和比賽也不一定時(shí)刻都能按照這些內(nèi)容去做的。還需要結(jié)合實(shí)際情況合理安排時(shí)間，抓其重點(diǎn)感謝感謝時(shí)刻關(guān)心親人和辛勤培育老師。感謝鼓勵(lì)并幫助各位朋友。感謝給中國計(jì)算機(jī)學(xué)會(huì)和 IOI2009 中國國家集訓(xùn)隊(duì)。浙江省紹興市第一中學(xué) 董華星二九年三月15 of 23Huaxing DONGProvinceShaoxing Onior High School inResearch for National Training Team of China, IOI2009附錄文件解壓知道，一個(gè)文本文件中的字符數(shù)目越多，文件也就會(huì)越大。為了節(jié)省空間，人們想出了一種又一

34、種壓縮方式，使得文件盡可能的小。的小 C 也想出了一個(gè)壓縮的方法。不過由于能力，他處理的原始文件中是不含有字符“0”至“9”的，同時(shí)也不含有字符“(”和“)”。對(duì)于壓縮碼 P 我們用如下定義，來告訴你它到底表示什么，即將 P 解壓后將是什么：1. P 中沒有數(shù)字也沒有小括號(hào)，表示它自己本身；2. P 格式為 Numb示 ababab；)，表示 P解壓后的內(nèi)容重復(fù) Number 次，例如 3(ab)表3. P 格式為 P1P2P3.PN，表示將 Pi 分別解壓后，按順序連接起來，例如 2(b)c表示 bbc。盡管小 C 發(fā)現(xiàn)被他壓縮后的文件可能會(huì)比原來的大，但是他還是為自己的這感到非常驕傲。他通

35、常都是用自己獨(dú)創(chuàng)的壓縮方法來表示一個(gè)文本文件的內(nèi)容，而且他也常常把已經(jīng)被他壓縮過的文件發(fā)給自己的同伴。雖然，他的同伴并不在意他的這項(xiàng)壓縮方法，但是他們還是希望能夠知道小 C 發(fā)給自己的到底是什么文件，這文件有何用處，原始內(nèi)容是什么。由于小 C 傳給同伴的文件都挺大，所以只好讓你來幫他們把這些文件給解壓了。輸入文件若干字符用于描述小 C 給出的一個(gè)被壓縮的文件內(nèi)容，大小不超過 1KByte。輸出文件若干字符用于描述將文件解壓后的內(nèi)容，不會(huì)超過 1MByte。樣例輸入 1!2( )!樣例輸入 2r2(a4(b)t2(e)樣例輸出 1! !樣例輸出 2rabbbbabbbbtee來源第十四屆青少年信

36、息學(xué)聯(lián)賽 紹興一中模擬賽，作者董華星16 of 23Huaxing DONGProvinceShaoxing Onior High School inResearch for National Training Team of China, IOI2009Numbers to NumbersNumbers in English are written downhe following way (only numbers lessthen 109 are considered). Number abc,def,ghi is written as “abc million def thousand

37、 ghi”. Here “xyz ” means the written down number xyz .he written down number the part “abc million” is omitted if abc = 0 , “def thousand” is omitted if def = 0 , and “ghi ” is omitted if ghi = 0 . If the wholenumber is equal to 0 it is written down as “zero”. Notet words “million” and“thousand” are

38、 singular even if the number of millions or thousands respectively isgreatern one.Numbers under one thousand are written downhe following way. The numberxyz is written as “xdred and yz . Here “xdred and” is omitted if x = 0 . Notet “dred” is also always singular.Numbers under 20 are written down as

39、“zero”, “one”, “two”, “three”, “four”, “five”, “six”, “seven”, “eight”, “nine”, “ten”, “eleven”, “twelve”, “thirteen”, “fourteen”, “fifteen”, “sixteen”, “seventeen”, “eighteen”, and “nineteen” respectively.Numbers from 20 to 99 are written downhe following way. Number xy is writtenas “x0 y ”, and nu

40、mbers divisiby ten are written as “twenty”, “thirty”, “forty”,“fifty”, “sixty”, “seventy”, “eighty”, and “ninety” respectively.For exle, number 987,654,312 is written down as “ninedred and eightyseven million six 100,000,037 as “onedred and fifty four thousand threedred and twelve”, numberdred milli

41、on thirty seven”, number 1,000 as “one thousand”.Notet “one” is never omitted for millions, thousands anddreds.Given English text will numbers written as words, transform it to the textwhere all numbers are written as numbers. For exle, the text “he had onedredand ninety five dogs” must be tranforme

42、d to “he had 195 dogs”. You must perform atransformation in such a wayt as many words assible are transformed tonumbers, so, for ex thousand”.le, “three thousand” must be transformed to “3000”, not to “3If there are several way to perform the transformation in such a way, you must doit sot thenumber

43、 is as great assible, for exle “two thousand thirtytwo” must be transformed to “2032”, not “2030 2”. If there are still several ways, ize the second number, and so on.InputThere are mutilple caseshe input file.Each case contains an English textt only contains English letters, punctuationmarks (, .,

44、!, ?, :, ;, (, ), and bls (spaand line feeds).You must perform the transformationhe way described. Words in numbers tobe transformed are separated with bls only (so, for exle, “thirty, three” mayonly be transformed as “30, 3”, not as “33”).When performing transformation you must replace characters s

45、tarting from theletter of thewordhe number to the last onehe last word with digits.17 of 23Huaxing DONGProvinceShaoxing Onior High School inResearch for National Training Team of China, IOI2009Input file is not empty and its size does not exceed 20000 bytes. There is an empty line after each case.Ou

46、tputOutput the result of the transformation.There should be an empty line after each case.SlutFrom three thousand one from one thousand fourdred and fifty teamecteddred and eleven universitiesin seventy five countries competing at onedred andtwenty seven sites anddreds more competing atpreliminary c

47、ontests worldwide, seventy three teams of students competed for bragging rights and prizesat The Twenty Eighnnual ACMernational CollegiateProgramming Contest World Finals sponsored by IBM on March Thirty One, Two Thousand Four, and hosted at thei Dum, Prague by Czech Technicale Outputiversity in Pra

48、gue.SFrom 3150 teamectedfrom 1411 universitiesin 75 countries competing at 127 sites and preliminary contests worldwide, 73 teamsdreds more competing atof students competed for bragging rights and prizesat The 20 Eighnnual ACMernational CollegiateProgramming Contest World Finals sponsored by IBM on

49、March 31, 2004, and hosted at thei Dum, Prague by Czech Technicaiversity in Prague.SourceZOJ2698, Andrew Sevichs Contest #918 of 23Huaxing DONGProvinceShaoxing Onior High School inResearch for National Training Team of China, IOI2009跳動(dòng)的水珠廣場(chǎng)的夜晚并不寧靜漆黑，蜂擁而至的人們?cè)绫荒菚r(shí)高時(shí)低，再伴上點(diǎn)輕盈的音樂，點(diǎn)綴些多彩的夜燈，的噴泉所著迷。水柱、浪漫，全都彌

50、漫在這濕潤的空氣中。留戀于此的人們多想在家就擁有這精神的盛宴。于是，一種擁有著跳動(dòng)的水珠的音樂盒被設(shè)計(jì)誕生了。音樂盒最關(guān)鍵的設(shè)計(jì)當(dāng)然是在那水珠。不過設(shè)計(jì)者們已經(jīng)有所打算，他們希望設(shè)計(jì)一個(gè) N*M大小的音樂盒，而它恰好被分成了 N行 M列相同大小的單元。每個(gè)單元都有各自的水珠跳動(dòng)系統(tǒng)，上面所有的水珠都會(huì)按照這個(gè)時(shí)刻所設(shè)進(jìn)行跳躍。指令有五種類型：C、U、D、L、R，分別表示這個(gè)位定的置上將出現(xiàn) X粒新的水珠，這個(gè)位置上的水珠將跳到上一個(gè)單元、下一個(gè)單元、左一個(gè)單元、右一個(gè)單元，如果水珠跳出了音樂盒，它將被裝在音樂盒上的特殊裝置回收。而且要注意的是，任意水珠之間都是互不影響的。例如下面這個(gè)指令 C

51、只能產(chǎn)生 1 粒水珠，大小 2*2 的音樂盒：時(shí)刻 1 到時(shí)刻 2，原本在左上的水珠跳到了左下，原本在左下的水珠跳到了右下，而原本沒水珠的右下新出現(xiàn)一粒水珠，最后左下有一粒水珠而右下有兩粒。00CU10DU00CL1010RC12CD2000CU時(shí)刻 0時(shí)刻 1時(shí)刻 2時(shí)刻 3指令注：每個(gè)時(shí)刻左邊的是當(dāng)時(shí)每個(gè)單元上的水珠數(shù)目，右邊的是當(dāng)時(shí)的音樂盒啟動(dòng)時(shí)，每個(gè)單元上都沒有水珠，所有的單元都執(zhí)行各自設(shè)置的第一個(gè)指令，每 L個(gè)為一個(gè)循環(huán)。系統(tǒng)中不過音樂盒每個(gè)單元上能夠存在的水珠個(gè)數(shù)也是有限的，如果某個(gè)單元上的水珠數(shù)目一旦超過或恰好為 P，則通過音樂盒的特殊裝置，水珠瞬間會(huì)減少 P 粒 。這樣，音樂盒

52、的每個(gè)單元可以始終保持在 P粒水珠之內(nèi)，也可以保證整個(gè)音樂盒不需要無限多的水來維持其正常工作。音樂盒設(shè)計(jì)者希望在設(shè)計(jì)之初能夠確定某個(gè)音樂盒在啟動(dòng)（時(shí)刻 0）后的時(shí)刻 T的狀態(tài)，這也便是你的任務(wù)。對(duì)于音樂盒的任意一行，用一個(gè) PQ 序列“P1 Q1 P2 Q2Pk Qk”來描述其時(shí)刻 T 的狀態(tài)，表示這一行的狀態(tài)先是 P1個(gè) Q1， 再是 P2個(gè) Q2最后是 Pk個(gè) Qk。當(dāng)然，這里Pi=M，Pi0，PiPi+1。輸入文件第一行五個(gè)正整數(shù) N，M，X，P和 T，分別表示音樂盒相關(guān)參數(shù)，以及你所 求的時(shí)刻 T。相鄰數(shù)字之間由一個(gè)空格隔開。接下來 N行，每行 M項(xiàng)內(nèi)容，相鄰兩項(xiàng)之間有一個(gè)空格。每項(xiàng)內(nèi)

53、容先是一個(gè)整數(shù)Li,j表示音樂盒至上而下第i行，從左往右第j列的指令的循環(huán)節(jié)長度 ，然后是長度為 Li,j的一個(gè)由 C、U、D、L、R 組成的字符串，描述指令序列的循環(huán)節(jié)，其中串的第一個(gè)字符是時(shí)刻 0 時(shí)那一個(gè)單元對(duì)應(yīng)的指令。Li,j和串之間由一個(gè)空格隔開。輸出文件共 N行，每行一個(gè)PQ 序列來描述這一行對(duì)應(yīng)的狀態(tài)，相鄰兩個(gè)數(shù)用一個(gè)空格隔開。樣例輸入樣例輸出19 of 23Huaxing DONGProvinceShaoxing Onior High School inResearch for National Training Team of China, IOI20092 2 1 100

54、33 CDC 3 UUL3 CRC 7 UCDLULL數(shù)據(jù)范圍1 1 1 01 2 1 0對(duì)于 60%的數(shù)據(jù)，保證 N,M8 且 T104； 對(duì)于 80%的數(shù)據(jù)，保證 N,M8 且 T109； 對(duì)于 50%的數(shù)據(jù)，保證所有的 Lij都相等；對(duì)于 100%的數(shù)據(jù)，保證 2N,M100，X,P,T109，Li,j是集合3,7,9中的一個(gè) ， 且擁有指令 C 的單元不超過 20 個(gè)（例如，樣例擁有 3 個(gè)）。解題第一部分其實(shí)原來輸出的是 N*M的數(shù)字矩陣，但似乎 Vijos 對(duì)于輸出文件比較大的評(píng)測(cè)會(huì)出問題，所以改了個(gè)輸出方式。即可。第二部分把 N*M的數(shù)字矩陣求出來后稍加處理直接按照題目內(nèi)容，一秒

55、一秒地模擬。時(shí)間復(fù)雜度 O(NMT)期望得分 3040第三部分對(duì)每一時(shí)刻水的去向建一張圖論中常用的鄰接矩陣，看看有沒的發(fā)現(xiàn)。新對(duì)矩陣的所有位置標(biāo)號(hào)為 1 至 NM，建一張(NM+1)*(NM+1)的二維表Link，用來表示水的去于某一時(shí)刻內(nèi)，如果標(biāo)號(hào)為 i位置的水珠會(huì)跳到標(biāo)號(hào)為 j位置，則設(shè) Linki,j為 1；并且再設(shè)一個(gè)標(biāo)號(hào)為 NM+1 的位置，這里表示水珠的產(chǎn)生地，對(duì)于所有會(huì)產(chǎn)生水珠的位置 k，設(shè) LinkNM+1,k為 1；另外特別的，LinkNM+1,NM+1也為 1，其他位置都是 0。比如樣例時(shí)刻 2 內(nèi)的 Link 可以這樣寫：12對(duì)于初始局面，建一張長為 NM+1 的二維表

56、Opt，表示每個(gè)位置初始的水珠數(shù)。故，OptNM+1為 X（這里的 X即指令 C 一次產(chǎn)生的水珠量），其余位 置都是 0。若用 Opti表示時(shí)刻 i時(shí)的局面（即初始局面為 Opt0）， 用 Linki表示時(shí) 刻 i內(nèi)的水的去向，則 Optn=Opt0*Link1*Link2*.*Linkn。這一步即矩陣乘法。雖然每個(gè)時(shí)刻的 Link不一定相同，但是發(fā)現(xiàn) Link是循環(huán)著的。因?yàn)閱栴}中矩陣每個(gè)位置的循環(huán)指令是循環(huán)著的，設(shè) Lcm是所有 Li,j的最小公倍數(shù)，所以 Link每 Lcm個(gè)成一個(gè)循環(huán)。設(shè) Link=Link1*Link2*.*LinkLcm，則：Optn=Opt0*Linktrunc(

57、n/Lcm)*Linktrunc(n/Lcm)*Lcm+1*Linktrunc(n/Lcm)*Lcm+2*.*Linkn。而這里，求 Linktrunc(n/Lcm)時(shí)可以使用快速冪，從而提高效率，但是需要一定的數(shù)學(xué)基礎(chǔ)。時(shí)間復(fù)雜度 O(NM)3log2T期望得分 407020 of 23Huaxing DONGProvinceShaoxing Onior High School in0010000000000100001000010Research for National Training Team of China, IOI2009第四部分再仔細(xì)分析題目，可以發(fā)現(xiàn)，原本在某個(gè)位置上的水珠

58、，經(jīng)過一定時(shí)間后它們所去的目的地是唯一的、確定的，除非已經(jīng)走出了大矩陣，因?yàn)槿我晃恢迷谌我鈺r(shí)刻它的略（詳見本是唯一的。）是否可以利用這一點(diǎn)？這個(gè)做法不需要像第二部分一樣還得熟悉矩陣乘法，只要將常用的模擬加以改進(jìn)即可。時(shí)間復(fù)雜度 O(NMlog2T)期望得分 80100第五部分試題中有一個(gè)條件是“擁有指令 C 的單元不超過 20 個(gè)”，在上述算法中并沒有使用，不知道對(duì)于大家解這個(gè)題是否有幫助。希望大家能夠想出補(bǔ)充解決這道題目的好算法。針對(duì)第五部分內(nèi)容，確實(shí)有人利用了這一標(biāo)程沒有使用的條件，應(yīng)該可以通過在高效信息學(xué)評(píng)測(cè)系統(tǒng)（Velocious Informatics Judge Online Sy

59、stem，簡稱Vijos）上交流得到。來源首屆海峽青少年程序設(shè)計(jì)競(jìng)賽大陸邀請(qǐng)賽，作者董華星21 of 23Huaxing DONGProvinceShaoxing Onior High School inResearch for National Training Team of China, IOI2009Chip DesigningDesigning computer chips is quite difficult. Recently Peter has decided to get ajob in Karelia Quaterconductors companyt is going t

60、o produce chips for new EBMprosor. As a qualifying work for theition he has goask of designing a layoutfor a very simple chip. A chip has n inputs and n outputs, located in po 0) , , (n-1, 0) and (0, 1) , (1, 1) , , (n-1, 1) respectively (all dimen course, in nanometers).s (0, 0) , (1,s are, ofhis c