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