p_b_p_b' blog

Blog

Public Round #5 题解

2022-06-12 13:38:33 By p_b_p_b
  • 搬题人:
    • A:he_____he
    • B:p_b_p_b
    • C:hehezhou
  • 组题人:hehezhou
  • 题解:hehezhou, p_b_p_b

双向奔赴

题目来源:

  • XXI Open Cup named after E.V. Pankratiev. Grand Prix of Korea, Problem C

QOJ 链接:https://qoj.ac/contest/776/problem/3301

一个强连通分量一定可以由如下过程产生:

  1. 初始有一个集合 $S$,包含其中的一个点。
  2. 每次选择一条链 $u\rightarrow v_1 \rightarrow v_2\rightarrow\cdots\rightarrow v_k\rightarrow w$,其中 $u,w\in S$ ,将 $v_1,v_2,\cdots,v_k$ 加入到 $S$ 中。

对于 $(i,j)$ 的无向边,我们可以默认代价较小的那个方向的有向边一定出现,然后将代价同时减去这个较小值。我们可以状压 dp 这个过程,用 $d_S$ 表示集合变为 $S$ 的最小代价。定义 $f_{S',v,w}$ 表示目前考虑了一条 $u$ 到 $w$ 的链,同时这条链已经走到了 $v$ 点,还剩余 $v$ 到 $w$ 的部分没有完成, 表示 $S'$ 并上这条链中 $u$ 到 $v$ 的部分,此时的最小代价。可以直接枚举链上 $v$ 的下一条边转移。需要注意不能同时包含连接两个点的两个方向的有向边。时间复杂度 $O(2^nn^3)$。

循环移位

题目来源:

  • Petrozavodsk Winter 2022. Day 7. Gennady Korotkevich Contest 6, Problem I
  • XXII Open Cup named after E.V. Pankratiev, Grand Prix of Gomel, Problem I

QOJ 链接:https://qoj.ac/contest/825/problem/2624

经过打表,发现满足条件或不满足条件的排列都看不出任何性质。

那就只能暴力一点,用 $O(2^{n-1})$ 的时间枚举每个 $i$ 是否有 a[i]<a[1] ,以此获得一个大小关系树。然后再计算有多少个满足条件的排列也同时满足这个大小关系树。

注意到如果当前这个 a[i] 在之前已经被考虑过,那么必然有 a[i]>a[1] 。那么感性理解一下,随着 $i$ 增大,a[i] 从未被考虑过的概率越来越小,从而可能的大小关系树的数量会远小于 $2^n$ 。

写一个带剪枝的 dfs ,发现 $n=42$ 时只有 $\approx 10^9$ 种可能,因此直接暴力打表即可。

和平共处

题目来源:

  • RuCode 2020 Division A+B Championship Round, Problem I
  • XX Open Cup named after E.V. Pankratiev, Grand Prix of Moscow, Problem I

QOJ 链接:https://qoj.ac/contest/923/problem/4219

题解的做法几乎没有用到平面黑白点的任何性质。

利用一些二分图匹配的性质,不难发现题意等价于求这张二分图的字典序最小的最大匹配,字典序的定义为匹配白点集合的字典序,下面简称字典序最小最大匹配为最优匹配。

我们给出结论:如果能在 $T(n+m)$ 的时间复杂度内计算出左右部分别为 $n,m$ 个点的二分图的最小割以及方案,那么可以在 $T(n+m)\log {n}$ 的时间内计算出左部的最优匹配。这里最小割的定义为:设左部和右部分别为 $L,R$,一个割由左集和右集 $X,Y$ 组成,满足 $X\bigcap Y=\emptyset,X\bigcup Y=L\bigcup R$ 并且 $X\bigcap L$ 和 $Y\bigcap R$ 之间不存在边。割的大小定义为 $X\bigcap R+Y\bigcap L$,令 $X_l=X\bigcap L,X_r=X\bigcap R,(Y_l,Y_r)$ 同理。

具体的做法如下:考虑过程 $F(S_1,S_2,S_3)$ 表示你需要求出左部为 $S_1\bigcup S_2$,右部为 $S_3$ 的最优匹配,并且 $S_2$ 中所有元素小于 $S_1$ 中元素且一定在最优匹配中,答案就是 $F(L,\emptyset,R)$。

将 $S_1$ 按照元素大小划分成大小相同的两部分,元素较小和较大部分分别设为 $X,Y$。求出 $(S_2\bigcup X,S_3)$ 的一个最小割,左集和右集分别设为 $(A_l,A_r),(B_l,B_r)$。

引理 $1$:$(B_l\bigcup Y,B_r)$ 的最优匹配一定包含 $B_l$。

首先 $(B_l,B_r)$ 的最大匹配大小为 $|B_l|$,因此包含 $B_l$,注意到 $Y$ 中所有元素大于 $B_l$ 中元素,由匈牙利算法可得,$(B_l\bigcup Y,B_r)$ 的最优匹配包含 $B_l$。$\square$

引理 $2$:$(X\bigcup S_2,S_3)$ 的最优匹配由 $(A_l,A_r)$ 和 $(B_l,B_r)$ 的最优匹配组成。

两者之间的边只存在于 $A_r$ 和 $B_l$ 之间,这些边不可能成为匹配边,否则这个匹配大小达不到 $|A_r|+|B_l|$。

引理 $3$:$(S_1\bigcup S_2,S_3)$ 的最优匹配由 $(A_l,A_r)$ 和 $(B_l\bigcup Y,B_r)$ 的最优匹配组成。

考虑在 $(X\bigcup S_2,S_3)$ 的最优匹配的基础上,将 $Y$ 中元素逐个加入,模拟找增广路的过程,由于 $Y$ 中元素较大,这样得到的结果就是最优匹配。

每次找到的增广路不可能包含 $A$,因为 $A_l$ 只和 $A_r$ 相连,$A_r$ 所有点均已匹配且匹配点均在 $A_l$,一旦增广路走到 $A$ 就无法出来且找不到未匹配点。因此每个点加入后,$A$ 内部的匹配不会改变。$\square$

对 $(A_l,A_r)$ 的求解直接调用 $F(A_l\bigcap S_1, A_l\bigcap S_2, A_r)$。对 $(B_l\bigcup Y,B_r)$ 的求解调用 $F(Y,B_l,B_r)$。注意到每次递归,每个点恰好会递归至一侧,并且 $S_1$ 的大小减半。递归树仅有 $\log n$ 层,复杂度 $T(n+m)\log n$。

考虑求出一组最小割:这可以贪心解决,具体的,先求匹配,将所有点按照 $x$ 轴排序并枚举,加入黑点时将 $y$ 坐标加入集合,加入白点时找集合中最大的不超过当前白点 $y$ 坐标的黑点,匹配两个点并将黑点从集合中删去,如果找不到则认为匹配不上。然后从所有未匹配的白点开始 bfs,将所有走到的黑点以及他们对应匹配的白点不断加入队列,这可以通过线段树优化建图完成,因此 $T(n)=O(n\log n)$。

总复杂度 $O(n\log^2 n)$。

Comments

No comments yet

Comments are turned off.