做题记录 25.4.9

· · 个人记录

比赛

\purple\odot P3511 [POI 2010] MOS-Bridges

二分答案，转化为一张图中有有向边和无向边，要给无向边定向使之有欧拉回路

有欧拉回路等价于每个点出度等于总度数的一半

因此建立二分图，每个左部点为一条边，每个右部点为一个点，左部点只能匹配一次，第 i 个右部点匹配 \frac{deg_i}2 次

对于有向边 u\to v，左部点向右部的 v 连边

对于无向边 u-v，左部点向右部的 u,v 分别连边

若所有左部点都匹配，则存在欧拉路，此时若左部 i 匹配右部 j，表示第 i 条边定向为指向 j

根据定向结果建图求出欧拉路即可构造方案

时间复杂度 O((n+m)^{1.5}\log V)，可优化到 O((n+m)^{1.5}\log m)

代码

参考

\textcolor{black}\odot CF1458D Flip and Reverse

令 0 为 -1，1 为 +1，令 s_i 为 1\sim i 的前缀和，从 -n\sim n 分别建立一个点，所有 s_i 连向 s_{i+1}（其中 i<n），则序列可以看做一条从 0 开始的欧拉路

序列中的操作等价于把欧拉路中一个环的遍历顺序取反

因此任意一条从 0 开始的欧拉路都可对应一个合法序列

由于要求序列字典序最小，等价于要求欧拉路字典序最小

有一种 O(n) 的简单实现：令 cnt_{i,0} 表示目前为止 i\to i-1 的数量，cnt_{i,1} 表示目前 i\to i+1 的数量

令 x 表示目前所在的点，初始 x=0，cnt 的初始值容易预处理

若 cnt_{x,0}>0 且 cnt_{x-1,1}>0，则说明存在一个 x\to x-1\to\cdots\to x-1\to x 的环，因此当前位置可以 填 0，令 cnt_{x,0}\gets cnt_{x,0}-1,x\gets x-1

否则若 cnt_{x,1}>0，则此时要么没有向 x-1 的边，要么存在向 x-1 的边但没有回到 x 的边，两种情况下都不能先移到 x-1，因此当前位置只能填 1，令 cnt_{x,1}\gets cnt_{x,1}-1,x\gets x+1

否则当前位置可以填 0，令 cnt_{x,0}\gets cnt_{x,0}-1,x\gets x-1

总时间复杂度 O(\sum n)

代码

参考

\textcolor{black}\odot CF1163F Indecisive Taxi Fee

删边最短路模板题

代码

\purple\odot P8456 「SWTR-8」地地铁铁

假设边权为 0/1

总点对数量为 \binom n2，考虑减去不合法的得到合法数量

不合法的 (x,y) 分为三类：

前两种计算方式相同，以第一种为例，可证若一个点双中存在 1 边，则圆方树上经过这个点双的点对之间一定存在经过这条 1 边的路径，因此删去含 1 边的点双内的所有边，满足第一种条件的点对数量为连通块大小选 2 之和

对于第三种情况，显然满足要求的 (x,y) 必在同一点双内，可证一个点双内至多有一组这样的 (x,y)，且一个点双内存在满足要求的点对 当且仅当 点双内存在恰好两个点满足点同时含有指向同一点双内点的 0 边和 1 边

通过一次 \text{Tarjan} 求出每个点双内的边和点，容易处理情况三

情况二容易通过并查集实现，也可建图后直接统计连通块

时间复杂度 O(n+m\alpha(n))，可做到 O(n+m)

代码

参考

\textcolor{black}\odot CF1515G Phoenix and Odometers

显然各个强连通分量之间独立，因此分开考虑

假设一个强连通分量中存在长为 a 和 b 的环，则这个连通分量可以表示出长为 ax+by\;(x,y\in\mathbb N^+) 的环，根据裴蜀定理，相当于能表示出所有 \gcd(a,b)\mid w（不需要考虑 w<\min(a,b) 的情况，因为 x,y,a,b,w 都是对询问中的 t 取模），因此问题转化为求出一个强连通分量中所有环长的 \gcd 和

先一次 \text{Tarjan} 求出所有强连通块，然后对连通块进行 \text{dfs}，求出每个点到搜索树根的距离 d_u，对于非树边 (u,v,w)，令当前连通块的 \gcd 和对 d_u-d_v+w 取 \gcd

时间复杂度 O(\sum (n+(m+q)\log V))

代码

参考

\purple\odot CF1361E James and the Chase

显然一个点合法当且仅当以这个点为起点进行 \text{dfs} 时，\text{dfs} 树上只存在返祖边和树边

这样可以 O(n) 判断一个点是否合法

假如已经找到一个合法的点 u，考虑如何找到所有合法的点

可证非根结点 u 合法当且仅当其子树内只存在恰好一条到 u 的祖先（不含 u）的返祖边，满足指向的点合法

先通过树形 dp 求出返祖边的数量和具体指向的结点，然后通过一次 \text{dfs} 找到所有合法点，时间复杂度 O(n)

随机 100 次并判断，若存在一个合法的 u 则由其求出答案，否则直接判断无解，错误概率只有 0.8^{100}\approx 2\times10^{-10}

时间复杂度 O(\sum Tn)，其中 T 为随机次数 100

代码

参考