IOI 2021

警告：本文含有大量爆雷內容

終於到了 IOI 啦，這次跟去年一樣是線上賽，不一樣的地方是臺灣疫情剛好爆發，所以今年連實體國手培訓都沒有。我們就都住在家裡，比賽日才到比賽場地去，比賽場地有師大跟交大，所以國手們就分隔兩地了。

在正式比賽前有個測試賽，測試賽兩個小時放了四題，其中兩題是沒什麼好玩的水題，另外兩題有一題是某種二分搜，連續給分，我沒有拿滿（然後它就是這次唯一出現的連續給分了），另一題小測資很水，大測資不會做。

Results．Code．題目

day 1 的 code 沒什麼好看的所以就沒有存 (?)。

我本來想要把作法跟過程寫在一起，這樣比較能感受到思考的過程 (?)，但我發現我的金魚腦不足以讓我記住我想到東西的詳細過程，所以還是像之前一樣跟題目寫在一起ㄅ。

Day 1

題目

pA 分發糖果

3 / 8 / 27 / 29 / 33 = 38

有一個長度 的序列 ，一開始都是 0，還有給你一個長度相同的序列 ，然後有 筆操作，對於一筆操作 ，表示對於 ， 是正的則 否則 ，求最後的 。

嗯，區間加值取 min、max，很有 Segment Tree Beats 的感覺，可是每個位置取 min 的值不一樣，可能不能直接用 Segment Tree Beats 做。這題乍看之下是三題裡面最可做的題目，原因就是它和 Segment Tree Beats 很像，感覺會是線段樹小改一些東西。

subtask 3 是 全部長一樣，subtask 4 是操作的區間是整個序列。subtask 3 就真的是裸的 Segment Tree Beats，不過賽中我就想這不是跟 IOI 2014 Wall 長得一樣嗎，寫這個的時候才發現 Wall 沒有區間加值，不過也差不多，我的 tag 維護是節點區間的上下界和要加的值，不過要加的值會先作用到這顆點的上下界，只是用來下推用的，所以大概長成這樣（這個時候就有點希望我有存 code 了）：

struct Node{
    ll mn = 0, mx = 0, add = 0;
};

void add_tag(int v, int type, Node &node){
    if(type == 0){ // 改下界
        node.mn = max(v, node.mn);
        node.mx = max(v, node.mx);
    }
    else if(type == 0){ // 改上界
        node.mn = min(v, node.mn);
        node.mx = min(v, node.mx);
    }
    else{ // 加值
        node.mn += v;
        node.mx += v;
        node.add += v;
    }
}

然後 push 就是直接把三種 add_tag 對子節點做一遍，modify 遞迴之前要記得先 push，不然範圍會壞掉。

至於 subtask 4，我在快結束的時候才大概想到作法，我的想法是，如果把所有加的數字分配進去裡面的 min、max，例如 ，那麼每個數字都會變成操作的後綴和，而那一個操作是取 min 或 max 依正負而定，然後可能可以用某種方法判斷最後取到的數字是哪一個，因為時間不多，所以我亂唬了一個作法，最後 2 秒傳上去，有夠驚險，不過還是沒過 QQ。

聽說這題其實是掃描線套線段樹。

pB Keys

9 / 11 / 17 / 30 / 33 = 37

為什麼這題題目名稱沒有翻譯呢？我也不知道。

有一張 節點 條邊的圖，每個節點上有一把鑰匙，鑰匙有 種，只要你在節點 ，你就可以獲得第 種鑰匙；如果你要通過第 條邊，你必須要有第 種鑰匙。鑰匙不會消耗。求從哪些節點作為起點，能到達的節點數量是最少的。

前三個子題就是直接 BFS 下去就好了，至於後面的我一點頭緒也沒有。

pC 噴泉公園

5 / 10 / 15 / 20 / 20 / 30 = 70

平面上有 個噴泉，每個噴泉是一個點，、 座標都是偶數，你可以建造若干個長度為 2 的，水平或鉛直的線段，表示一個道路，道路的兩端必須都是噴泉，道路要使所有噴泉連通。並且你要為每一條道路決定一個長椅的位置，長椅是一個點，位置只能在那條道路中點的兩側（和道路垂直方向） 1 單位距離的地方，並且不同道路的長椅位置不能重複。

前三個 subtask 分別是 座標只有 1、2、3 種，最直覺的想法就是先把在同一個 座標，可以連的都連起來，然後再用水平道路把連通塊們連起來。至於長椅位置， 座標最多 3 種，分成左中右，左邊和右邊的長椅可以放在左邊和右邊，不會和其他長椅衝突，至於中間的話可能會和水平道路衝突。

不過注意到只要蓋出來的道路是樹，並且遵守垂直能連就連的原則，無論水平道路怎麼建，可能造成衝突的只會有這兩種狀況：

不難發現只要讓水平道路的長椅 座標不重複，就一定可以讓中間的鉛直道路有長椅。

至於 subtask 4 是保證只有一種建道路的方法，所以就是能建道路就建，最後一定是一顆樹，而且對於每一條道路，它兩側都不會有和它平行、距離 2 的道路（也就是沒有平行的會搶長椅的道路）。我想了一個我覺得很棒的作法，就是把它做二分圖分兩邊，一邊是順時針點、另一邊是逆時針點，然後每個點相鄰的道路，它的長椅就是往那個點的順序時針方向指定，這樣就可以保證沒有道路共用長椅。

其實做這件事的前提只有「每個道路都沒有平行的、會跟它搶長椅的道路」這件事而已，而 subtask 5 的限制「沒有 方格」正好滿足，所以只要確保蓋出來是樹就行。

我寫 subtask 4 的時候還沒想到 subtask 5 可以用，然後又想這個子題蓋出來一定就是樹，所以就把用來防止環的 DSU 拿掉，還好我後來有發現可以直接拿 subtask 5 分數，不然就少 20 分了。

過程

之前打 OI 都是開場讀題半個小時，不過因為 IOI 的題目比較重思考，所以就拉到一個小時。第一次讀完題後超緊張，因為我全部都只會暴力，精神分數少得可憐。因為想說 pA 看起來最可做，待會應該會多想到一點東西，我就先去把沒什麼頭緒的 pB 寫掉，pC 的話因為實作感覺小麻煩（其實也還好），所以想說先放著等一下再寫。

結果我想 pA 想了超久都沒有進展，還是只會暴力，因為那個暴力超好寫，想說之後跟大測資一起寫掉就好，不然之後再寫也不遲，所以就先去寫 pC 了。

後來我發現 pC 才是這天最可做的題目，前三個 subtask 用 subtask 3 一次過之後，很快就想到了 subtask 4，這個時候就像前面說的，我不知道這個作法可以直接拿去做 subtask 5，所以就先回去想 pA。

忽然發現 subtask 3 長得跟 Wall 很像，花了點時間想仔細後就開始寫，本來超擔心實作會不會爛，還好一次就過了。

我本來想要想 subtask 4，但是真的想不出來，所以回去看了下 pC，發現 subtask 5 只要補 DSU 就好了，這個故事告訴我們乍看沒用的東西不要亂刪，會有意想不到的收穫。要是我沒回去看 pC 一直想 pA 的話就拿不到這 20 分了，真是可怕。

比賽的尾聲就是想 pA subtask 4，最後 10 分鐘想到了點東西，趕快開始寫，最後幾秒根本不確定正確性就丟了，超刺激，不過沒過。

前半場其實都滿焦慮的，因為 pA 做不出來，但看起來又是那種可能大家都會的資結小變化題，我前面緊張到有點慌亂，後半場因為 pC 分數很多很開心所以有稍微放鬆一點，不過結束的時候還是很擔心會不會銅牌。第一次讀完題我甚至擔心我會不會沒牌，不過其實賽中不應該想這種事。

總結

總分 38 / 37 / 70 = 145，排名 53，落在銀牌中間。

其實名次有點高得出乎意料，我結束的時候真的以為這個分數會在銅牌。結果 ZCK 跟蛋餅的分數都跟我一模一樣，balbit 分數也只比我們多 7 分，看來表現得並不是特別慘，就普普通通。

Day 2

題目

pA DNA 突變

21 / 22 / 13 / 28 / 16 = 100

給你兩個長度 的字串 和 ，只由 A、T、C 構成。對於一個字串，你可以對他作操作，每次操作是把某兩個位置交換，不必相鄰。有 筆詢問，一筆詢問 表示把 變成 的最少操作數。

堪稱 IOI 史上最水題目，可能是 Day 1 出太難了想平衡一下 (X)，這題有 304 個 AC，水到跟不存在差不多。

我的作法（應該也只有這個作法）是數每一種 (原始, 目標) 的種類數，原始跟目標相同的忽略，然後 跟 可以對消，消了會讓答案 +1。可以消的消完以後，如果有解的話會剩剛好三種 、、，而且數量都一樣，然後答案就是數量 。

本來其實不太確定是不是這樣做，上廁所的時候感性 (?) 證明了一下，回去後就開始寫了，不過我其實不會嚴謹證明 QQ。

pB 地牢遊戲

11 / 26 / 13 / 12 / 27 / 11 = 62

有 個房間，從 0 開始編號，如果你現在在第 個房間且力量是 ，那麼：

• 如果 ，結束。
• 如果 ，力量會加 ，且你移動到 。保證 。
• 如果 ，力量增加 ，移動到 。

有 筆詢問，每筆詢問給你初始在的房間編號和力量，求結束時的力量。

因為 、 都是正的，所以很顯然最多 輪就會結束，第一個 subtask 可以暴力掉。

我先想了 subtask 3，每個 都一樣，所以只要贏一次就會直接走到結束，顯然就是用倍增法看走輸了幾次後會達到需要的力量。

想到這個之後，我以為每次贏之後力量就會變兩倍，所以頂多贏 次，就用倍增寫了一直輸、贏一步、一直輸……，結果只拿到 subtask 1，我想了一段時間才發現這是錯的，因為 很小的話就不是變兩倍了。

沒關係，這個假解改一下就可以拿到 subtask 3 了，不過因為我沒有設好房間 走到的地方，所以可能會不小心走回去 ，剛好 subtask 1 不知為啥沒卡到這個，我就花了一點時間 debug。

subtask 4 的限制看起來很怪，是 只有 5 種，好吧，那就離散化 ，然後用倍增處理「目前力量 第幾大的 時，走 步」的資訊。

在想 subtask 2 的時候想到了一個新的假解：一直輸、一直贏、一直輸……最多切換 次，所以我就把 subtask 3 的 code 改一下，複雜度變成 輸贏的切換次數 ，但這個次數其實可能是 ，不過在 subtask 2 裡面，每次輸的時候，力量會真的翻倍，所以只會輸 次而已，這邊就意外地拿到這個分數了。

總之我的分數都是在假解中來的 ww。

順帶一提，這題是臺灣的前國手何達睿學長出的，這裡有他的出題心得。

pC 位元移位暫存器

10 / 11 / 12 / 25 / 13 / 29 = 46

這題的敘述不是三言兩語可以講完的，所以就自己去看題本吧 (X)。

我在取 min 的任務作法是，要取兩個數的 min，就先把它們 xor，然後找到 xor 的最高位，找法請見 code (?)，接著拿最高位去和其中一個數 and，如果 and 完那位還在的話，表示兩個數中的最小值是，這個數 xor (兩者的 xor)，因此就把這個 and 完的結果往低位填充，再拿去跟兩數的 xor 做 and，最後把這個結果跟剛剛選的那個數 xor，這樣就會拿到最小值。

這樣直接對全部一個一個取 min 的話可以過前 3 個 subtask（subtask 2 可能需要特別壓一下）。

至於排序的任務，我的作法就是直接 bubble sort，交換兩個數的方法是先做剛剛的取 min，然後比較大的那個當然就是 min xor (它們兩個的 xor)。

過程

一樣開場先讀題，本來預計是一個小時但狀況有點不一樣 (?)。pA 看一看不久就想到解法，雖然不確定對不對但先放在心裡，看下一題。pB 比較多東西可以想，我先想到了 subtask 3 是倍增，然後就去看 pC。pC 看完後完全沒有想法，一個 subtask 都不會做，想了滿長一段時間都沒想到，只好待會再想。

pA 在開場 41 分鐘就過了，本來預計的讀題一個小時縮水超多，應該只有半個小時而已。

後來花了滿多時間在 pB 上，中間有時不時回去想 pC，但都想不到什麼東西，pC 一直到快三個小時的時候才過了第一個 subtask，我想了大概一個小時吧。後來我有抓到一點 pC 的感覺了，滿順利地想到了後面的 subtask。

pC 分數拿不下去之後就回去想 pB 肥肥的 subtask 2，26 分真的很吸引人。想到假解本來是想拿滿分的，結果只多拿到這個我本來沒什麼頭緒的 subtask，其實也還算不錯。

總結

分數 100 / 62 / 46 = 208，排名 29。

這天的表現我滿滿意的，感覺該拿的分數都拿到了，排名也不錯。

這天比較好的地方是我有盡量克制自己去想名次的問題，所以這天沒有像 day 1 那麼焦慮，不過原因一部分可能是 DNA 真的太水。

是說我很驚訝這天居然沒有出現連續給分，因為 day 1 有超多人同分，尤其是銀牌線和銅牌線都有幾十個人同分，本來想說一定會出現連續給分解決同分的問題。不過這天的題目也滿多種 subtask 組合的，所以也解決了同分問題。

真正的總結

兩天總分 353，第 33 名，銀牌。

金牌線是第 30 名 373 分，不過我差了一個 subtask 的距離，所以也不能算是差一點點，就算金牌我可能也會覺得我是靠賽 (?)。

結果整體還挺滿意的，我本來是預期我會在大概前 50 名，鍋貼金牌線比預期好很多，而且該拿的分數看起來都有拿到（不過我其實還沒開始補題，可能我開始補之後會發現我超笨）。

這次很可惜不能出國，國培也只是線上上幾堂課而已，所以就希望明年還能再當一次國手，然後疫情快快結束，讓我出國啦 QQ，至少也要有到處跑來跑去的國培。

然後我之前好像說要在 blog 發資奧總心得，不過好麻煩喔還是算了吧 (X)，想看去看 FB 的。