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