那啥

· · 算法·理论

2605 - Soccer Match

题目来源

题目网址：https://qoj.ac/contest/824/problem/2605

本题是 ICPC Camp 2022 (Powered by Huawei) Day 1 的 A 题，该比赛随后被使用于 42nd Petrozavodsk Programming Camp Day 6。

题目大意

给定一张 N 个点 M 条边的无向图，以及一个参数 K，保证 M\geq 2KN。请找出一种给无向图的每个顶点染上红、蓝、白三种颜色的方案，使得：

可以证明一定有解。

数据范围

多组测试，保证 1\leq N,M,K\leq 5\times 10^4，M\geq 2KN 且所有测试数据的 M 总和不超过 5\times 10^4。

解题过程

我们首先考虑给所有顶点染上红色或蓝色的一种，使得至少有 \frac{1}{2}M 条边的两端点异色。如果异色的边数不到总边数的一半，则容易知道至少存在一个顶点，其异色邻居个数小于同色邻居的个数。此时我们可以翻转该顶点的颜色，这样异色的边数一定会至少增加 1，因而该调整法至多执行 \frac{1}{2}M 轮便会终止。

假设现在至少有 \frac{1}{2}M 条边为异色边，由 M\geq 2KN 可知此时至少有 KN 条异色边。若有一个顶点的异色邻居个数不超过 K，则我们将该顶点修改为白色，此时有色顶点个数减少 1，而连接一个红色顶点一个蓝色顶点的异色边个数至多减少 K。可以得出，在调整的过程中，异色边的个数一定超过有色顶点个数的 K 倍。

若调整法过程中，仅剩一个有色顶点，则此时异色边数量必然为 0，与上述性质矛盾，故而调整法得到的解一定有 >1 个有色顶点，即得到的解一定是一个满足题意的构造。

由于每轮翻转颜色操作会影响 O(N) 个邻居，而该操作会进行至多 O(M) 次，可以说明上述做法的时间复杂度为 O(NM)。在 M\leq 5\times 10^4 的数据范围下，该时间复杂度不一定可以接受。

我们考虑在所有染色方案中，随机任意一种染色方案。可以算出，此时异色边数量的均值为 \mu=\frac{1}{2}M，而方差为 \sigma^2=\frac{1}{4}M。若调整法执行了 k 轮，则初始边的数量一定不超过 \frac{1}{2}M-k 条。根据切比雪夫不等式可知，该事件发生的概率满足：

P(x\leq \mu-k)\leq \frac{\sigma^2}{k^2}

故可以说明，对于 k=c\sqrt M，该事件仅有不超过 \frac{1}{4c^2} 的概率发生，可以认为，有足够高的概率 k 为 O(\sqrt M) 级别，即时间复杂度为 O(N \sqrt M)。

参考资料

  1. Soccer Match - Problem - QOJ.ac
  2. 随机变量的数字特征 - OI Wiki
  3. 概率不等式 - OI Wiki

2610 - Build a City

题目来源

题目网址：https://qoj.ac/contest/824/problem/2610

本题是 ICPC Camp 2022 (Powered by Huawei) Day 1 的 F 题，该比赛随后被使用于 42nd Petrozavodsk Programming Camp Day 6。

题目大意

二维平面上有 n+1 个点，编号为 0 到 n，第 i 个点的坐标为 (x_i,y_i)，保证第 0 个点的坐标为 (0,0)。你有一个矩形，初始时其为仅包含点 (0,0) 的退化矩形。每次操作，你可以从平面上的 n+1 个点中选择任意一个未被矩形包含的点，并将矩形扩大直到恰好包含该点。

定义一次操作的代价为，新得到的矩形的周长中，不与原矩形重合的部分的长度。给定所有点，和一个代价上限 m，求出是否存在一种操作方案，使得最终矩形包含所有 n+1 个点，且每一次操作的代价均不超过 m。

数据范围

多组测试，所有测试数据的 n 总和不超过 5\times 10^5。代价上限 m 满足 1\leq m\leq 4\times 10^9，点的坐标 (x_i,y_i) 满足 1\leq x_i,y_i\leq 10^9。

解题过程

由于坐标范围较大，首先将坐标离散化为 O(n) 级别。

对于此类数据范围较大的题目，我们常常考虑动态规划。令 f(x,y) 表示是否存在某种操作方案可以得到左下角为 (0,0)，右上角为 (x,y) 的矩形，若存在则 f(x,y)=1，否则 f(x,y)=0。转移时枚举下一步操作选择的点 (x_i,y_i)，检查代价是否超过上限 m，并从 f(x,y) 转移到 f(\max(x,x_i),\max(y,y_i))。该朴素动态规划的时间复杂度为 O(n^3)。

考虑对转移部分进行优化。我们可以将转移分为三类：

其中第二和第三类转移是对称的。

对于第一类转移，从 f(x,y) 转移到 f(x_i,y_i) 的操作代价为 2x_i+2y_i-x-y，我们可以定义辅助数组 g(x,y) 表示，所有满足 x'<x, y'<y,f(x',y') 的点 (x',y') 中，x'+y' 的最大值。此时 f(x_i,y_i) 可以被转移到当且仅当 2x_i+2y_i-g(x_i,y_i)\leq m。

对于第二类转移，从 f(x,y) 转移到 f(x_i,y) 的操作代价为 2x_i+y-2x。令 h_1(x,y) 表示最大的 x'<x 使得 f(x',y)=1，则此时 f(x,y) 可以被转移到当且仅当存在输入的点 (x_i,y_i) 满足 x_i=x,y_i\leq y，且 2x+y-2h_1(x,y)\leq m。第三类转移与第二类转移对称。

转移中涉及到的辅助数组均可以在转移过程中以 O(n^2) 的时间复杂度维护，此时得到的做法时间复杂度为 O(n^2)。

由于 n 的上限为 5\times 10^5，而动态规划的状态数量已经达到了 O(n^2) 级别，这启发我们考虑在对 x 轴扫描线的过程中，使用数据结构对于每个 y 维护 f(x,y) 的值。由于操作代价的单调性，我们只需要实时维护 p_y 表示当前最大的 x' 满足 f(x',y)=1。

在从 x-1 移到 x 的过程中，我们首先进行第二类转移。设 y_{\min} 为所有横坐标为 x 的输入点中纵坐标的最小值。对于每个 y\geq y_{\min}，我们尝试用第二类转移更新 DP 值。但是目前维护的信息不适合线段树，且无法在低于 O(n^2) 的时间内找出所有需要更新的位置，我们分析性质并且给出引理：

引理：若某个 y\geq y_{\min} 在某次无法被第二类转移更新 DP 值，则直到该纵坐标在之后的某个时刻被第一或三类转移更新 DP 值之前，忽略该纵坐标不影响任何一类转移。

证明：由于第三类转移是在某个横坐标内部转移，则显然在该纵坐标 DP 值被重新更新为 1 之前不能参与任何第三类转移。对于第二类转移，由于其是在该纵坐标内部转移，且操作代价具有单调性，故若当前不能转移，则在 p_y 被更新之前不能参与任何第二类转移。对于第一类转移，设某个需要被转移到的输入点为 (x',y')，由于当前不能进行转移，代价 y+2x-2p_y>m，而该第一类转移的代价为 2x'+2y'-p_y-y，由 x'\geq x,y'\geq y 可知该代价也大于 m，故这样的转移不成立。

由引理可知，如果线段树中只维护未被忽略的位置，则所有位置的 p_y 关于 y 单调不降。于是我们可以维护所有 p_y 的单调栈，每次将 \geq y_{\min} 的一段后缀的 p_y 更新为 x，同时每弹出一段相同 p_y 的区间，它们进行第二类转移的代价是关于 y 单调增的一次函数，我们可以找出其中不能转移的部分，将那段区间的信息在线段树上清空，剩余部分的信息保留。这部分的时间复杂度为 O(n) 次线段树操作。

然后我们进行第一类转移。枚举所有横坐标为 x 的输入点，在线段树上区间查询 y+p_y 的最大值，判断可不可以转移即可。注意到输入点的 y 值一定不会小于 y_{\min}，所以第一类转移不影响单调栈中的信息。

然后我们进行第三类转移。对于每个 x 坐标，我们只需要考虑三小类转移：

  1. 以某个第一类转移中更新到的输入点为起点的转移；
  2. 以某个 x_{\min}=x 的纵坐标为起点的转移；
  3. 在单调栈被更新之前，跨过原单调栈的两段的转移。

不属于这三小类中任意一种的位置满足：在那一段对应的横坐标 p_y 时就有同样的 DP 值，该横坐标同样可以进行第三类转移，即 x_{\min}\leq p_y。而由于代价的单调性，若在当前 x 可以转移，则早应在横坐标 p_y 处已经进行了转移，故这样的转移是可以忽略的。

这三小类转移的数量总数是 O(n) 级别的。每次转移的时候，在线段树上维护的所有 x_{\min}\leq x 的位置中，二分出第一个距离过远而无法转移的，并将 DP 值区间覆盖为 1 即可。

所有上述的转移，操作，与需要维护的信息均可以用线段树在 O(\log n) 的时间内完成，具体的实现细节略过不提。

时间复杂度 O(n\log n)。

参考资料

  1. Build a City - Problem - QOJ.ac
  2. 线段树基础 - OI Wiki
  3. 单调栈 - OI Wiki

12302 - Unfair Card Deck

题目来源

题目网址：https://qoj.ac/contest/1171/problem/12302

本题是 Yandex Cup 2019 的 B 题，该比赛随后被使用于 36th Petrozavodsk Programming Camp Day 4。

题目大意

牌堆中有 n 种花色的牌，第 i 种花色有 a_i 张，第 i 种花色的每张牌权值均为 X_i，X_i 未知。进行 m 轮游戏，每轮游戏依次将牌堆中剩余的牌按带权概率抽出，直到牌堆被抽空。给出每轮游戏依次被抽出的牌的花色顺序，还原出一组 X_i。

设你输出的权值为 W_i，则你的答案正确当且仅当对于任意 X_i\leq X_j，都有：

\left|\frac{X_i}{X_i+X_j}-\frac{W_i}{W_i+W_j}\right|<0.02

数据范围

保证 m=10^5，\sum a_i=30，即牌堆中总共有 30 张牌。

解题过程

通过每张牌作为每轮游戏第一张出现的频率，可以求出 X_i 的一组近似值，但是由于 X_i 可能非常小，两个几乎没有出现的花色之间的 X_i 之比可能误差较大。

为了让被抽出概率极小的两种花色之间也能比较，我们考虑，对于花色 i 和 j，计算出每轮游戏第一次抽出一张花色为 i 或 j 的牌时，这张牌花色是 i 的频率。有了这个频率，我们可以对所有 \frac{a_iX_i}{a_jX_j} 给出近似。

这个近似在 X_i 与 X_j 比例悬殊的时候仍然不够精确。于是我们希望首先将所有花色对 a_iX_i 排序。利用前文提到的，作为每轮游戏第一张出现的频率，可以找出所有花色中 a_iX_i 最大的一种。进一步地，计算每轮游戏第一张非前述花色牌的花色频率，可以求出 a_iX_i 第二大的一种花色。如此递归下去便可以将花色排序。

时间复杂度 O(mn^2) 或 O(mn)。

参考资料

  1. Unfair Card Deck - Problem - QOJ.ac
  2. 条件概率与独立性 - OI Wiki
  3. 随机变量 - OI Wiki

12306 - Planar Max Cut

题目来源

题目网址：https://qoj.ac/contest/1171/problem/12306

本题是 Yandex Cup 2019 的 F 题，该比赛随后被使用于 36th Petrozavodsk Programming Camp Day 4。

题目大意

给定一张无向带权平面图每个点的坐标以及每条边的边权，求这张图最大割的大小。一个割定义为将图的点集分成不交的两个部分的方案，割的大小为所有两端点不在同一部分中的边的边权和。

数据范围

点数 n 满足 1\leq n\leq 200，边数 m 满足 1\leq m\leq 1000。边权为 [0,10^5] 中的整数，坐标的绝对值不超过 10^4。

解题过程

对于图的某个割，若某条边的两个端点在同一部分中，则将这条边删去，将两个端点合并为一个点。重复执行直到所有边的两个端点都不在同一部分，由定义可知得到的新图是一张二分图。

求出原平面图的每个面，其在新图中，要么对应一个面，要么面上所有点被缩在一起。新图是二分图意味着，原平面图的每个面，恰有偶数条边没有被删去，即恰有偶数条边满足两端点不在同一部分。

另一方面，对于任意一个原图的边集，满足每个面恰有偶数条边被包含在边集中，都存在一个割满足该边集恰好是所有两端点不在同一部分的边的集合。这是因为，当且仅当一张平面图的所有面都包含偶数条边时，该平面图是二分图，于是我们进行上述缩点后二分图染色，即可得到一种合法的方案。

对于平面图，其中的每条边被所有面恰好包含两次，我们建出原图的对偶图，则对偶图的每个顶点对应了原图的一个面，对偶图的每条边对应了原图的一条边，连接了原图中包含它的两个面。特别地，若在原图中某条边被同一个面包含了两次，则它对应对偶图中的一个自环。

经过上面的转化，问题变为：给定一张无向带权图，求出它的某个生成子图，使得每个点的度数均为偶数，且生成子图的边权和尽量大。考虑某个合法生成子图的补图，我们令奇度数点的集合为 S，给出如下引理：

引理：一个合法生成子图的补图一定可以拆分为 \frac{1}{2}|S| 条边不重复的路径和若干个环，且 S 中每个点恰好作为某条路径的端点出现一次。

证明：关于 |S| 归纳。S 为空时显然补图的每个点度数为偶数，即补图由若干个环组成。S 不为空时，由每个连通块恰有偶数个奇度数点知存在两个点 u,v\in S 联通。找到一条 u 到 v 的路径从补图中删去，结合归纳条件可知引理成立。

我们求出图上所有奇度数点两两间最短路。并求出以最短路为权值的完全图的最小权完美匹配，由引理知一个合法生成子图的补图权值和一定大于这个完美匹配的边权和，与此同时我们选择所有在偶数（包括 0）条路径中出现的边可以得到一个合法的生成子图，所以这个完美匹配的边权和即为所求答案，使用前文所述方法可以构造一个合法方案。这个做法的时间复杂度是 O(n^3)。

参考资料

  1. Planar Max Cut - Problem - QOJ.ac
  2. 二分图 - OI Wiki
  3. 平面图 - OI Wiki
  4. 一般图最大权匹配 - OI Wiki