2020 ICPC 濟南站感想和部分題解

在上次 CCPC 打銅之後，我們打了一次很失敗的校賽二等獎。濟南報名之後，正式比賽之前，我感覺自己的狀態和心態都並不是很好。準備這次比賽時想着拿銅有點小虧，拿銀就比較正常了。

在賽場上，簽到四題的部分共 WA 一發，還算比較穩，但並不快，排名在銀區。

然後自然是跟榜看 A、L，但是都沒有想出做法，尤其是 A 涉及的矩陣變換等是我最弱的方向。

後來發現有人過 J 題之後，我也開始看，一開始想在反圖（原圖不存在的所有邊組成新圖）裏找強連通分量來構造，後面發現似乎並不可行。然後我想起了樹上可以相鄰點異色染色之類的操作，就發現它可以染兩種色，同色點之間無邊，這樣這題一下子就豁然開朗了。很快地過了 J，排名一下子到了 9。

然後就進入了罰坐模式，期間我甚至想提前放棄🌚。A 題過的隊越來越多，我們卻遲遲找不到做法。由於我矩陣、代數等方面不太行，幫不上忙，便把所有沒過的題都看了，然後也沒發現有思路的，心態有點炸。A 題隊友找到了把等式變形，矩陣按列拆開之後每列算自由度的做法，繼而想到高斯消元和線性基。因爲高斯消元算各列，總的複雜度是 O(n4)O(n4)，即 1.6×1091.6×109，感覺過不了，然後線性基連板子都沒人看得懂，又開始卡。直到最後沒辦法才嘗試用高斯消元去做，結果直接過了。賽後大佬們都說高斯消元本來複雜度就卡不滿🌚，另外這題也可以 bitset 優化，不過沒優化也過了。

A 題過了之後金牌應該是穩了，我一下子心態好了非常多，然後我們再一起看 L，想到了枚舉後面幾位的方法，但是隻有不到半小時，來不及過了。不過金牌已經有了，這題過了也離出線差一題，所以也沒太大影響。

這場我前中期發揮還可以，但在 A 卡題過程中不僅沒幫上什麼忙，反而因爲自己心態不好，對隊友心態也有些影響。很感謝他們並沒有一起心態爆炸，並且最終過了這題，讓我們第一次打 ICPC 就獲得了金牌的好成績。

A Matrix Equation

題意：已知相同大小的 0-1 方陣 AA 和 BB，定義運算 ×× 是普通的矩陣乘，所有元素對 2 取模。定義 ⊙⊙ 爲對應位置元素相乘（也就是相與），求使等式 A×C=B⊙CA×C=B⊙C 成立的 CC 的個數，對 998244353 取模。

很顯然，CC 的一個元素只會影響它所在的那一列，所以可以以列爲單位分開考慮。

好像是隻考慮一列之後，就可以得出方程組，然後用高斯消元算自由度。這題隊友過的，我先溜了🌚。

C Stone Game

題意：有若干堆石頭，每堆有最多三個石頭，MianKing 想把它們合併爲一堆。他每次可以把任意兩堆合併爲一堆，如果合併前兩堆石頭各有 xx、yy 個，則代價爲 (xmod3)(ymod3)(xmod3)(ymod3)，求最小總代價。

首先，石堆的個數只有模 3 後的部分有意義。模 3 爲 0 的石堆，它與任何石堆合併代價爲 0，也不會影響其個數模 3 的值，故可以無視。

然後，1 與 2 都有時，把它們兩兩合併爲 0 是最優解，因爲如果不這樣做，兩個 1 變成 2 代價 1，兩個 2 變成 1 代價 4，怎麼想都是虧的。因此，優先合併爲 0，耗盡 1 和 2 中較少的那種。

對於多出的 1 或 2，顯然只能合併，然後得到 2 或 1，然後按照上面的結論，優先合併 0。也就是三個 1 或 2 合併得 0，代價是 3 或 6，直至剩下不到三個爲止。

上一步如果剛好夠或者剩一個，都沒有額外代價。剩兩個時則還有一次額外的合併。

D Fight against involution

題意：期末論文有一個奇怪的打分規則：一個人的成績等於全班總人數減去論文字數比他多的人數，不含相等。每個人能寫的字數都有一個區間 [L,R][L,R] 作爲限制。爲了拿高分，卷王們自然都會寫最多的字數。但是，如果大家都不那麼卷，適當減少字數，或許可以讓所有人的成績都不降低。這題要求找到一個這樣的方案，在所有人成績不降低的前提下，讓所有人寫的字數總和最小。只輸出最小總和的值即可。

這個成績實際上就是排名，並列往高算。

所有人排名不降，也就是排序不能變。因爲並列算高，原本不併列的可以變並列，反之則不能。

顯然可以貪心，按原字數排序，原字數最少的儘量減（到 LL），後面的在不比前面的少的情況下儘量減。並列的只能一起減到它們的 LL 中的最大值。

具體做法可以把 RR map 到對應的最大 LL，也可以對 RR 並列的按 LL 從大到小排，等等。

G Xor Transformation

題意：通過最多五次操作把 xx 變成 yy，每次操作是任選滿足 0≤a<x0≤a<x 的 aa，令 x=x⊕ax=x⊕a。保證 y<xy<x。

第一次可以把 xx 補滿成 2k−12k−1 的形式，第二次則直接變成 yy。由於允許 a=0a=0，這種做法無需任何特判。

J Tree Constructer

題意：已知一棵無向樹，要求爲每個點賦值（[0,260)[0,260)），使有連邊的兩點所賦值按位或結果等於 260−1260−1，無連邊的兩點所賦值按位或不等於 260−1260−1。輸出一種方案即可。

這題一開始往反圖方向考慮去了，後面發現這樣做位數應該不夠。

按染色思路，相鄰邊異色，染成兩色，設較少的顏色爲 0，多的爲 1，這樣顯然可以構造互補關係。

先對每個顏色爲 0 的點，分配一位，置 0，其它位置 1。再爲了防止同色互連，把一個標記位置 0。

這樣顏色爲 1 的與它互補，標記位置 1，分配給與它相鄰的各點的位置 1，其它置 0。

最多 51 位，加上顏色爲 1 的各點共同的零（剩下 9 位都是，需要 1 位），共需 52 位。

M Cook Pancakes!

題意：經典問題，平底鍋煎煎餅，兩面都要煎，3 個餅能同時煎 2 個，最少 3 次可以煎完。求 nn 個餅能同時煎 kk 個，最少幾次能煎完，n,k>0n,k>0。

現在我們應該很容易想到，2n/k2n/k 向上取整的方案肯定是存在的。

然後，當 n<kn<k 時需要煎 2 次，而上面的式子可能會得到 1 的錯誤答案。

因此，max(2,(2n+k−1)/k)max(2,(2n+k−1)/k) 即爲答案。