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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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