VP 记录 - 2022 CCPC 广州站

比赛链接

进度: 7 / 13

题目概览

题号 1标题 2做法
*AAlice and Her Lost Cat
*BAyano and sequences
CCustoms Controls 2图论,构造,缩点,并查集 / 差分约束
*DDigits
EElevator签到 (前缀和)
*FEquations
*GGame
HGameX签到 (博弈论)
IInfection树上背包,概率 DP
JMath Exam容斥,前缀和,折线计数
KMiddle Point Graph图论 -> 无向图三元环 & 四元环计数
LStation of Fate签到 (组合数学)
*MXOR Sum

官方题解

A - Alice and Her Lost Cat

解题思路

复杂度

代码参考

Show code

B - Ayano and sequences

解题思路

复杂度

代码参考

Show code

C - Customs Controls 2

解题思路

设从 \(1\)\(i\) 的答案为 \(d_i\)

显然若对任意点 \(v\), 若有弧 \(u_1\to v\), \(u_2\to v\), 则 \(d_{u_1}=d_{u_2}\)

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

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

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

要做到这一点,若有弧 \(u\to v\), 我们只需令 \(w_v=b_{s_v}-b_{s_u}\) 即可

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

复杂度

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

代码参考

Show code

D - Digits

解题思路

复杂度

代码参考

Show code

E - Elevator

代码参考

Show code

F - Equations

解题思路

复杂度

代码参考

Show code

G - Game

解题思路

复杂度

代码参考

Show code

H - GameX

代码参考

Show code

I - Infection

解题思路

复杂度

代码参考

Show code

J - Math Exam

解题思路

复杂度

代码参考

Show code

K - Middle Point Graph

解题思路

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

三元环和四元环的求法可参照 笔记 - 无向图连通子图 & 环计数 相关章节

复杂度

代码参考

Show code

L - Station of Fate

代码参考

Show code

M - XOR Sum

解题思路

复杂度

代码参考

Show code


  1. 打 * 的是还没写的题↩︎

  2. 带超链接的是找到了原题或原型↩︎