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