图上 DS 刷题笔记

sunkuangzheng / 2024-10-21 / 原文

希望能在 11.15 前刷完 CF 上 $2800 \sim 3400$ 的图论 + DS 题。

自己切掉的题都在这个题单了，建议收藏这个动态更新超水紫黑题的题单！！111（题单还包含一些 trees + DS 的 $2800 \sim 3400$，这部分的做题笔记受到密码保护，密码可以私信找我要。）

CF1566G Four Vertices

开门红。

最优方案不可能包含四条及以上的边，一个四条边的方案一定可以通过调整端点删去一条边。

如果我们选择了三条边，则一定是一个点的三条出边，否则可以被两条边替代。这种情况容易维护：对每个点维护前三小出边，再全局开一个 set 维护每个点的前三小边的和。

剩余情况都是两条边。直观的想法是找到最小和次小边 $(a,b),(c,d)$。如果 $a,b,c,d$ 互不相同则直接结束，否则设 $d = a$，两条边分别为 $(a,b),(a,c)$。

重要观察：$(a,b),(a,c),(b,c)$ 中至少有一条边被选择。
Proof：假设我们已经选择了一条边 $(u,v)$。如果 $(u,v) \ne (b,c)$，则 $(a,b),(a,c)$ 两条边至少有一条可以选。由于它们是最小的两条边，故一定会选。

现在问题变成，维护边集 $\{(u,v,w)\}$，每次查询给出 $(a,b)$，找到一对 $(u,v,w)$ 满足 $a,b,u,v$ 互不相同且 $w$ 最小。

将所有边挂在较小端点 $u$ 上，设询问的 $a < b$。将左端点拆分成三段区间 $[1,a),(a,b),(b,n]$，每个区间内查一个 $w$ 的右端点 $v$ 满足 $v \ne a,v \ne b$。线段树每个节点维护 $w$ 前三小的 $v$ 即可。

时间复杂度 $\mathcal O(n \log n)$，常数非常非常大。实现时请注意常数，注意常数，注意常数，不是所有单 $\log$ 都能轻松过 $10^5$。

CF1419F Rain of Fire

首先二分答案 $mid$，将点合并成若干个连通块。考虑将每个点向上下左右四个方向引一条长度为 $mid$ 的线段，不难发现我们需要考虑的点只有两种：

对于两个横/纵坐标相同的点，如果其距离小于等于 $2mid$，且这两个点恰好属于这张图仅有的两个连通块，那么我们可以在线段的交点处放点。
否则，相交方式一定是垂直相交。我们在交点处放点。

交点显然只有 $\mathcal O(n^2)$ 个。可以预处理出每一个交点到旁边四个点的距离以避免二分里面再带 $\log$。

总复杂度 $\mathcal O(n^2 \log n)$，但是会被卡常。最有用的卡常是：

if(time > 1900) {
    cout << -1;
    return 0;
}

CF1056G Take Metro

注意到在环上走 $t$ 步和 $t \bmod n$ 步没有区别，因此暴力做掉 $t \bmod n$ 步后，剩余的是走 $\dfrac{t}{n}$ 个 $n - 1,n - 2,\ldots,0$。这一部分显然可以倍增处理。

问题是怎么对 $1 \sim n$ 的每一个 $i$ 都求走 $n$ 步后会到哪里。注意到移动方式很简单，从 $i$ 到 $i-1$ 就是一些简单的复制拼接。这里需要上 DS 了：区间复制，区间移动，需要使用可持久化平衡树完成。本题可以直接用 rope 水过。

CF757F Team Rocket Rises Again

套路的建出最短路 DAG，问题变为 DAG 上删一个点使得和 $s$ 不连通的点数最多。

【支配树】可以做到对每一个 $u$ 都求出删去它后和 $s$ 不连通的点数，DAG 上建立支配树的方法如下：

称 $u$ 支配 $v$ 当且仅当所有 $s \to v$ 的路径都经过 $u$。任意两个支配 $u$ 的点 $x,y$ 一定呈支配关系（如果 $x$ 支配 $u$ 但 $x,y$ 无支配关系，那么会存在路径 $1 \to x \to u$ 而不经过 $y$）。
把每个点和最近的支配它的点连边得到支配树。
$u$ 支配 $v$ 的充要条件是对于 $v$ 的所有入边 $(w,v)$，$u$ 都支配 $w$。
结合以上不难发现 $u$ 的支配父亲就是支配树上 $w$ 的 LCA。

动态加叶子维护 LCA 可以倍增完成。

CF1654G Snowy Mountain

思路打开，着眼全局。

首先很容易发现的是，反复横跳只会在最后一条等边处发生，调整易证。

然后我花了两个小时也没想到题解一句话带过的结论：

结论：设 $u$ 能到达的 $f_v$ 最小的可以反复横跳的点是 $v$，答案是 $2f_u - f_v$。
Proof：考察从 $u$ 一直到 $v$ 反复横跳完所有动能的整个过程，一定走了 $2f_u - 2f_v$ 步。加上剩下的一段路即为 $2f_u - f_v$。

对每个点求 $v$ 只需要点分治即可。

CF1470E Strange Permutation

首先注意到一种方案里对字典序影响更大的是最开始的修改，不妨对每个询问都先考虑其第一个修改在哪里。将所有可能的位置排序，然后对每一个第一个修改，计算出其后面修改的方案数，然后二分找到那个对应的修改后，递归入一个后缀的子问题。

由于 $c \le 4$，递归层数最多只有 $4$ 层。离线所有询问，对询问扫描线。从后向前扫，一个一个后缀往进插入，用线段树二分查询询问。复杂度 $\mathcal O((n + q) c \log n)$。

调了一上午。太太太难写了啊啊啊啊啊啊。

CF763D Timofey and a flat tree

子树同构直接树哈希，求每个根直接换个根就好了。

CF798E Mike and code of a permutation

trick：图的拓扑序可以对反图 dfs 求出，参考代码：

vector<int> order;
void dfs(int u){
    visit[u] = 1;
    for(int v : u 的反图出边) 
        if(!visit[v]) visit[v] = 1,dfs(v);
    order.push_back(u);
}

这样做的好处类似 dj 存边的最短路，每个点只会被遍历一次。对于 $\mathcal O(n^2)$ 条边的 dag，我们只需要快速找到一个 $u$ 的反图出边，在数据结构里把这个点删掉，复杂度就可以做到 $\mathcal O(nf(n))$，其中 $f(n)$ 是数据结构的复杂度。

本题很容易想到暴力 $\mathcal O(n^2)$ 的暴力拓扑做法，考虑应用上面的 trick。设 $b_i$ 是点 $i$ 被标记的时间（$b_{a_i} = i$），则所有 $b_i > x,i < a_x$ 的 $x$ 都比 $i$ 小。使用线段树维护反图即可。

CF1615H Reindeer Games

保序回归。

引理：如果代价函数 $f(x)$ 是凸的，如果全局最优解是 $b_1,b_2,\ldots,b_n$，那么如果值域是 $[l,r]$ 的最优解是 $b_1',b_2',\ldots,b_n'$ 满足 $b_i' = \max(l,\min(r,b_i))$。

证明：集训队论文 2018。

保序回归问题的通常做法是整体二分。根据上面的引理，我们限定值域为 $[mid,mid+1]$ 即可得知全局最优解是 $\le mid$ 还是 $> mid$，然后二分下去即可。判断每个位置取 $mid$ 还是 $mid + 1$ 可以用最大权闭合子图判断。复杂度未知。