小 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 分。