《noip模擬總結(jié)》PPT課件.ppt

1、模擬,by windfinder,模擬綜述,試題描述中是怎么做的，程序就模擬怎么做，該進(jìn)時進(jìn)，該退時退，須記錄時就記錄（變量賦值）。選擇合適的數(shù)據(jù)結(jié)構(gòu)如標(biāo)記變量（或者數(shù)組）、棧、隊列、樹等，這樣才能方便程序的實現(xiàn)，數(shù)據(jù)清晰，不該有的交叉絕對不能有，正如數(shù)學(xué)上函數(shù)的對應(yīng)關(guān)系一樣，f(x)對于某一個x有一個唯一確定的值與它對應(yīng)。,Noip中的模擬,前幾年的NOIP復(fù)賽第一題基本上都可以通過模擬或者再結(jié)合其它的一些基本算法就可以完成。如NOIP2010第一道題. 某道題如果你不能確定套用什么典型算法來實現(xiàn)，那么你就模擬吧！,模擬分類,模擬： 分為三類： 普通模擬（完全模擬的較少，大多為結(jié)合貪心 。排

2、序的，貪心 。 排序的不單獨討論） 歷屆試題：NOIP多項式輸出數(shù)列 NOIP 多項式輸出.： 多項式輸出:這道題想要拿分很容易，但要注意一下模擬過程，此題實際上需有4個判段過程，其中有一個是極易遺漏的。 數(shù)列:這道題竟是第4題,很簡單的模擬題,還可用轉(zhuǎn)成2進(jìn)制的方式直接算. 字符模擬 歷屆試題：NOIP ISBN號碼 Jam記數(shù)法 立體圖 ISBN號碼: 總體難度不大，這道題如果是使用C語言的話，可以用 每個字符都減去字符0 的方式，直接把它們從字符轉(zhuǎn)為數(shù)字,再進(jìn)行處理。 Jam記數(shù)法:很絕對的模擬,一開始我還認(rèn)為是數(shù)學(xué)知識模擬題,就是從后往前推. 立體圖:很難的很考細(xì)心的一道模擬題,沒說的

3、,就是上機(jī)不斷的調(diào)程序. 數(shù)學(xué)知識模擬 歷屆試題：NOIP 細(xì)胞分裂 初中組目前唯一一道數(shù)學(xué)知識模擬題，掌握了相關(guān)的知識就應(yīng)該不難，這道題要滿分還是比較難的，需要高精度運(yùn)算（用LONG LONG 型不知道可不可以）,還有一定要注意時間問題,這道題極易超時.,小試牛刀,學(xué)校里有一個水房，水房里一共裝有m 個龍頭可供同學(xué)們打開水，每個龍頭每秒鐘的供水量相等，均為1。現(xiàn)在有n 名同學(xué)準(zhǔn)備接水，他們的初始接水順序已經(jīng)確定。將這些同學(xué)按接水順序從1到n 編號，i 號同學(xué)的接水量為wi。接水開始時，1 到m 號同學(xué)各占一個水龍頭，并同時打開水龍頭接水。當(dāng)其中某名同學(xué)j 完成其接水量要求wj 后，下一名排隊

4、等候接水的同學(xué)k馬上接替j 同學(xué)的位置開始接水。這個換人的過程是瞬間完成的，且沒有任何水的浪費。即j 同學(xué)第x 秒結(jié)束時完成接水，則k 同學(xué)第x+1 秒立刻開始接水。若當(dāng)前接水人數(shù)n不足m，則只有n個龍頭供水，其它m；n個龍頭關(guān)閉。現(xiàn)在給出n 名同學(xué)的接水量，按照上述接水規(guī)則，問所有同學(xué)都接完水需要多少秒。 輸入格式 第1 行2 個整數(shù)n 和m，用一個空格隔開，分別表示接水人數(shù)和龍頭個數(shù)。第2 行n 個整數(shù)w1、w2、wn，每兩個整數(shù)之間用一個空格隔開，wi 表示i 號同學(xué)的接水量。 輸出格式 輸出只有一行，1 個整數(shù)，表示接水所需的總時間 樣例輸入 【輸入輸出樣例1】 5 3 4 4 1 2

5、 1 【輸入輸出樣例1】 4,此題巨水無比把所有人 按順序塞入當(dāng)前時間最短的那個水龍頭 最后找時間最長的水龍頭就行了優(yōu)化 前M個人直接塞入M個水龍頭中預(yù)計得分 AC實際得分 AC程序復(fù)雜度 0程序長度 低 另： 此題不是貪心，切忌貪心,普通模擬,一元 n 次多項式可用如下的表達(dá)式表示： 其中，a_ixi 稱為i次項，a_i稱為i 次項的系數(shù)。給出一個一元多項式各項的次數(shù)和系數(shù)，請按照如下規(guī)定的格式要求輸出該多項式：1. 多項式中自變量為x，從左到右按照次數(shù)遞減順序給出多項式。2. 多項式中只包含系數(shù)不為0 的項。3. 如果多項式n 次項系數(shù)為正，則多項式開頭不出現(xiàn)“+”號，如果多項式n 次項系

6、數(shù)為負(fù)，則多項式以“-”號開頭。4. 對于不是最高次的項，以“+”號或者“-”號連接此項與前一項，分別表示此項系數(shù)為正或者系數(shù)為負(fù)。緊跟一個正整數(shù)，表示此項系數(shù)的絕對值（如果一個高于0 次的項，其系數(shù)的絕對值為1，則無需輸出1）。如果x 的指數(shù)大于1，則接下來緊跟的指數(shù)部分的形式為“xb”，其中b 為x 的指數(shù)；如果x 的指數(shù)為1，則接下來緊跟的指數(shù)部分形式為“x”；如果x 的指數(shù)為0，則僅需輸出系數(shù)即可。5. 多項式中，多項式的開頭、結(jié)尾不含多余的空格。【數(shù)據(jù)范圍】1 n 100，多項式各次項系數(shù)的絕對值均不超過100。 輸入格式 共有2 行。第一行 1 個整數(shù)，n，表示一元多項式的次數(shù)。第

7、二行有 n+1 個整數(shù)，其中第i 個整數(shù)表示第n-i+1 次項的系數(shù)，每兩個整數(shù)之間用空 輸出格式 共1 行，按題目所述格式輸出多項式。 輸入格式 共有2 行。第一行 1 個整數(shù)，n，表示一元多項式的次數(shù)。第二行有 n+1 個整數(shù)，其中第i 個整數(shù)表示第n-i+1 次項的系數(shù)，每兩個整數(shù)之間用空 輸出格式 共1 行，按題目所述格式輸出多項式。 【輸入樣例1】 5 100 -1 1 -3 0 10 【輸出樣例1】 100 x5-x4+x3-3x2+10,字符模擬：,ISBN號碼【問題描述】每一本正式出版的圖書都有一個ISBN號碼與之對應(yīng)，ISBN碼包括9位數(shù)字、1位識別碼和3位分隔符，其規(guī)定格式

8、如“x-xxx-xxxxx-x”，其中符號“-”是分隔符（鍵盤上的減號），最后一位是識別碼，例如0-670-82162-4就是一個標(biāo)準(zhǔn)的ISBN碼。ISBN碼的首位數(shù)字表示書籍的出版語言，例如0代表英語；第一個分隔符“-”之后的三位數(shù)字代表出版社，例如670代表維京出版社；第二個分隔之后的五位數(shù)字代表該書在出版社的編號；最后一位為識別碼。識別碼的計算方法如下：首位數(shù)字乘以1加上次位數(shù)字乘以2以此類推，用所得的結(jié)果mod 11，所得的余數(shù)即為識別碼，如果余數(shù)為10，則識別碼為大寫字母X。例如ISBN號碼0-670-82162-4中的識別碼4是這樣得到的：對067082162這9個數(shù)字，從左至右，

9、分別乘以1，2，9，再求和，即01+62+29=158，然后取158 mod 11的結(jié)果4作為識別碼。你的任務(wù)是編寫程序判斷輸入的ISBN號碼中識別碼是否正確，如果正確，則僅輸出“Right”；如果錯誤，則輸出你認(rèn)為是正確的ISBN號碼?！据斎搿枯斎胛募sbn.in只有一行，是一個字符序列，表示一本書的ISBN號碼（保證輸入符合ISBN號碼的格式要求）。【輸出】輸出文件isbn.out共一行，假如輸入的ISBN號碼的識別碼正確，那么輸出“Right”，否則，按照規(guī)定的格式，輸出正確的ISBN號碼（包括分隔符“-”）?！咎貏e說明】輸出文件最后會多一個空行。【輸入輸出樣例1】isbn.in0-6

10、70-82162-4isbn.outRight【輸入輸出樣例2】isbn.in：0-670-82162-0isbn.out：0-670-82162-4,ISBN號碼 解題思路：本題主要考查基本編程能力。數(shù)組 char isbn20 用來保存輸入的ISBN號碼，可將輸入數(shù)據(jù)以字符串的方式讀入數(shù)組isbn中。ISBN號碼共有13位，存放在數(shù)組下標(biāo)為012的元素中，其中isbn12是識別碼，本題需驗證這一位是否正確。根據(jù)ASCII碼將isbn數(shù)組中的規(guī)定位上字符轉(zhuǎn)換成數(shù)字，然后根據(jù)識別碼公式計算出正確的識別碼，并與isbn12中字符進(jìn)行比較。識別碼計算公式如下：（ (isbn0-0)+(isbn2-

11、0)*2+(isbn3-0)*3+(isbn4-0)*4+(isbn6-0)*5+(isbn7-0)*6+(isbn8-0)*7+(isbn9-0)*8+(isbn10-0)*9 ）%11,核心代碼如下：char isbn20; int idCode=0; cin isbn;/以字符串的形式讀入isbn碼到數(shù)組isbn中idCode = (isbn0-0)+(isbn2-0)*2+(isbn3-0)*3+(isbn4-0)*4+(isbn6-0)*5+(isbn7-0)*6+(isbn8-0)*7+(isbn9-0)*8+(isbn10-0)*9; idCode = idCode%11;/計算

12、識別碼if (idCode10)if ( isbn12 = idCode+0 )/識別碼正確cout Right endl;else/識別碼不正確isbn12 = idCode+0;cout isbn endl;else if (isbn12 = X)/識別碼正確cout Right endl;else/識別碼不正確isbn12 = X;cout isbn endl;,數(shù)學(xué)模擬：,描述Hanks 博士是BT (Bio-Tech，生物技術(shù)) 領(lǐng)域的知名專家?，F(xiàn)在，他正在為一個細(xì)胞實驗做準(zhǔn)備工作：培養(yǎng)細(xì)胞樣本。Hanks 博士手里現(xiàn)在有N 種細(xì)胞，編號從1N，一個第i 種細(xì)胞經(jīng)過1 秒鐘可以分裂為

13、Si 個同種細(xì)胞（Si 為正整數(shù)）。現(xiàn)在他需要選取某種細(xì)胞的一個放進(jìn)培養(yǎng)皿，讓其自由分裂，進(jìn)行培養(yǎng)。一段時間以后，再把培養(yǎng)皿中的所有細(xì)胞平均分入M 個試管，形成M 份樣本，用于實驗。Hanks 博士的試管數(shù)M 很大，普通的計算機(jī)的基本數(shù)據(jù)類型無法存儲這樣大的M 值，但萬幸的是，M 總可以表示為m1 的m2 次方，即M = m1m2 ，其中m1，m2 均為基本數(shù)據(jù)類型可以存儲的正整數(shù)。注意，整個實驗過程中不允許分割單個細(xì)胞，比如某個時刻若培養(yǎng)皿中有4 個細(xì)胞，Hanks 博士可以把它們分入2 個試管，每試管內(nèi)2 個，然后開始實驗。但如果培養(yǎng)皿中有5個細(xì)胞，博士就無法將它們均分入2 個試管。此時，

14、博士就只能等待一段時間，讓細(xì)胞們繼續(xù)分裂，使得其個數(shù)可以均分，或是干脆改換另一種細(xì)胞培養(yǎng)。為了能讓實驗盡早開始，Hanks 博士在選定一種細(xì)胞開始培養(yǎng)后，總是在得到的細(xì)胞“剛好可以平均分入M 個試管”時停止細(xì)胞培養(yǎng)并開始實驗?，F(xiàn)在博士希望知道，選擇哪種細(xì)胞培養(yǎng)，可以使得實驗的開始時間最早。 輸入格式輸入文件名為 cell.in，共有三行。第一行有一個正整數(shù) N，代表細(xì)胞種數(shù)。第二行有兩個正整數(shù) m1，m2，以一個空格隔開，m1m2即表示試管的總數(shù)M。第三行有 N 個正整數(shù)，第i 個數(shù)Si 表示第i 種細(xì)胞經(jīng)過1 秒鐘可以分裂成同種細(xì)胞的個數(shù)。輸出格式輸出文件 cell.out 共一行，為一個整

15、數(shù)，表示從開始培養(yǎng)細(xì)胞到實驗?zāi)軌蜷_始所經(jīng)過的最少時間（單位為秒）。 如果無論 Hanks 博士選擇哪種細(xì)胞都不能滿足要求，則輸出整數(shù)-1。 樣例輸入112 13 樣例輸出1-1 輸入輸出樣例1 說明：經(jīng)過 1 秒鐘，細(xì)胞分裂成3 個，經(jīng)過2 秒鐘，細(xì)胞分裂成9 個，可以看出無論怎么分裂，細(xì)胞的個數(shù)都是奇數(shù)，因此永遠(yuǎn)不能分入2 個試管。 樣例輸入 2224 130 12 樣例輸出 22 輸入輸出樣例2 說明：第 1 種細(xì)胞最早在3 秒后才能均分入24 個試管，而第2 種最早在2 秒后就可以均分（每試管144/(241)=6 個）。故實驗最早可以在2 秒后開始。 數(shù)據(jù)范圍 對于 50%的數(shù)據(jù)，有m

16、1m2 30000。 對于所有的數(shù)據(jù)，有1 N 10000，1 m1 30000，1 m2 10000，1 Si 2,000,000,000。,總的來說就算是 分解質(zhì)因數(shù) 由于m1=30000,m2=10000，根本無法直接計算，所以需要 通過數(shù)學(xué)分析得出答案。如果一個數(shù)能夠整除另一個數(shù)，那么這個數(shù)因數(shù)分解后一定有另一個數(shù)所有的元素，且每個元素個數(shù)均大于等于另一個數(shù)相同元素的個數(shù)。因此我們可以先對m1進(jìn)行因數(shù)分解，并將對應(yīng)元素的個數(shù)乘以m2。之后讀入每個數(shù)，判斷該數(shù)因數(shù)分解后是否有m1中所有的元素。如果有的話，則計算該細(xì)胞最大的分裂次數(shù)，即對應(yīng)m1種元素個數(shù)/si中元素個數(shù)后向上取整。最后更新

17、答案即可。 注意因數(shù)分解中1比較特殊，所以要單獨判斷一下。,1機(jī)器翻譯(translate.pas/c/cpp)【問題描述】小晨的電腦上安裝了一個機(jī)器翻譯軟件，他經(jīng)常用這個軟件來翻譯英語文章。這個翻譯軟件的原理很簡單，它只是從頭到尾，依次將每個英文單詞用對應(yīng)的中文含義來替換。對于每個英文單詞，軟件會先在內(nèi)存中查找這個單詞的中文含義，如果內(nèi)存中有，軟件就會用它進(jìn)行翻譯；如果內(nèi)存中沒有，軟件就會在外存中的詞典內(nèi)查找，查出單詞的中文含義然后翻譯，并將這個單詞和譯義放入內(nèi)存，以備后續(xù)的查找和翻譯。假設(shè)內(nèi)存中有M 個單元，每單元能存放一個單詞和譯義。每當(dāng)軟件將一個新單詞存入內(nèi)存前，如果當(dāng)前內(nèi)存中已存入的

18、單詞數(shù)不超過M1，軟件會將新單詞存入一個未使用的內(nèi)存單元；若內(nèi)存中已存入M 個單詞，軟件會清空最早進(jìn)入內(nèi)存的那個單詞，騰出單元來，存放新單詞。假設(shè)一篇英語文章的長度為N 個單詞。給定這篇待譯文章，翻譯軟件需要去外存查找多少次詞典？假設(shè)在翻譯開始前，內(nèi)存中沒有任何單詞?！据斎搿枯斎胛募麨閠ranslate.in，輸入文件共2 行。每行中兩個數(shù)之間用一個空格隔開。第一行為兩個正整數(shù)M 和N，代表內(nèi)存容量和文章的長度。第二行為N 個非負(fù)整數(shù)，按照文章的順序，每個數(shù)（大小不超過1000）代表一個英文單詞。文章中兩個單詞是同一個單詞，當(dāng)且僅當(dāng)它們對應(yīng)的非負(fù)整數(shù)相同?！据敵觥枯敵鑫募ranslate.out 共1 行，包含一個整數(shù)，為軟件需要查詞典的次數(shù)?！据斎胼敵鰳永?】3 71 2 1 5 4 4 15【輸入輸出樣例 1 說