2020 ICPC 濟南站感想和部分題解
在上次 CCPC 打銅之後，我們打了一次很失敗的校賽二等獎。濟南報名之後，正式比賽之前，我感覺自己的狀態和心態都並不是很好。準備這次比賽時想着拿銅有點小虧，拿銀就比較正常了。
在賽場上，簽到四題的部分共 WA 一發，還算比較穩，但並不快，排名在銀區。
然後自然是跟榜看 A、L，但是都沒有想出做法，尤其是 A 涉及的矩陣變換等是我最弱的方向。
後來發現有人過 J 題之後，我也開始看，一開始想在反圖（原圖不存在的所有邊組成新圖）裏找強連通分量來構造，後面發現似乎並不可行。然後我想起了樹上可以相鄰點異色染色之類的操作，就發現它可以染兩種色，同色點之間無邊，這樣這題一下子就豁然開朗了。很快地過了 J，排名一下子到了 9。
然後就進入了罰坐模式，期間我甚至想提前放棄🌚。A 題過的隊越來越多，我們卻遲遲找不到做法。由於我矩陣、代數等方面不太行，幫不上忙，便把所有沒過的題都看了，然後也沒發現有思路的，心態有點炸。A 題隊友找到了把等式變形，矩陣按列拆開之後每列算自由度的做法，繼而想到高斯消元和線性基。因爲高斯消元算各列，總的複雜度是 $O(n^4)$，即 $1.6 \times 10^9$，感覺過不了，然後線性基連板子都沒人看得懂，又開始卡。直到最後沒辦法才嘗試用高斯消元去做，結果直接過了。賽後大佬們都說高斯消元本來複雜度就卡不滿🌚，另外這題也可以 bitset 優化，不過沒優化也過了。
A 題過了之後金牌應該是穩了，我一下子心態好了非常多，然後我們再一起看 L，想到了枚舉後面幾位的方法，但是只有不到半小時，來不及過了。不過金牌已經有了，這題過了也離出線差一題，所以也沒太大影響。
這場我前中期發揮還可以，但在 A 卡題過程中不僅沒幫上什麼忙，反而因爲自己心態不好，對隊友心態也有些影響。很感謝他們並沒有一起心態爆炸，並且最終過了這題，讓我們第一次打 ICPC 就獲得了金牌的好成績。
A Matrix Equation
題意：已知相同大小的 0-1 方陣 $A$ 和 $B$，定義運算 $\times$ 是普通的矩陣乘，所有元素對 2 取模。定義 $\odot$ 爲對應位置元素相乘（也就是相與），求使等式 $A \times C = B \odot C$ 成立的 $C$ 的個數，對 998244353 取模。
很顯然，$C$ 的一個元素只會影響它所在的那一列，所以可以以列爲單位分開考慮。
好像是只考慮一列之後，就可以得出方程組，然後用高斯消元算自由度。這題隊友過的，我先溜了🌚。
C Stone Game
題意：有若干堆石頭，每堆有最多三個石頭，MianKing 想把它們合併爲一堆。他每次可以把任意兩堆合併爲一堆，如果合併前兩堆石頭各有 $x$、$y$ 個，則代價爲 $(x \mod 3) (y \mod 3)$，求最小總代價。
首先，石堆的個數只有模 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$），後面的在不比前面的少的情況下儘量減。並列的只能一起減到它們的 $L$ 中的最大值。
具體做法可以把 $R$ map 到對應的最大 $L$，也可以對 $R$ 並列的按 $L$ 從大到小排，等等。
G Xor Transformation
題意：通過最多五次操作把 $x$ 變成 $y$，每次操作是任選滿足 $0 \le a < x$ 的 $a$，令 $x = x \oplus a$。保證 $y < x$。
第一次可以把 $x$ 補滿成 $2^k-1$ 的形式，第二次則直接變成 $y$。由於允許 $a = 0$，這種做法無需任何特判。
J Tree Constructer
題意：已知一棵無向樹，要求爲每個點賦值（$[0,2^{60})$），使有連邊的兩點所賦值按位或結果等於 $2^{60}-1$，無連邊的兩點所賦值按位或不等於 $2^{60}-1$。輸出一種方案即可。
這題一開始往反圖方向考慮去了，後面發現這樣做位數應該不夠。
按染色思路，相鄰邊異色，染成兩色，設較少的顏色爲 0，多的爲 1，這樣顯然可以構造互補關係。
先對每個顏色爲 0 的點，分配一位，置 0，其它位置 1。再爲了防止同色互連，把一個標記位置 0。
這樣顏色爲 1 的與它互補，標記位置 1，分配給與它相鄰的各點的位置 1，其它置 0。
最多 51 位，加上顏色爲 1 的各點共同的零（剩下 9 位都是，需要 1 位），共需 52 位。
M Cook Pancakes!
題意：經典問題，平底鍋煎煎餅，兩面都要煎，3 個餅能同時煎 2 個，最少 3 次可以煎完。求 $n$ 個餅能同時煎 $k$ 個，最少幾次能煎完，$n,k > 0$。
現在我們應該很容易想到，$2n/k$ 向上取整的方案肯定是存在的。
然後，當 $n < k$ 時需要煎 2 次，而上面的式子可能會得到 1 的錯誤答案。
因此，$\max(2, (2n+k-1)/k)$ 即爲答案。