全國賽09.集訓(xùn)隊(duì)試題

1、-青少年信息學(xué)中國國家隊(duì)訓(xùn)練2010-2011競賽時(shí)間：待定提交源程序須加后綴注意：最終測試時(shí)，所有編譯命令均不打開任何優(yōu)化開關(guān)。對于 Pascal 語言stock.pascolor.pasequation.pas對于 C語言stock.ccolor.cequation.c對于 C+ 語言stock.cppcolor.cppequation.cpp題目名稱的數(shù)顏色的等式目錄stockcolorequation可執(zhí)行文件名stockcolorequation輸入文件名標(biāo)準(zhǔn)輸入標(biāo)準(zhǔn)輸入標(biāo)準(zhǔn)輸入輸出文件名標(biāo)準(zhǔn)輸出標(biāo)準(zhǔn)輸出標(biāo)準(zhǔn)輸出每個(gè)測試點(diǎn)時(shí)限1s0.6s1s測試點(diǎn)數(shù)目202020每個(gè)測試點(diǎn)分值555

2、是否有部分分N/AN/AN/A題目類型傳統(tǒng)型傳統(tǒng)型傳統(tǒng)型的【問題描述】的熱愛炒股，她要求為她編寫一個(gè)軟件，的走勢。折線圖是具，它通過一張時(shí)間與數(shù)圖像清晰地展示了 經(jīng)過長時(shí)間的觀測，某只未來的必備工的價(jià)位的函 的走勢情況。發(fā)現(xiàn)很多都有如下的規(guī)律：之前的走勢很可能在短時(shí)間內(nèi)重現(xiàn)！如圖可以看到這只A 部分的股價(jià)和 C 部分的股價(jià)的走勢如出一轍。通過這個(gè)觀測，認(rèn)為他可，他本能找到了一個(gè)未來走勢的方法。進(jìn)一步的難住了想試圖統(tǒng)計(jì) B 部分的長度與發(fā)生這種情況的概率關(guān)系，不過由于數(shù)據(jù)量過于龐大，依賴人腦的力量難以完成，于是找到了編程的你，請你幫他找一找給定重現(xiàn)的間隔（B 部分的長度），有多少個(gè)時(shí)間段滿足首尾

3、部分的走勢完全相同呢？當(dāng)然，首尾部分的長度不能為零?！据斎敫袷健枯斎氲牡谝恍邪瑑蓚€(gè)整數(shù) N、M，分別表示需要統(tǒng)計(jì)的總時(shí)間以及重現(xiàn)的間隔（B 部分的長度）。接下來 N 行，每行一個(gè)整數(shù)，代表每一個(gè)時(shí)間點(diǎn)的股價(jià)。【輸出格式】輸出一個(gè)整數(shù)，表示滿足條件的時(shí)間段的個(gè)數(shù)【樣例輸入】12 41 2 3 4 8 9 1 2 3 4 8 9【樣例輸出】6【樣例說明】6 個(gè)時(shí)間段分別是：3-9、2-10、2-8、1-9、3-11、4-12。【數(shù)據(jù)規(guī)?！繉τ?20%的數(shù)據(jù)， 4N100。對于 40%的數(shù)據(jù)， 4N5000。對于 100%的數(shù)據(jù)，4N50000 1M10 MN 所有出現(xiàn)的整數(shù)均不超過 32 位含符

4、號整數(shù)。時(shí)間限制：1s【解題】題目大意：給定一個(gè)由整數(shù)組成的序列，求出滿足下列要求的（連續(xù)）子序列的個(gè)數(shù)。1、子序列由 ABC 三個(gè)相鄰部分組成。2、A 部分的長度與 C 部分相等。3、對于 A 部分中任意相鄰兩項(xiàng)的差與 C 部分中任意相鄰兩項(xiàng)的差相等4、B 部分的長度給定，但是很?。ㄐ∮诘扔?10）本題乍看起來直接按題目描述處理顯然較不清晰，可以把原串修改一下。為了描述方便，不妨把原序列稱之為 S1，S2SN。將每一項(xiàng)減去前一項(xiàng)，可以得到 S2-S1，S3-S2SN-SN-1。可以稱為序列SN。那么原題就轉(zhuǎn)換成了求新序列SN中滿足形式類似與 PQP 的子序列的個(gè)數(shù)，并且|Q|的給定。做完了這

5、個(gè)轉(zhuǎn)換工作，乍看之下問題似乎還是難以解決，下面介紹幾個(gè)此題的做法，分別可以得到不同的分?jǐn)?shù)。方法 1：看到這個(gè)形式的問題第一反應(yīng)就是首先枚舉 Q 的位置，然后再枚舉 P 的長度，然后檢查然后檢查對應(yīng)位置是否匹配。這種做法非常直觀，不過時(shí)間效率較低，情況下為 O(N3)，期望得分 20 分。方法 2：方法一十分低效因?yàn)樗隽肆嗽S多無用功。對于一中第三步的檢查對應(yīng)位置是否匹配，有許多現(xiàn)成的算法可以使用。很容易可以看出，這個(gè)過程的本質(zhì)就是在計(jì)算 P2 與 P1 每一個(gè)位置的的 LCP（最長公共前綴）！這個(gè)過程很容易可以使用后綴數(shù)組優(yōu)化而做到詢問 O(1)回答。不過由于需要枚舉 Q 的位置和 P 的長度

6、，時(shí)間復(fù)雜度仍然只能達(dá)到 O(N2)。這樣可以使用 O(N2)的動(dòng)態(tài)規(guī)劃來代替后綴數(shù)組來優(yōu)化編程復(fù)雜度。期望得分 4050 分。方法 3：方法 2 的瓶頸是枚舉 P 的長度與 Q 的位置，不過按照這個(gè)思路繼續(xù)下去似乎難以優(yōu)化掉這兩重循環(huán)，不得不另尋更為巧妙的方法。對于這種性序列上的組合計(jì)數(shù)問題，很容易想到一個(gè)工具：分治！。分治算法在形如快速排序等地方能順利優(yōu)化算法，嘗試將其運(yùn)用至本題中。不妨設(shè)過程 F(Left,Right)可以統(tǒng)計(jì)在區(qū)間Left,Right中滿足條件的子序列的個(gè)數(shù)。設(shè)Mid 為區(qū)間Left,Right的中點(diǎn)由于分治執(zhí)行，Left,Mid,Mid+1,Right中的子序列，剩下

7、的不需要統(tǒng)計(jì)那些屬于分兩種情況。1、點(diǎn) MidQ。這種情況由于|Q|非常小，可以直接枚舉 Q 的位置，然后使用方法 2 中的算法解決這個(gè)問題，此時(shí)算法多了一個(gè)系數(shù) M，不過整體仍然可以在 O(NMLogN)的復(fù)雜度內(nèi)完成。點(diǎn) MidQ，這種情況就比較麻煩了，可以表示成如下示意圖：2、由于 Mid 的存在，P2 被分割成了 3 份，由于 P1=P2，把 P1也分割成 3 份，經(jīng)過仔細(xì)觀察，發(fā)現(xiàn)只需要枚舉紅線的位置即可解決此部分的統(tǒng)計(jì)問題。黃色部分的最大匹配值可以通過將整個(gè) Mid 左面的部分倒置后求 LCP。而 Mid 以及綠色部分的匹配值可以直接通過后綴數(shù)組+RMQ 求的。知道了綠色與黃色部分

8、的最大值后，那么 Q 的位置個(gè)數(shù)也可以相應(yīng)得出，問題得到解決，此部分復(fù)雜度為 O(NLogN)。方法三總復(fù)雜度為 O(NMLogN)，為一個(gè)非常優(yōu)秀的算法。由于后綴數(shù)組配合 RMQ 代碼較長，在標(biāo)程中我使用了擴(kuò)展 KMP 算法來代替后綴數(shù)組實(shí)現(xiàn)，而擴(kuò)展 KMP 時(shí)間復(fù)雜度為 O(N)，不影響整體復(fù)雜度。數(shù)顏色【問題描述】了一套 N 支彩色畫筆（其中有些顏色可能相同），擺成一排，你需要回答的提問。會(huì)像你發(fā)布如下指令：1、Q L R 代表詢問你從第 L 支畫筆到第 R 支畫筆筆。2、R P Col 把第 P 支畫筆替換為顏色 Col。有幾種不同顏色的畫為了滿足的要求，你知道你需要干什么了嗎？【輸入

9、格式】第 1 行兩個(gè)整數(shù) N，M，分別代表初始畫筆的數(shù)量以及個(gè)數(shù)。第 2 行 N 個(gè)整數(shù)，分別代表初始畫筆排中第 i 支畫筆的顏色。會(huì)做的事情的第 3 行到第 2+M 行，每行分別代表分。會(huì)做的一件事情，格式見題【輸出格式】對于每一個(gè) Query 的詢問，你需要在對應(yīng)的行中給出一個(gè)數(shù)字，代表第L支畫筆到第 R 支畫筆有幾種不同顏色的畫筆。【樣例輸入】6 51 2 3 4 5 5Q 1 42 61 2Q 1 4Q 2 6【樣例輸出】4434【數(shù)據(jù)規(guī)?！繉τ?40%數(shù)據(jù)，只包含第一類操作（無修改操作），且。除此之外的 20%的數(shù)據(jù)，N，M1000對于 100%的數(shù)據(jù)，N10000，M10000，修

10、改操作不多于 1000 次，所有的輸入數(shù)據(jù)中出現(xiàn)的所有整數(shù)均大于等于 1 且不超過 106。時(shí)間限制：0.6s【解題】題目大意：給定一個(gè)序列，設(shè)計(jì)一種數(shù)據(jù)結(jié)構(gòu)，需要支持：1、修改一個(gè)數(shù)字。2、詢問一個(gè)區(qū)間內(nèi)有多少個(gè)互不相同的數(shù)字。這是一道數(shù)據(jù)結(jié)構(gòu)題，數(shù)據(jù)結(jié)構(gòu)題一般來說代碼量較大，而給分又有明顯的階段性，可以從數(shù)據(jù)規(guī)模處獲得一些解題的想法，下面就此。對于 20%的小數(shù)據(jù)，只要樸素地用數(shù)組來模擬操作就可以了。40%的數(shù)據(jù)：對于原來的序列沒有任何的修改操作，這就給了做數(shù)據(jù)結(jié)構(gòu)題的一些提示：可以離線來回答這些詢問！離線回答詢問的好處就是可以對那些詢問排序?？梢赃@樣思考，一個(gè)出現(xiàn)的權(quán)值為在只要讓在回答每

11、個(gè)詢問時(shí)，詢問的區(qū)間中每種數(shù)1，否則為 0，這樣就可以用線段樹或者樹狀數(shù)組等工具來這個(gè)和，這里我使用的是樹狀數(shù)組。離線的建立事件點(diǎn)：就是這樣，來看看具體如何解決：1、對于原始序列中的每一個(gè)數(shù)，分別建立一個(gè)事件，事件點(diǎn)為這個(gè)數(shù)在序列中的位置，發(fā)生這個(gè)事件時(shí)查詢這個(gè)數(shù)字之前有沒有入過樹狀數(shù)組（將這個(gè)數(shù)所在的位置的權(quán)值+1）。如果相同的數(shù)字之前插入過樹狀數(shù)組，那么2、對于每一個(gè)詢問操作，其刪除（將這個(gè)數(shù)所在的位置的權(quán)值-1） 詢問區(qū)間的末端點(diǎn)作為這個(gè)事件的時(shí)間，然后直接在樹狀數(shù)組中查詢此區(qū)間中所有數(shù)字的和。不難發(fā)現(xiàn)在這個(gè)區(qū)間中，對于相同的數(shù)，只有最后一個(gè)數(shù)字的權(quán)值為 1，其他的權(quán)值都是零。40 分得

12、到解決。對于滿分算法，須首先設(shè)計(jì)一種支持詢問的方法，可以這原數(shù)列做一個(gè)轉(zhuǎn)換，對于原數(shù)列中的數(shù) Si，樣做：它轉(zhuǎn)換為最大的 j(ji)，使得 Si=Sj。如果不存在這樣的 j，那么令其為-1。這樣的轉(zhuǎn)換顯然是可以再線性時(shí)間內(nèi)完成的。作了這樣的轉(zhuǎn)換以后，驚訝的發(fā)現(xiàn)這時(shí)我們要查詢L,R內(nèi)有多少不同的數(shù)，只要看在新序列中的對應(yīng)區(qū)間內(nèi)有多少數(shù)字小于 L（說明這些數(shù)上次出現(xiàn)的位置不在區(qū)間L,R中，也就是說是第一次回答提問了。而詢問一個(gè)區(qū)間內(nèi)有多少數(shù)字小于 L出現(xiàn)），這樣就能這個(gè)問題是個(gè)經(jīng)典的線段樹應(yīng)用：建立一顆線段樹，線段樹的每個(gè)節(jié)點(diǎn)中儲(chǔ)存一個(gè)數(shù)組，數(shù)組內(nèi)將該節(jié)點(diǎn)所代表的區(qū)間中的數(shù)從小到大排序，不難發(fā)現(xiàn)這

13、顆線段樹可以用類似歸并排序的方法建立，這樣對于詢問，數(shù)字小于 L，然后相加即可。但是本題有修改操作，如果就可以在每個(gè)區(qū)間二分，看看有多少要修改序列中數(shù)字，只要將節(jié)點(diǎn)中的數(shù)組修改為平衡樹。你還需要得知一個(gè)點(diǎn)的之前的與其相同點(diǎn)是多少，同樣可以使用平衡樹來。最終使用類似線段樹的方法完成，將數(shù)據(jù)結(jié)構(gòu)變?yōu)闃涮讟涞慕Y(jié)構(gòu)。本題最終在 O(NLog2N) 的時(shí)間復(fù)雜度內(nèi)完成，代碼量很大，對代碼編寫的功底有一定的要求，思考過程也需要經(jīng)過多次的轉(zhuǎn)變才能得到，而且設(shè)置了幾段部分分，可以說是對選手的全面。的等式【問題描述】a1x1+a2y2+anxn=B 存在非負(fù)整突然對等式很感，他正在數(shù)解的條件，他要求你編寫一個(gè)程

14、序，給定 N、an、以及 B 的取值范圍，求出有多少 B 可以使等式存在非負(fù)整數(shù)解?！据斎敫袷健枯斎氲牡谝恍邪?3 個(gè)正整數(shù)，分別表示 N、BMin、BMax 分別表示數(shù)列的長度、B 的下界、B 的上界。輸入的第二行包含 N 個(gè)整數(shù)，即數(shù)列an的值。【輸出格式】輸出一個(gè)整數(shù)，表示有多少 b 可以使等式存在非負(fù)整數(shù)解。【樣例輸入】2 5 103 5【樣例輸出】5【數(shù)據(jù)規(guī)?！繉τ?20%的數(shù)據(jù)，N5，1BMinBMax10。 對于 40%的數(shù)據(jù)，N10，1BMinBMax106。對于 100%的數(shù)據(jù)，N12，0ai4*105，1BMinBMax1012。時(shí)間限制：1s【解題】本題是本是比賽三題中

15、較為簡單的一道，由于題面的描述較為簡單，這里就不再復(fù)述一遍了。這是一類特殊的背包問題，還是按照不同的數(shù)據(jù)規(guī)模來講解此題：20%的數(shù)據(jù)最為簡單，使用回溯算法小，可以輕松通過大約 20%的數(shù)據(jù)。枚舉所有的 ai，由于 N、b 都非常40%的測試數(shù)據(jù)也相當(dāng)簡單，由于 b 的數(shù)量較小，這就和平時(shí)使用的動(dòng)態(tài)規(guī)劃算法沒有什么區(qū)別，這就是經(jīng)典的不限制的背包問題，動(dòng)態(tài)規(guī)劃方程：Fi,j=Fi-1,j-ai or Fi,j，最后只要統(tǒng)計(jì)一下 Fn,j就可以得出結(jié)果了，這樣就通過了 40%的測試數(shù)據(jù)。對于此類背包問題，其實(shí)還有不少的優(yōu)化的技巧可以使用，這里我介紹一種區(qū)間背包的優(yōu)化算法：傳統(tǒng)的動(dòng)態(tài)規(guī)劃算法低效的原因

16、，是因?yàn)樗麤]有充分利用背包問題的特性。可以發(fā)現(xiàn)，大部分 F 數(shù)組的組成很多情況下都是連續(xù)的，即一段都是False，一段都是 True。利用這個(gè)特點(diǎn)，把 F 數(shù)組的結(jié)構(gòu)作如下修改：可以使用一個(gè)二元組(Left,Right)來表示Left,Right這個(gè)區(qū)間是全部為 True 的，然后 F 數(shù)組就是有很多的這樣的二元組組成的數(shù)組，轉(zhuǎn)移的時(shí)候也差不多，我 (Left,Right) 轉(zhuǎn) 移到 (Left,Right+ai)、(Left+ai,Right+ai)、(Left+2*ai,們只要從 Right+2*ai).(Left+k*ai,Right+k*ai)，然后把相加的相并即可。這種結(jié)構(gòu)對程序效率

17、的時(shí)顯然的，雖然具體的時(shí)間復(fù)雜度和數(shù)據(jù)相關(guān)，但是情況要下也不會(huì)比原來的常規(guī)的動(dòng)態(tài)規(guī)劃來得慢，不失為一種優(yōu)秀的算法。不過本題中 h 的范圍比較大，而這種取巧的動(dòng)態(tài)規(guī)劃算法不是本題的重點(diǎn)。我也沒有寫過標(biāo)程，因此無法得知其期望時(shí)間復(fù)雜度，預(yù)計(jì)效果可能不是特別理想，這里只是介紹一下這個(gè)方法。對于 100%的數(shù)據(jù)，觀察數(shù)據(jù)范圍可以發(fā)現(xiàn) ai 的范圍只有 105，這顯然是本題的突破口。單純的數(shù)論似乎對本題沒有很好的效果，只能繼續(xù)回到老，回想以前對于多重背包的解決方法，其運(yùn)用到本題上面：可以按照模分類。設(shè) Gi：達(dá)到背包容量模 a1 為 i 的時(shí)候，背包的容量最少是多少，不難發(fā)現(xiàn)嗎，求出 G 的值以后，就不難得出最終的。初始值 G0=0，更新的話就是 Gi+(aj)=Min(G(i+aj) mod a1,Gi+aj)很容易想到，可以使用不停的迭代來更新 G 數(shù)組的值。直接用 For 循環(huán)來迭代效率似乎相當(dāng)?shù)拖?，再次類比以前的算法，發(fā)現(xiàn)這個(gè)和最短路算法非