在上次 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)$ 即爲答案。