信息學(xué)奧賽的重要資料。對(duì)于愛(ài)好信息學(xué)奧賽的青少年而言，此報(bào)告十分難得。
Chapter 1 Day 1 1.1 Day 1 rail 11.1題目大意 有兩條平行的單向鐵路(上方的從右到左,下方的從左到右),分為m段 有η個(gè)車站,每個(gè)車站為C類型(只能從上往下)或D類型(只能從下往上), 分布在某些段中,每個(gè)段最多一個(gè)車站。 已知0號(hào)車站是C類型,并給出0號(hào)車站的位置,最多可以詢問(wèn)兩車站之間 的距離3(n-1)次(距離指經(jīng)過(guò)段與段連接處的次數(shù),例如上圖0號(hào)車站到2號(hào) 車站的距離為5),要求確定每個(gè)車站的位置和類型。保證車站兩兩可達(dá) 11.2算法討論 先詢問(wèn)得到0號(hào)車站到其他車站的距離,而最近的一個(gè),就是0號(hào)車站右側(cè) 第一個(gè)D類型的(稱之為j號(hào)車站) 然后詢問(wèn)得到號(hào)車站到其他車站的距離,其中最近的一個(gè),可能是0號(hào)車 站,也可能是其他車站(都稱之為k號(hào)車站),顯然和k之間不會(huì)冉有其他車 IOI2014解題報(bào)告 Day 1 Wall 站,而0和k之間也不會(huì)有其他的D類型的車站,所有k號(hào)車站到其他車站的 距離可直接算出 有了和k到其他車站的距離,那就可以輕松分出左右了(離j號(hào)近,就 在k的左側(cè),否則在j的右側(cè))。 但分出左右后還是不能確定具體位置,而這時(shí)對(duì)于每個(gè)車站我們還留下 次詢問(wèn)的機(jī)會(huì)。接下來(lái)稱當(dāng)前車站為號(hào)車站 而這次詢問(wèn)一定是留給特殊位置的車站,假設(shè)當(dāng)前車站在左側(cè),則考慮當(dāng) 前確定的最左側(cè)的車站(稱之為L(zhǎng)號(hào))。 按離(或k)號(hào)車站的距離從近到遠(yuǎn)的順序處理剩下的車站,那么只有這 兩和情況: L k j 以及(注意下面這種L和之間還會(huì)有C類型的車站) L i k 兩者都會(huì)有以下關(guān)系式:dst(j,L)+|0s;-pos|=dist(j.)+x(x≥0) 第一種情況多出來(lái)的是L到它右側(cè)第一個(gè)D類型車站的距離×2,而第二種 情況多出來(lái)的是L到它右側(cè)第一個(gè)C類型車站的距離×2。 所以,算出x之后,只要到L右側(cè)的c/2的距離處看下車站的類型就可以 確定位置了。這樣問(wèn)題就解決了 如果當(dāng)前車站在右側(cè),那么詢問(wèn)與已確定的最右側(cè)車站的距離,類似討論 即可。 1.2 Day 1 Wall 21題目大意 維護(hù)一個(gè)長(zhǎng)度為的整數(shù)序列,一開(kāi)始每個(gè)元素均為0,支持以下兩種操 作 將連續(xù)一段中小于k的元素修改為k 將連續(xù)段中大于k的元素修改為k 問(wèn)所有m個(gè)操作進(jìn)行完之后序列各元素的值。 3 IOI2014解題報(bào)告 Day 1 Game 1.22算法討論 不難發(fā)現(xiàn)對(duì)某一個(gè)元素的操作是可加的,即說(shuō)對(duì)于某一個(gè)元素來(lái)說(shuō),應(yīng)用 在其上的每一個(gè)操作可以都表示為“如果它的初值小于L,那么最終它等于l; 如果它的初值大于γ,那么最終它等于η;否則它最終等于初值”這樣的形式, 并且多個(gè)這樣的形式是可以合并的。于是我們可以把每個(gè)操作都看成一個(gè)值, 這樣原問(wèn)題就轉(zhuǎn)化成“維護(hù)一個(gè)序列,每次對(duì)一段區(qū)間加上一個(gè)值,問(wèn)最后每 個(gè)元素的值”。這是可以用帶標(biāo)記的線段樹(shù)直接維護(hù)的。該算法的時(shí)間復(fù)雜度 為O(m+ m log n) 對(duì)于“維護(hù)一個(gè)序列,每次對(duì)一段區(qū)間加上一個(gè)值,問(wèn)最后每個(gè)元素的值” 這個(gè)問(wèn)題,我們也可以使用掃描線進(jìn)行維護(hù)。但本題中的值是不可減也不滿足 交換律的,因此在掃描過(guò)程中我們需要使用一個(gè)線段樹(shù)來(lái)維護(hù)覆蓋到當(dāng)前點(diǎn)的 值并將它們按時(shí)間順序依次求和。該算法的時(shí)間復(fù)雜度為O(m+ m log m) 1.3 Day 1 game 131題目大意 有一張n個(gè)點(diǎn)的無(wú)向圖,小B每次會(huì)詢問(wèn)某兩個(gè)點(diǎn)之間是否有邊相連, 小A每次回答yes或no。如果在小B把所有(條邊間完之前,小B就能確定這 整張圖是否聯(lián)選,小A就輸了。現(xiàn)在讓你當(dāng)小A,依次對(duì)每個(gè)詢問(wèn)回答yes或no 求一種獲勝方案。1<n<1500 13.2算法討論 考慮到,如果在一個(gè)已經(jīng)聯(lián)通(這里指的是通過(guò)已經(jīng)回答過(guò)ys的那些邊而 聯(lián)通)的聯(lián)通塊中,還存在一些沒(méi)有詢問(wèn)的邊,那么小B總可以把這些邊留到 最后問(wèn),小A肯定輸了。如果小A能每時(shí)每刻保證已經(jīng)聯(lián)通的聯(lián)通塊中,已經(jīng) 沒(méi)有還沒(méi)詢問(wèn)過(guò)的邊了,那么小4就肯定獲勝了。 邶么每次小B詢問(wèn)一條邊(x,y),如果此時(shí)x和y所在的聯(lián)通塊之間只有一條 邊了,就凹答yes;否則回答no-這樣就可以保證上述邦個(gè)性質(zhì)了。維護(hù)兩個(gè)聯(lián) 通快之間的邊數(shù)可以使用并查集。時(shí)間復(fù)雜度On2) Chapter 2 Day 2 2.1 Day 2 gondola 2.11題目大意 初始有一個(gè)序列,由1~n循環(huán)位移得到,即可能為 1) 是1到n范圍內(nèi)的任意一個(gè)數(shù)字。 之后有若干操作,每次操作時(shí),首先找到當(dāng)前最小的還未用過(guò)的編號(hào)ad, 將序列中的某個(gè)數(shù)字替換為il 定義替換序列為每次操作中被替換的數(shù)字組成的序列 要回答三個(gè)問(wèn)題 1.一個(gè)操作完的序列是否合法? 2.構(gòu)造一個(gè)可能的替換序列 3.可能的替換序列的個(gè)數(shù)(mod1.00,00) 2.1.2數(shù)據(jù)范圍 前三個(gè)了任務(wù)只需回答第一個(gè)問(wèn)題 子任務(wù)分值7 inputted 55 7≤100 從1到n的數(shù)字恰好出現(xiàn)一次 7≤100,0001≤ inputted[i]≤ 107≤100,0001≤ inputted[i]≤250,000 IOI2014解題報(bào)告 Day 2 gondola 接下來(lái)的三個(gè)子任務(wù)只需回答第個(gè)問(wèn)題 子任務(wù)分值n gondolas 4 7<100 1≤ condo1aseq[i]≤n+1 101≤1,0001≤ condo1aseq[i]≤5,000 6 20 n<100,0001≤ condo1aSeq[i]≤250.000 接下來(lái)的四個(gè)子任務(wù)只需要回答第三個(gè)問(wèn)題: 子任務(wù)分值 inputted 5 4≤n≤501< input sea[ 1+3 1≤ inputted[i]≤100,1~m中 154≤n≤50 至少有m-3個(gè)出現(xiàn)在操作完的序列中。 15m≤100,0001≤ input seg[i]≤250,000 10 107≤100,0001≤ input sea[i]≤1,000000 2.1.3算法討論 第一問(wèn) 如果存在1~m中任意一個(gè),那么先檢查相對(duì)位置是否正確 檢查是否所有數(shù)字互不相同。 第二問(wèn) 如果存在1~仉中任意一個(gè),那么可以確定最開(kāi)始的序列;否則任選一個(gè) 初始序列。 從小到大枚舉之后放進(jìn)去的數(shù)字,如果出現(xiàn)在最終序列中,那么放在該位 置,否則放在任意一個(gè)非確定的位置。 第三問(wèn) 從之前的構(gòu)造可以得到計(jì)數(shù)的方法 首先用第一問(wèn)檢查是否合法。 如果存在1~n中任意一個(gè),那么可以確定最開(kāi)始的序列;否則任選一個(gè) 初始序列,亦即最后答案公乘以n 對(duì)于子任務(wù)7~9,依然可以枚舉放進(jìn)去旳數(shù)字,如果不出現(xiàn)在最終序列 中,那么答案乘以非確定的位置的個(gè)數(shù) 對(duì)最后一個(gè)子任務(wù),可以對(duì)最終序列中的數(shù)字排序,分段計(jì)算即可 6 IOI2014解題報(bào)告 Day 2 Friend 14時(shí)空復(fù)雜度 時(shí)間復(fù)雜度:O( n log n) 空間復(fù)雜度:O(m) 2.2 Day 2 Friend 221題目大意 有一個(gè)點(diǎn)帶權(quán)的無(wú)向圖,最開(kāi)始只有點(diǎn)0,隨后點(diǎn)1至點(diǎn)n-1依次加入 點(diǎn)加入時(shí),會(huì)有一個(gè)已經(jīng)加入的點(diǎn)作為它的host,記為host;,它會(huì)在點(diǎn)i和其 他一些已經(jīng)加入的點(diǎn)之間連邊。具體連邊方式有以下三種: I方式:只將i與host連邊。 M方式:只將i與host的所有鄰居連邊(host;本身不與i連邊)。 W方式:將i與hos;及其所有鄰居連邊。 現(xiàn)在已知每個(gè)點(diǎn)的點(diǎn)權(quán),host以及連邊方式,求該圖的最大點(diǎn)杖獨(dú)立集。 22.2算法討論 注意到如果將host;當(dāng)做點(diǎn)i父親,我們就能得到一棵以點(diǎn)0為根的樹(shù),其 中每個(gè)孩子節(jié)點(diǎn)根據(jù)相應(yīng)的點(diǎn)的連邊方式不同可以分為Ⅰ、M和W三種類型。考 慮樹(shù)形DP。令f()表示點(diǎn)訶可以被選的情況下以為根的子樹(shù)的最大權(quán)值,g()表 示點(diǎn)能被選的情況下以i為根的子樹(shù)的最大權(quán)值(這里的能否被選是在不考 慮以i為根的子樹(shù)的情況下)。 首先考慮g(i)的計(jì)算。因?yàn)辄c(diǎn)是不能選的,所以點(diǎn)的所有M類和W類孩子 都是不能選的,I類孩子是可以選的。因此 ∑9(u)+∑f() 其中u是的M類或W類兒子,0是iI類孩子 ∫()的計(jì)算分兩種情況。第一種情況,我們選擇了點(diǎn),那么點(diǎn)i的所有I類 和W類孩子就不能選了,而M類孩子仍是可以選的,所以在這種情況下 f()=∑9(u)+∑ 7 IOI2014解題報(bào)告 day 2 holiday 其中α是i的I類吸W類孩子,是的M類孩子。第二種情況,也就是不選擇點(diǎn)a 凊況稍微復(fù)雜一些,我們需要決定的每個(gè)孩子α是否能夠被選擇,唯一的限制 是,一旦我們決定了一個(gè)類或W類兒子是可以選擇的,那么在它之后加入(編 號(hào)比它大)的M類孩子和W類孩子就是不能選擇的了。我們可以對(duì)所有孩 子進(jìn)行一個(gè)簡(jiǎn)單的DP來(lái)作出最優(yōu)決定,再加上i點(diǎn)本身的權(quán)值即可得到這種情 況下的f()。最后,在兩種情況下得到的∫(i)屮取較大的一個(gè)作為最后的f()即 最終,f(0)即為答案。該算法的時(shí)間復(fù)雜度為O(m) 2.3 Day 2 Holiday 231題目大意 n個(gè)城市依次排開(kāi),編號(hào)為0到m-1。i號(hào)城市與讠-1號(hào)城市和i+1號(hào)城市 相鄰。一開(kāi)始你在 start號(hào)城市。每一個(gè)時(shí)刻,你可以選擇移動(dòng)到相鄰的一個(gè)城 市,或者游玩當(dāng)前城市,并獲得α;的娛樂(lè)值,其中i是你現(xiàn)在所在的城市編號(hào)。 你不能游玩同一個(gè)城市多次,但是能多次經(jīng)過(guò)同一個(gè)城市。問(wèn)d天你能獲得的最 大愉悅值是多少。1<m<100000 2.3.2算法討論 起點(diǎn)在0號(hào)城市 可以發(fā)現(xiàn),在這種情況下,只會(huì)一直往右移動(dòng),而不會(huì)回頭。因此可以枚 舉往右走到的最右邊那個(gè)城市,然后再?gòu)氖Ｓ嗟奶鞌?shù)中,選擇愉悅值最大的若 干個(gè)城市進(jìn)行游覽。后者可以用可持久化線段樹(shù)實(shí)現(xiàn)。 只往右走,對(duì)每個(gè)d求得答案 令∫a為可以游覽d大,最優(yōu)的那個(gè)右端點(diǎn)。我們有如果x<y,那么f≤f 考慮fx與x+1,假設(shè)fx+1<fx。先把能游覽x+1天的右端點(diǎn)與游覽x天的 右端點(diǎn)放在∫處。右端點(diǎn)每次向左栘動(dòng)一格,游覽π天的與游覽x+1天的,都 能游覽一個(gè)新的城市(當(dāng)最右端的那個(gè)城市本來(lái)也被選時(shí),是兩個(gè)新的城市)。 但由于ε+1天的本來(lái)就比天的游覽了更多的城市,所以這個(gè)天的新城市的愉 悅值要大于等于+1天的新城市的愉悅值。當(dāng)它們移動(dòng)到fx+1時(shí),x天的增加 的愉侻值大于等于x+1天的增加的愉悅值。于是就矛盾了。因此有f≤f+1 IOI2014解題報(bào)告 day 2 holiday 接下去考慮分治,要求d在1,中的所有fa,并且知道這些fa在[a,b中。令mid 12」,首先暴力找到fmd接下去遞歸分別找h…fmid-1,fmi+1…f。其中 f;……fmad-1都在a,fmd之間;fmid4+1….f都在[fmtd,b之間。這樣總的時(shí)間復(fù) 東度是O( )的 原問(wèn)題 最優(yōu)策略肯定是往右走再折回左邊,或者往左走再折回右邊。既然可以對(duì) 每一個(gè)d都求出只在左邊或者只在右邊的答案,也可以求出對(duì)于每一個(gè)d往 方向走,再折回 start的答案(具有類似上文中的單調(diào)性),那么只要求出兩邊 分別對(duì)于所有d的答案后,就能求出整個(gè)問(wèn)題的最優(yōu)解了。