WC 2025

日期： 2025年1月14日，甲辰十二月十五
標籤： pkuwc wc 2025 journal

2025-01-14

T1

有 a 節好電池和 b 節懷電池。你需要找到兩節好電池。每次你可以詢問兩節電池是否是好的。問最優策略下，找到兩節好電池最壞情況至少需要幾次嘗試。

T2

給定一顆有根樹，每次詢問 (l, r, x)，問 [l, r] 節點的 x 級祖先構成的集合大小。

T3

Alice 和 Bob 在一張有向圖上博弈。每個節點有一個顏色 $a_{i}$，有一個顏色序列 $c_{i}$。從 $x$ 節點出發，Alice 和 Bob 輪流操作，第 $i$ 次操作到，從當前節點出發，走若干步，找到某個節點，使得其顏色爲 $c_{i}$。如果沒有這樣的節點，或者 $c$ 不夠長，則輸。問對於每個出發節點 $x$，最小的 $r$ 使得當顏色序列 $c$ 去掉前 $r$ 項時，Alice 有必勝策略，如果必敗輸出 -1。

考得很差。好多時間都浪費在 T1 上面了。死活調試不出來。暴力也很難寫，最後覺得寫一個 $O(2^{n^{2} + n})$ 的試一試，結果發現 $a=3, b=3$ 的答案居然是 6。我一直以爲是 7。然後豁然開朗，寫了一個 $O(n^3)$ 小常數的，過了。

T2 本來以爲會了 $O(n^{1.5} \log n)$，結果假了，只有 24 暴力。

T3 也只會暴力，$O(n^3 / w)$ 的 20 分也沒寫完。

考得稀爛😭️。再次被 ssz 爆殺。

2025-01-15

T1

交互題，有一棵大小不超過 $10^5$ 的樹，通過以下兩種詢問，找到這顆樹的任意兩一條之徑的兩個端點。

1. query(x, y, z)，返回 dis(x, y) + dis(y, z) + dis(x, z)。要求 x, y, z 兩兩不同。調用次數不能超過 $3 \times 10^5$。
2. in(x, y, z)，返回 x 是否在 y 到 z 的路徑上。調用次數不能超過 $2$ 次。

T2

有 n 個桶，第 i 個桶有 $a_{i}$ 個球，你需要通過一下兩種操作，將所有桶內的所有球拿出來。

1. 選擇一個桶，拿出一個球，代價爲 1
2. 選擇一個長度不超過 m 的區間，從這個區間的桶中拿出不超過 k 個球，代價爲 c。

問將所有球拿出的最小代價和。

T3

從 x = 1 開始。有三種操作：

1. $x \gets x + 1$。
2. 若 $x > 1$，$x \gets x - 1$。
3. 選一個整數 $k > 1$，$x \gets xk$。

問對於 $[l, r]$ 中的每個整數 $y$，經過不超過 $B$ 此操作，從 $x=1$ 操作成 $x=y$ 有多少種操作方案。

T1 不會做，寫了一個多小時只會 7n 的做法，其中 4n 用於找一條邊的兩個端點，2n 用於尋找直徑的一個端點以及緊挨這這個端點的一個頂點（唯一），n 尋找直徑另一個端點。好像沒什麼思路優化了。

開 T2，一下子也沒有什麼思路，感覺可能可以強制從左往右拿球，但又不確定對不對。又開 T3，一看就不太會的樣子，先寫一個很顯然的 24pts $O(r\log r B)$ 暴力。試圖卡過 5e6 的點，但是卡不動。有嘗試寫了寫 B <= 4，l=r 的點，結果寫半個多小時也寫不出來。感覺和整除相關的題目也不是我能做的。於是放棄。

又回來看 T2，嘗試寫了 $a_{i} \le 100$，$n \le 500$ 的 subtask，令 $f(i,j)$ 表示 $[0, i)$ 拿完，$a_{i}$ 還剩 $j$ 個，$[j + 1, n)$ 沒動的最小代價。然後又寫了 $c=1$ 的 subtask，比較簡單的貪心。發現這個 dp 雖然和值域相關，但是似乎狀態數不多，於是把值域那維換成 map，而且轉移也只用考慮當前在 $i$ 爲左端點使用了 $\left\lfloor\frac{j}{k}\right\rfloor$ 個操作 2，和使用了 $\left\lceil\frac{j}{k}\right\rceil$ 個操作 2 的情況。居然拿了 70 多分！太振奮了！！！

PKUWC 四個小時真的好緊張啊，三道題，一道都不會，同時處理三道題就會手忙腳亂。如果能趕快把 T1 做出來，那確實就輕鬆很多。

szz 會 T1，太強大，orz。

唉，如此成績如何省選。

2025-01-16

上午去了魯迅紀念館。中午喫了紹興菜，品鑑紹興黃酒。

帶圖畫的山海經（神似奶龍的刑天）：

回來時在酒店對面的兒童樂園玩（特別好玩），面積了羣友 0x3b800001。

2025-01-17

伙食比 PKUWC 好多了。

和不知名選手和不知名教師打了乒乓球。結果一天就戰損兩個乒乓球。

找到傳奇特級自習室：

可惜這個辦公室空調似乎有點問題，晚上巨冷無比。

杜子德單口相聲。

2025-01-18

不能再頹廢了！要認真聽講！

掀起了一股找講師要簽名的熱潮。

中午和不知名工作人員打乒乓球，似乎還是說是省隊，被虐爆了。

2025-01-19

上午去第二課堂聽網絡流，下午聽思維題。第一課堂聽不懂。

乒乓球晚上到了，又可以打球耶。

晚上再戰 WC24 代碼堵塞，寫一個多小時，一百多行，簡單背包。被題解區二十幾行代碼震驚到了。

2025-01-20 (考試日)

睡的不是很好啊，最近睡覺總是起夜。於是在試機的時候又睡了近一個小時。

T1 做的比較順利，很快就有思路，寫出來結果 selfeval 只有 65pts，仔細思考發現沒有考慮很多個大小 n/2 的優質貓糧的情況，改一改就過 selfeval 了。但是我還不知道有沒有什麼其他情況沒有考慮到，本打算寫個暴力對拍，但感覺暴力機難寫，於是選擇相信 selfeval。

T2 很沒思路，要輸出不超過 m 個方案，就很詭異。令 f(i,j,k) 表示考慮前 i 個數， xor 和爲 j，用 k 次加法，的方案數。後又發覺不必記錄方案數，改成 f(i,j) 表示前 i 個數，xor 和爲 j，最小加法使用次數，找方案直接搜索，得到 28pts，又想了一個來小時感覺沒啥思路，加法和異或放到一起太神祕。

T3 反而還容易一點，很快寫出 $O(n^2)$ dp，結果過不了大樣例，仔細分析，離散化應該要把 $a_{i}$ 和 $a_{i}-1$ 都包含進去，然後就得到 40pts。發現 dp 數組更新比較簡單，用數據結構維護。最後在比賽還剩 20min 的時候調試完 $O(n\log^2 n)$ 的版本，只有 85pts，雙 log 是因爲二分線段樹。嘗試改成單 log 線段樹二分，結果發現不會寫從特定端點開始的線段樹二分：

// 摘自 atcoder library
    template <bool (*g)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

總分 100 + 28 + 85 = 213，好多人比我高啊。唉，如此成績如何省選。

和 xzc 打 40min 左右乒乓球，戰損兩球，狗屎天花板設計。

晚上講題人 13 min 速通講題。然後文藝匯演，挺好玩的，甚至還有 cosplay 大佬，可惜我沒有參加表演的勇氣。

文藝匯演

極大概率是最後一次參加冬令營了，好像也看不到那麼遠，只希望能過省選。

晚上還有 codeforces，沒有打，jiangly 上 4000，太強大。jmr 上 grandmaster，被初三後生遠遠超越了。

洛谷修復了能看全網犇犇的 bug，猜猜犇壽命纔兩週就暴斃，犇站也掛掉了。

2025-01-21

上午是講隨機相關的科普性講座，聽了一半跑路了。

下午又聽動態圖連通性問題，說實話黃洛天講得挺好的，但是有點睏，後頭掉線了就跑路了。同時集齊了 IOI2024 國家隊簽名（原諒我不會做圖片）。

晚上和何釩佑玩，打了乒乓球。

探訪神祕 KTV，不敢去唱歌，內向自閉 OIer。

又玩了 crazy games 小遊戲。想到這些金牌的選手冬令營結束就要離我們遠去了，就很傷感。

2025-01-22

上午講稀疏圖上更快單源最短路算法，大概是 TCS 相關內容，沒想去聽，頹頹頹。下午講模擬退火和概率編程，比較有意思。

今天同時也是國家隊選拔第二試，何釩佑這場考試後竟是第六！問題來了，他沒有準備論文，而前六名必須要答辯。他來之前積分排名是第九，本以爲全無進前六的可能。於是從當天下午開始狂暴趕論文。

我晚上去陪他，同時打了一場 cf。是 Round 1000，div 2，陽間場，手速有點慢，被 D 硬控了好久，F 題都沒來得及看，好在還是上了 Master。而何釩佑趕論文和 PPT 趕到凌晨三點過，還沒來得及準備英文自我介紹。

2025-01-23

最後一天，上午是國家隊答辯。

提問特別有意思：

刘恒熙

杜：呃，我們的同學把手機帶進了考場，有同學遺憾地被取消了資格，就沒有得到牌牌。有人說：「領隊爲什麼不提醒我們的選手，別把手機帶進去」。你怎麼看這個事情？

刘：作爲選手，如果我能有幸被選入國家隊，我在之後一定會注意這個問題。我認爲選手也是有一定的責任的，就是比賽，它一定是不能帶進手機的。然後領隊的話，之後也應該要最好要做好提醒。感謝杜主席的提問。

杜：我現在告訴你，你選上還是選不上，我們以後都不會提醒你，因爲規則已經定在那兒了。就像是馬路上的紅綠燈，警察不提醒你你就闖紅燈，你覺得可以嗎？人家就按規則辦了，那你怎麼辦？

刘：呃，那只能在之後更加注意。

杜：一定要按規則辦，不需要提醒。

刘：好感謝杜主席的教導。

杜：哈哈哈哈。

刘海峰

杜：海峰你好。我們中國國家隊隊員呢，是經過層層選拔的，都非常優秀。呃，不光是四個同學，即使去八個同學，往往我們都可以拿足四個或所有的金牌（沒聽清？）。去年是因爲規則問題，我們喫了一點虧。好了，我假如啊，假如你被選入這個中國國家隊，今天到玻利維亞去，代表中國去參加 IOI。我呢，是你的指導教師，我也覺得挺榮幸的，我就打算在現場，拿個攝像機，向全世界來直播的這個行爲，啊。刘海峰已經順利到達了玻利維亞首都，他即將要比賽，啊這個海峰是我培養的衆多學生之一……還有更多。我一直在直播。你覺得我的這種行爲好嗎？

刘：我覺得這種行爲是不對的。首先感謝杜老師的提問。我覺得這種行爲是沒那麼恰當的。因爲，首先我們學信息學是因爲熱愛而學，而不是……我覺得作爲一個教信息學的教練，他應該……應該想方設法如何去培養學生，而不是把心思，花在如何蹭流量方面。

杜：海峰，我感謝你當着這麼多人的面，批評你的老師。經過你的批評，我決定修改我的想法，我不再直播了，謝謝你。

附參考文獻：

被罚，我认为是好事。我发现现在我们（当然包括我自己）有点骄傲了，有点飘飘然了，以为夺得金牌就意味着中国教育先进，科研创新力强，产业也打压外国！这哪儿和哪儿呢？这只是孩子们的智力游戏而已，不要拔那么高。而中学也借此大做文章，吹牛，为招生做铺垫。这不，这次居然有随队老师现场直播，意思是他们的学校盛产金牌！这样做，真是全球第一！

後頭懶得轉錄了，AI 識別準確度太低。

IOI25 中國國家隊答辯問答精選集

最终國家隊也沒有什麼懸念的 1234，恭喜。

下午頒獎儀式，szz 金牌太厲害。拜謝。然後冬令營就結束了。

hfy、xzc 這些選手下學期就去北大讀預科了，就此遠離我們了，有些傷感。

希望能過省選。