小 Q 与签到

算法 1

对于比较小的 $k$，手动构造一个解。

期望得分 20 ~ 40 分。

算法 2

暴力枚举 $x,y,z$。显然答案不会超过 $k$。

时间复杂度 $O(k^3)$。

期望得分 40 分

算法 3

经过思考发现枚举了 $x, y$ 后，$z$ 可以通过扩欧计算出来。

时间复杂度 $O(k^2 \log k)$

算法 4

观察到在这个式子中，$x,y,z$ 的地位均等。

期望得分 100 分。

小 Q 与图论

算法 1

暴力枚举出选边涂色的顺序。

时间复杂度 $O(m!)$。

期望通过 Subtask 1，得分 13 分。

算法 2

图为一条链时，链的两端的点只有一条边，因此会被自动涂色。随后，剩下的边也会自动涂色……

图为一棵树时同理。

因此，显然你不需要做任何操作，输出 $0$ 即可。

期望通过 Subtask 3 与 Subtask 4，得分10分。结合算法 1 可得到 23 分。

算法 3

当图为仙人掌时，注意到任意一条边只在一个简单环上，因此只要把这个环破开即可。问题转化为如何找环，可以简单地线性做到。

时间复杂度 $O(n)$，期望通过 Subtask 5，得分 25 分，结合算法 1,2 可得到 48 分。

算法 4

考虑 $n,m \leqslant 300$。

贪心地想，如果有白色度数为 $2$ 的节点，优先涂色。这样做显然是正确的。

更新的复杂度显然不会超过 $O(m)$，时间复杂度 $O(mn)$。期望通过 Subtask 2，得到 20 分。结合上面的做法可以得到 68 分。

算法 5

由于图不一定联通，且每个联通块之间显然是独立的。不妨考虑其中一个联通块 $G$。

首先，我们找到 $G$ 的一个生成树 $T$，然后考虑所有的非树边构成的几何 $H$。设 $t = |G| - |H|$。显然，对于此联通块，答案的上界为 $t$。下面，我们来证明答案的下界也是 $t$。

假设有一种涂色方案使得方案少于 $t$。我们把涂黑操作看作是“删边”，那么相当于如果一个联通块被删成了一棵树，那么就会自动消失。如果这种方案使得图仍然联通，就必定存在一个环（因为 $n$ 个点的联通无向简单图必定只有 $n-1$ 条边），若不然，则递归归纳即可。

综上，我们只需要找到每个联通快的生成树。$O(n \log n)$，期望得分 100 分。

算法 6

注意到，我们其实不关心这棵生成树是啥，只要判一下联通就好了。

时间复杂度 $O(n \alpha (n))$，期望的分 100 分。

算法 7

对于算法 4，有个显然的性质是，所有节点更新次数之和不会超过 $\sum^n_{i=1} \deg i = 2m$。因此采用个数据结构维护。

小 Q 与搜索

算法 1

直接暴力枚举。时间复杂度 $O(3^n \times \text{Poly}(n))$，期望得分 0 ~ 90 分。

所以这不是sb题吗……暴力就90分了，怎么没人写啊

算法 2

卡常数。

期望得分 100 分。

算法 3

四毛子算法。时间复杂度 $O(3^n / \log n)$。期望得分 100 分。