版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

仓库源文，站点原文

比赛链接

进度: 7 / 13

题目概览

官方题解

{% pdf /archives/ccpc-gzr2022/problems.pdf 600px %}

A - Alice and Her Lost Cat

解题思路

复杂度

代码参考

{% icodeweb blog lang:cpp ccpc-gzr2022/A.cpp %}

B - Ayano and sequences

解题思路

复杂度

代码参考

{% icodeweb blog lang:cpp ccpc-gzr2022/B.cpp %}

C - Customs Controls 2

解题思路

设从 $1$ 到 $i$ 的答案为 $d_i$

显然若对任意点 $v$, 若有弧 $u_1\to v$, $u2\to v$, 则 $d{u1}=d{u_2}$

我们用并查集将 $d$ 相同的点缩成一个点, 因为点权是正的, 所以缩点后的图应该也是个 DAG, 否则不满足要求

设点 $i$ 在缩点后的图中对应的点编号为 $si$, 之后我们对缩点后的图跑一遍 BFS 求一下每个点的拓扑序 $b{s_i}$

最后我们只需让所有路径的点权和为 $b_{s_n}$ 即可

要做到这一点, 若有弧 $u\to v$, 我们只需令 $wv=b{sv}-b{s_u}$ 即可

有一个小技巧: 我们可以将判环和 BFS 合起来, 我们记录一下缩点后的图的每个点的入度 $\deg_{in}(si)$, 若 $\deg{in}(s_1)>0$, 则显然不满足要求, 之后我们 BFS 时遍历到一个点时将这个点的入度减 $1$ (相当于删去刚刚走过的这条弧), 若这个点入度为 $0$ 了则入队, 这样图中没有环当且仅当每个点都被恰好遍历一次

复杂度

$O(m\alpha(n)+n)$

代码参考

{% icodeweb blog lang:cpp ccpc-gzr2022/C.cpp %}

D - Digits

解题思路

复杂度

代码参考

{% icodeweb blog lang:cpp ccpc-gzr2022/D.cpp %}

E - Elevator

代码参考

{% icodeweb blog lang:cpp ccpc-gzr2022/E.cpp %}

F - Equations

解题思路

复杂度

代码参考

{% icodeweb blog lang:cpp ccpc-gzr2022/F.cpp %}

G - Game

解题思路

复杂度

代码参考

{% icodeweb blog lang:cpp ccpc-gzr2022/G.cpp %}

H - GameX

代码参考

{% icodeweb blog lang:cpp ccpc-gzr2022/H.cpp %}

I - Infection

解题思路

复杂度

代码参考

{% icodeweb blog lang:cpp ccpc-gzr2022/I.cpp %}

J - Math Exam

解题思路

复杂度

代码参考

{% icodeweb blog lang:cpp ccpc-gzr2022/J.cpp %}

K - Middle Point Graph

解题思路

带讨论, 具体可以参照题解

三元环和四元环的求法可参照 {% post_link count-csgr-graph %} 相关章节

复杂度

代码参考

{% icodeweb blog lang:cpp ccpc-gzr2022/K.cpp %}

L - Station of Fate

代码参考

{% icodeweb blog lang:cpp ccpc-gzr2022/L.cpp %}

M - XOR Sum

解题思路

复杂度

代码参考

{% icodeweb blog lang:cpp ccpc-gzr2022/M.cpp %}