SNCPC 2024
SNCPC2024C: Seats
题意
找到长为 $n$ 的数组 $b_i$ ($1 \leq i \leq n, 1 \leq b_i \leq 2n$) 满足 $\forall i \neq j,b_i \neq b_j$ 且 $\forall i, b_i=i$ 或 $b_i=a_i$。且最大化 $b_i = a_i$ 的个数。你只需要输出最多的个数即可。
思考
观察到每个点可以有多个入度，但最多只有一个出度。这简化了这个问题。
发现整张图可能会存在的原子组成部分：树、环、基环树（内向）。画图可以发现以下结论：
对于树，满足树上最长链最优；对于环，要么环上节点同时被满足，要么没有节点会被满足。
对于基环树，不难发现只能满足环（满足环的话树们就没法满足，但不满足环的话环上的点也会保持不动，也会使得树们没法满足）。
具体做法：可以采用拓扑排序的方式，先统计所有树的最长链的答案。设 $maxx[x]$ 表示指向 $x$ 的节点所携带的链的长度的最大值，当拓扑删到树上的最后一个点时，再进行答案的统计（这样可以保证在基环树上的节点不被统计到答案，因为基环树上只有环上节点能被满足）。最后再通过染色法把基环树上的环以及普通的环直接统计答案标记即可（upd：可以省去这一步，直接将拓扑排序中未入队的点直接累积入答案即可）。
Code：https://paste.ubuntu.com/p/sHSrrJx5r5/
SNCPC2024G: Disappearing Number
题意
让计数系统中的一个数字 $x (1 \leq x \leq 9)$ 消失，计算某数字在该计数系统下的新排名。
思考
vp时想的过于复杂，被题目背景中的 dp 带偏了，通过打表找到了递推公式，又复杂的对数字进行拆分依次进行答案的累积……
实际可以发现这个决定不会影响在什么时候由 $k$ 位数变为 $k + 1$位数，但会使得 $k$ 位数更早去变为 $k + 1$ 位数。所以就是类似 九进制 的原理，对于每一位单独考虑，若该位的数字大于 $x$，则对它减一。把该新数看作九进制下的数字，转换为十进制即可。
且还是少用 pow 函数，不要忽视浮点误差。
Code：https://paste.ubuntu.com/p/tVMt5CwNRt/
SNCPC2024L: Chess
题意
初始有 $x$ 个棋子，两个人轮流行动拿走棋子，拿走的棋子数量 $y$ 要求满足在 $k$ 进制下各位数的乘积是 $y$ 的因子，寻找一个最小的 $k$ 使得先手必胜。
思考
题目无关信息其实挺多，乘积、因子这些。重要的是 0 这个数字。不难发现每次拿走的棋子数量的 $k$ 进制表示下是没有 0 的（有 0 必定导致积为 0，必定不合法）。
考虑最低位，若 $x$ 在 $k$ 进制下最低位为 0，此时先手必败：
- 先手的第一次选择必定会破坏“最低位为0”的情况，因为他要拿走一个合法的数
- 此时最低位为 $w$，那么后手只需要拿走 $w$ 即可让最低位又变回 0（注意，拿 $w$ 肯定是合法的）。
- 那么 step 1 和 2 会继续依次进行，最终先手必定会输掉游戏。
那么如果最开始的时候，$x$ 在 $k$ 进制下最低位不为 0，结局就会翻转。
所以我们要找的 $k$ ，应该是最小的且在 $k$ 进制下最低位非 0 的，即 $k$ 是 $x$ 的最小非因子（$x \mod k \neq 0$ $\iff$ $x$ 在 $k$ 进制下最低位非 0），可以在对数时间复杂度下求解。
SNCPC 2024