CF2081D MST in Modulo Graph

尝试用🍍把这个题目过了，想了一个 $O(n\log n\sqrt{n})$ 的做法然后假了。

显然如果 $k\times p_x\le a\le b< (k+1)\times p_x$，那么显然应该选择 $a$ 而不是 $b$。

对于 $p$ 一样的，我们先把他们合并了，然后在找每一个倍数的区间里最小的就行了。

时间复杂度是一个调和级数，复杂度是 $O(n\log^2n)$。

CF2057E Another Exercise on Graphs

先将所有边按照边权排序，考虑在询问时二分答案。

设现在二分到了第 $x$ 条边，那么我们将边权 $\le w_{x}$ 的边的边权改为 $0$，$>w_x$ 的改为 $1$，那么我们只需要判断此时 $a$ 到 $b$ 的最短路是否 $<k$ 即可。

那么考虑预处理出 $f_{i,j,k}$ 表示若边权 $\le w_i$ 的边权改为 $0$，其余边的边权是 $1$，$j$ 到 $k$ 的最短路，我们不难发现由 $f_{i-1}$ 到 $f_i$ 的变化就是将一条边的边权由 $1$ 改为 $0$，那么直接 $O(n^2)$ 更新即可。

$f_0$ 可以使用 floyd 求，时间复杂度 $O(n^2m)$。

因为这个图的边权只有 $0/1$，所以我们考虑将边权为 $0$ 的边的两个端点缩在一起，只有在这些新点之间的边才是有用的，显然如果将一条两个端点已经是属于同一个新点的边的边权由 $1$ 改为 $0$，这个操作显然是不会改变答案的，所以只有将两个新点合并的操作才是有用的，我们不难发现这种操作只有 $n-1$ 个，所以时间复杂度降为 $O(n^3)$。

AT_agc056_c 01 Balanced

容易想到差分约束系统，套路的我们设这个字符串的前缀和为 $s$，那么有限制：

$\begin{aligned} \left\{\begin{matrix} s_{l_i-1}-s_{r_i}=\dfrac{r_i-l_i+1}{2} \\ s_i-s_{i-1}\le 1 \\ s_i-s_{i-1}\ge 0 \end{matrix}\right. \end{aligned}$

发现建图有负权，只能用优先队列优化。

把 $0$ 看作 $-1$ 就没有负权了。

P3403 跳楼机

设 $k=ay+bz$，那么显然如果 $k$ 是合法的，$k+\alpha x$ 也是合法的。

设 $f(i)$ 表示在满足 $ay+bz\bmod x=i$ 的前提下，$ay+bz$ 的最小值。

$\begin{aligned} f(i)+y \ge f((i+y)\bmod x)\\ f(i)+z \ge f((i+z)\bmod x) \end{aligned}$

那么类似于差分约束系统，连边。

答案为：

$\begin{aligned} \sum\limits_{i=0}^{x-1} \lfloor\dfrac{H-f(i)}{x}\rfloor+1 \end{aligned}$

显然 $f(0)=0$，于是以 $0$ 为源点跑就行了，跑最短路。

P2371 国家集训队 墨墨的等式

简单加强即可。

AHOI2021初中组 地铁

于是不妨设 $d_i$ 表示 $1 \to i$ 的顺时针距离，根据定义，有 $d_1 = 0$，$d_{i+1} \ge d_{i} + 1$。

考虑到问题是在一个环上，而 $d$ 数组无法体现 $n$ 结点与 $1$ 结点之间的距离，所以我们再设一个变量 $C$ 表示环长，显然 $C \ge d_{n} + 1$。

考虑根据题意建立差分约束系统：

1. 对于第 $1$ 类信息：
   • 若 $S_i < T_i$，则有 $d_{S_i} - d_{T_i} \le -L_i$；
   • 否则，有 $d_{S_i} - d_{T_i} \le C-L_i$。
2. 对于第 $2$ 类信息：
   • 若 $S_i < T_i$，则有 $d_{T_i} - d_{S_i} \le L_i$；
   • 否则，有 $d_{T_i} - d_{S_i} \le L_i - C$。

我们知道，差分约束系统有解的条件为图中没有负环，也就是每个点的最短路是可求的。

那么，如果将 $C$ 视作未知数，图中的每一个环就相当于给定了一个关于 $C$ 的一次不等式，最终 $C$ 的取值范围必然是一段连续的区间。

如何求出 $C$ 的最小值 $l$ 和最大值 $r$ 呢？

以上界 $r$ 为例，考虑二分 $x$，带入 $C = x$ 进图找负环。

若没有负环，则 $r \ge x$。

若存在负环，对于该负环的不等式 $C$ 前面的系数 $k$ 进行分类讨论：

1. 若 $k = 0$，无解，因为这个环无论 $C$ 为何值都是负环。
2. 若 $k > 0$，则 $C$ 应当增大。
3. 若 $k < 0$，则 $C$ 应当减小。

答案为 $r - l + 1$，注意判断无限解的情况。

时间复杂度 $O(n(n + m ) \log V)$，$V$ 为值域。

P1543 POI 2004 SZP

感性理解，发现贪心是对的。

跑拓扑序乱贪就行了，细节有点多，拍了几组就过了。

P4436 HNOI/AHOI2018 游戏

钥匙在门左边的房间不可能从右边打开，反之同理。

对于在左边打开的门，我们定义其为这样 >，反之为 <。

把没有门的地方压到一起，对于：

>.> 的门向右拓展，对于 <.< 的门向左拓展，<.> 两边都拓展。

精细的实现可以做到 $O(n)$。

记录详情 - 洛谷 | 计算机科学教育新生态

CF1783F Double Sort II

建两个图，第 $1$ 个图把 $i$ 向 $a_i$ 连边，第 $2$ 个图把 $i$ 向 $b_i$ 连边。

考虑如果只有一个图，其次数就是 $n-g$，其中 $g$ 是其中环的个数。

这是容易理解的，我们需要的就是把一个图全部处理成自环。

那么这就相当于说给一个环选择一个点不动，那么直接给两个进行一个二分图匹配就行了。

具体的，我们一个环只能选择一个点，而我们匹配尽可能多。

那么我们给环进行编号，如果两个环有公共的点，给他们连边，做完了。

CF1635E Cars

如果输入了 $i,j$ 之间的关系，那么他们的方向一定是不同的。

跑一个二分图，把反向确定，确定了之后，考虑搞坐标。

那么会搞出一堆 $a_x<a_y$ 的条件，也就是 $a_x\le a_y-1$，那么我们把 $y\to x$ 连一个 $-1$ 的边。

跑一个拓扑，然后就完了

P3244 HNOI2015 落忆枫音

考虑对于一个 DAG 上的计数，如果一个节点的入度为 $in_i$，那么方案数为：

$\prod\limits_{i=2}^n in_i$

考虑如果出现了一个环，这样计数就会挂掉因为会有 $y\to x$ 的路径。

我们设 $f_x$ 为从 $x$ 到 $t$ 的所有路径中都没有出现环，剩下的路径随便选。

那么我们就可以把 $f_t$ 赋值，然后就有方程：

$f_x=\dfrac{\sum\limits_{\{to\to x\}\in E}f_{to}}{du_x}$

CF901C Bipartite Segments

没有偶还还全部是二分图，显然应该是一个森林。

搞一个 tarjan 去把环找出来，记录这个环最小和最大的编号，那么包含这个环的区间都死了。

我们设 $f_{x}$ 表示 $[x,f_x]$ 是合法的，但是 $[x,f_x+1]$ 不合法。

那么如果一个环的两个极值为 $mn,mx$，那么所有 $i\in [1,mn]$ 的 $f_i$ 都要 $f_i\gets \min(f_i,mx-1)$。

求解出 $f$ 后答案就很显然了：

$ans=\sum\limits_{i=l}^r \min(f_i,r)-i+1$

简化一下：

$ans=\dfrac{(2-l-r)\times(r-l+1)}{2}+\sum\limits_{i=l}^r \min(f_i,r)$

因为 $f_i$ 是单调的，所以可以二分一下 $\min$ 取到的后缀，于是复杂度为 $O(n+q\log n)$。

CF1835D Doctor's Brown Hypothesis

因为需要分别存在 $x\to y$ 和 $y\to x$ 的路径，所以满足题目要求的 $(x,y)$ 肯定是在一个 SCC 中的。

对于每一个 SCC 分开考虑，最后将结果相加即可，下面讨论的图都是强连通的。

假设图中所有的环的长度为 $len_1,len_2,\cdots,len_m$，那么记 $d=\gcd\limits_{i=1}^m len_i$。

下面讨论的图都是在在对 $d$ 取模意义下的。

在下的 SCC 中有一些性质：

如果存在一条路径 $a\to b$，而且边权为 $w$，那么就可以构造出 $b\to a$ 而且边权为 $-w$ 的路径。

证明：

因为 $a,b$ 在同一个强连通分量内，所以它们必然在一个环中，假设这个环的边权和为 $s$。那么从 $b$ 出发绕着环走 $t$ 圈，这样的贡献就是 $s\times t$ 也就是 $0$。

所以只要在最后一圈的时候直接停在 $a$ 那么就相当于构造出了一条 $b\to a$ 的边权为 $-w$ 的路径。

另外有一个性质，如果强连通分量上有一个环，那么所有的点都可以看作在这个环上。

证明：

假设 $a$ 在长度为 $x$ 的环上，而 $b$ 不在。

假设 $a\to b$ 的路径长度为 $w$，那么根据上面的性质，显然 $b\to a$ 的长度就是 $w$。

那么就可以构造 $b\to a\to b$ 的路径，在到达 $a$ 之后可以随意的在环上行走，而结束后又可以原路返回。容易理解，这样路径的长度为 $w+x+(-w)=x$。

换而言之：

$x\to y$ 的一条复杂路径可以表示为 $x\to y$ 的简单路径的长度加上 $\sum\limits_{i=1}^m a_i\times len_i$，其中 $\forall a_i\in \mathbb{N}$。

这样就解决有些 $a_i=0$ 但是却经过了一些其他必须要经过 $i$ 的环才能到达的环的问题。

最后还有一个性质，如果有一条 $x\to y$ 的路径长度为 $Len$，那么不管最初的简单路径怎么选择，其长度在模 $d$ 意义下都可以做到为 $Len$。

证明：

由第一个性质可以做出构造，先让长度为 $a$ 的路径走负边权的路原路返回再走一次长度为 $b$ 的路，这样结果就是 $a+(-a)+b=b$ 了。

考虑如何求解一个所有的环长的 $\gcd$。

对于一个 SCC 跑一个叶向生成树，显然环有两种情况：一条非树边和一些树边组成，多条树边和一些树边组成。

因为第二种情况，这些环的长度都可以通过第一种环通过加减得到，所以显然不会对 $\gcd$ 产生影响。

具体的 $\gcd(a,b)=\gcd(a,b,a+b)$，证明如下：

设 $\gcd(a,b)=g$，那么 $a=\dfrac{a}{g}\times g$，$b=\dfrac{b}{g}\times g$，所以就有 $a+b=g\times ({\dfrac{a}{g}+\dfrac{b}{g}})$。

于是就遍历这个 dfs 树，如果遇到了返祖边那么就更新 $\gcd$。

假设 $x\to y$ 存在一条非树边，那么计算方法为 $\lvert \text{dep}_{x}-\text{dep}_y+1\rvert$。

显然对于返祖边，这样是正确的，考虑证明对于横叉边的正确性。

假设有横叉边 $x\to y$，那么环的长度就应该为 $\text{dis}(rt,x)+\text{dis}(y,rt)+1$。

通过上面的性质，因为 $\text{dis}(rt,y)\equiv -\text{dis}(y,rt)\pmod{d}$，所以得到 $\text{dis}(rt,x)+\text{dis}(y,rt)+1\equiv \text{dis}(rt,x)-\text{dis}(rt,y)+1\equiv\text{dep}_x-\text{dep}_y+1\pmod{d}$。

回到这个题目的具体要求，假设 $x\to y$ 的简单路径长度为 $Len$，那么题目的要求就是：

$Len+\sum\limits_{i=1}^m a_i\times len_i\equiv k \pmod{d}$

因为 $\forall i\in[1,m]\cap\mathbb{Z}$ 都满足 $d\mid len_i$，所以 $\sum\limits_{i=1}^m a_i\times len_i\equiv 0\bmod{d}$，也就得到了其实题目的要求是 $Len\equiv k$。

因为 $x\to y$ 的长度和 $y\to x$ 的长度需要一样，所以我们先考虑判断 $\text{dis}(x\to y)\equiv \text{dis}(y\to x)\pmod d$。

因为第三个性质，所以不妨我们直接让 $x$ 走到 $rt$ 然后再走到 $y$，反之同理。

因为 $x\to y$ 的边权为 $w$ 那么 $y\to x$ 的边权就为 $-w$，所以就相当于判断：

$-\text{dis}(rt,x)+\text{dis}(rt,y)\equiv \text{dis}(rt,x)-\text{dis}(rt,y)\pmod d$

因为 $x$ 和 $y$ 到 $rt$ 的距离就相当于 $\text{dep}$，所以就可以得到：

$2\times(\text{dep}(x)-\text{dep}(y))\equiv 0\pmod{d}$

通过瞪眼法可以得到方程的解为 $\text{dep}(x)=\text{dep}(y)$，或者 $2\mid d$ 且 $\text{dep}(x)-\text{dep}(y)\mid \dfrac{d}{2}$。

当然，在最后计算答案的时候需要满足 $\text{dep}(x)\equiv k\pmod d$。

时间复杂度 $O(n)$，做完了。

CF1815F OH NO1 (-2-3-4)

给定一张无向图，每个点都有点权 $w_i$。你需要为每条边定向，记 $d_i$ 为点 $i$ 在所有边被定向后的入度，你需要使得对于每条边 $(u,v)$ 都有 $w_u+d_u\neq w_v+d_v$。

上述问题（记作问题 $A$）的一个简单做法是初始设所有 $d_i=0$，然后每次找 $w_i+d_i$ 最小的点 $i$，将于 $i$ 相连的所有未定向边 $(i,x)$ 改为 $i\to x$。

通过这样的构造方法，得到的图肯定是有解。

然后我们发现原问题可以转化为问题 $A$。

具体来说，如果给一个环上的点分别赋值为 $1,2,3$ 那就这些点就会分别增加 $3,4,5$。

所以如果把所有点先增加 $3$，那么就相当于给这些边定向，于是就做完了。

CF1804F Approximate Diameter

有点问题，首先一个图的直径只能通过 $n$ 次 bfs 求得，但是有设 $dis_x$ 为从 $x$ 出发的经过 bfs 得到的最大值，那么肯定有：

$\lfloor\dfrac{d(G)}{2}\rfloor\le dis_x\le d(G)$

所以我们可以算出当前一个 $dis_x$ 然后计算可以向后用多少才会比 $2\times dis_x$ 大。

时间复杂度 $O(n\log n)$，做完了。

CF1648E Air Reform

这题需要用 Kruskal 重构树，先速通了。

首先拿到一个图，把这个图搞一个最小生成树出来，然后把这个树里的边从小到大一次拿出来。

假设这个边连接的是 $x,y$，那么新建一个节点其点权设置为 $(x,y)$ 的边权。

把新建的节点和 $x,y$ 连边，如果 $x$ 或者 $y$ 已经在原图上出现过那么连接其根节点以替代。

void Ex_Kruskal()
{
    int cnt=n;
	sort(e+1,e+m+1,cmp);
    for (int i=1;i<2*n;++i) f[i]=i;
    for (int i=1;i<=m;++i)
	{
        int u=get(e[i].x),v=get(e[i].y);
        if (u!=v)
		{
			++cnt;
        	f[u]=f[v]=cnt;
        	val[cnt]=e[i].z;
        	add(cnt,u);add(cnt,v);
        	if (cnt==2*n-1) break;
        }
    }
}

有些牛逼的性质：

• 是一棵二叉树。
• 如果是按最小生成树建立的话是一个大根堆。
• 原图中两个点间所有路径上的边最大权值的最小值 = 最小生成树上两点简单路径的边最大权值 = Kruskal 重构树上两点 LCA 的点权。

利用这个性质，我们可以找到到点 $x$ 的简单路径上的边最大权值的最小值 $\le val$ 的所有点 y。可以发现都在 Kruskal 重构树上的某一棵子树内，且恰好为该子树的所有叶节点。

根据题目的意思，如果我们得到补图的 Kruskal 重构树，那么我们就做完了。

但是显然不能把补图处理出来，这是 $O(n^2)$ 的，于是我们考虑直接求出补图的 MST，据说可以用 Boruvka 直接求。

对于每一个点，我们需要找到一个在原图的 Kruskal 重构树中最靠下的 $x$ 满足：

• 这个祖先的子树中存在与 $x$ 不在同一个连通块中的点。
• 上述点中存在 在原图中与 $x$ 无边直接相连 的点。

我们给每一个点开两个指针，分别指向在 dfs 序前面和后面的最靠近这个点的满足条件的位置。

那么我们需要的就是这两个点与现在处理的点的 LCA 的较深者。

我们用数据结构快速跳过连通块，因为第二个限制一共遇到 $O(m)$ 次，所以直接暴力处理。

至于数据结构，直接把连通块暴力处理出来就行了，时间复杂度是 $O((n+m)\log n)$ 的。

CF1567F One-Four Overload

有点小牛逼的题目，感觉自己不可能想到。

• 只有 $1$ 和 $4$，那么考虑二分图染色。
• 如果 $\texttt{X}$ 的旁边有奇数个 $\texttt{.}$ 那么显然无解。
• 如果有 $2$ 个 $\texttt{.}$ 那么直接连接这两个点就行了。
• 如果有 $4$ 个 $\texttt{.}$ 那么比较复杂，我们需要连接“左边”和“上面”，“右边”和“下面”。

正确性懒得证明，时间复杂度为 $O(n)$。