省选计划（第三周）

Find_Yourself · 2023-01-24 10:42:45 · 个人记录

知识回顾：

• 巩固：概率DP，错排，组合数

• 深入研究：组合数，后缀数组，tarjan，2-SAT

• 简单了解/没学明白：

练题：

[ABC280F] Pay or Receive

概率 DP。

定义 f_i 为把怪物打成 i 滴血的期望攻击次数。

令 p=\frac{p}{100}。

则 f_i=f_{i+2} \cdot p+f_{i+1} \cdot (1-p)+1。

最终答案为 f_0。

复杂度 O(n)。

[ABC281G] Farthest City

一句话题意：问有多少种图满足 1 到 n 的最短路大于 1 到其他点的最短路。

容易想到将这些点分层。

定义 f_{i,j} 为考虑前 i 个点，其中有 j 个点在最外层上。

那么枚举上一层的点数，可以得到的转移方程为：

i=n 时需要特殊处理一下。

复杂度 O(n^3)。

P5239 回忆京都

先用杨辉三角形预处理出组合数，然后二维前缀和算就行了。

复杂度 O(n^2)

P4071 [SDOI2016]排列计数

组合数+错排。

这里的组合数比较大，需要用快速幂。

错排公式为 f_i=(i-1)\cdot (f_{i-1}+f_{i-2}) 其中 i > 2。

所以最终答案为 \dbinom{n}{m}\cdot f_{n-m}。

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

P8321 『JROI-4』沈阳大街 2

很有意思的 DP。

首先发现如果直接暴力 DP 的话，会出现重复的问题。

我们不妨将 a 和 b 连个数组合并成 c，并记录 c 中每个元素来自哪里。

然后从大到小排序。

定义 f_{i,j} 表示前 i 个元素配 j 对的值。转移方程显然：

其中 num 为 1 到 i - 1 中与 i 的来源不一样的元素的个数。

初始化：f_{i,0}=1。

答案：f_{n \cdot 2,n} \cdot inv，其中 inv=(!n)^{-1}。

复杂度 O(n^2)。

P5353 树上后缀排序

题如其名。

比较可以采用树上倍增。

现在的主要问题是可能会有相同的后缀。

于是基数排序时我们不仅要考虑前后两端的 rk 数组，还要加上上一次的 rkk 数组，即加上 id 限制后没有并列排名的数组。

剩下的就和普通的后缀排序差不多了。

复杂度 O(n \log n)。

Three strings

后缀数组拓展应用。

显然可以转化为求 LCP 的问题。

先将三个字符串拼接起来，中间用奇怪的符号隔开，跑一边后缀排序。

然后将每个位置按其 height 数组从大到小排序。

从大到小枚举 len，用并查集维护连通起来的块，对于每个块记录其分别有多少后缀在a、b、c三个字符串中。

每次合并时更新答案，即 cnt_1 \cdot cnt_2 \cdot cnt_3。

实现还是有些难度的，而且比较抽象。

复杂度 O(n \log n)。

P4782 【模板】2-SAT 问题

• 基本模型：

给定 n 个集合，每个集合有 2 个元素。再给定若干要求，形如 “a 与 b 只能选其一” 。请选出 n 个元素，使得从每个集合选且 仅选了 1 个元素，并且满足所有要求。

n 个集合相当于 n 个布尔变量。

每个要求相当于“变量 x = T/F 与 y = T/F 只能选其一”。

原问题相当于求一组布尔变量的可行值。

• 模型转化：

将每个布尔变量看成是两个结点 x 与 !x

x 表示变量取值为 T

!x 表示变量取值为 F

x 与 y 只能取其一，相当于两个条件关系，即两个有向边

x 成立，则 !y 必须成立，连边 x → !y

y 成立，则 !x 必须成立，连边 y → !x

原问题无解 等价于 存在 x 与 !x 属于同一个 scc

于是可以用 Tarjan 解决。

• 构造一组可行解：

对于任意的一条有向边 (u,v)，必有 scc_i \ge scc_j。

多以对于每一对 x 和 !x，我们可以贪心地取编号小的。

其实就是反向边的拓扑排序。

• 常见转化：

x 和 y 只能取其一：(x,!y),(y,!x)。

x 和 y 至少满足其一：(!x,y),(!y,x)。

若取 x 则必取 y：(x,y),(!y,!x)。

x 必为 T：(!x,x)。

P6378 [PA2010] Riddle

两种情况：

1. x 和 y 至少选一个

2. 如果选了 x，则一个集合内的所有元素均不能选。

可以发现，第一种情况很好处理，而第二种会使时间和空间复杂度上升至 O(n^2)，需要优化建边。

可以给每个点建立两个辅助点，分别维护前缀集合和后缀集合。

然后对于每个点只需要向它的前继前缀和后继后缀两个点连边即可。

这样点数是 4n，边数是 m+4n。

于是我们就得到了一个常数巨大的 O(n) 做法。

Break Up

Tarjan + 最小割

本来想直接用 Tarjan 解决，即对于每一条，记录其子树内有多少返祖边，结果发现这玩意不好维护，于是考虑网络流。

如果 s 和 t 不连通，则直接输出 -1，可以用并查集维护。

考虑只割 1 条边的情况。

跑一遍 Tarjan 找最小的割边使得去掉后 s 和 t 不连通。

这里可以从 s 开始跑，然后判断 t 是否在桥的子树内，dfs序判断就行。

再考虑只割 2 条边的情况。

将每一条边的边权加上极大值 inf，使得求最小割时尽可能地少选边。

同时，为了防止只选一条边，我们把所有桥的边权加上 4 \cdot inf。

最后只需要判断最大流是否大于 3 \cdot inf 即可。

如果大于，输出 -1。否则 dfs 只走没有满流的边，看 s 能到达哪些点，找到两个端点状态不同的两条边就行了。

需要注意的是，如果当前的流量已经大于 3 \cdot inf 了，就要立刻退出，否则会在第 153 个点 TLE。（被坑了好久......

复杂度 O(n^2m)。

Museums Tour

可以想到拆点。

对于每个点 i，拆成 d 个，定义第 j 天的 i 号节点的编号为 x_{i,j}

那么对于一条边 (u,v)，可以连接 (x_{u,j}, x_{v,j+1})，j 表示一周中的每一天。

这个图显然有环，不能直接用最长路解决，需要缩点。

对于每个强联通分量，记录其内部有多少个开门的不同的博物馆。

然后在 DAG 上 dfs 一遍就行了。

这样会不会算重呢？答案是不会。

假设有两个点 x_{u,j}，x_{u,j+k} 分别处在不同的强联通里。

如果没有直接或间接的连边，则不影响。

现在考虑会不会出现有连边的情况。

如果 (x_{u,j},x_{u,j+k})，则 (x_{u,j+k},x_{u,j+k+k})，以此类推可以得出 (x_{u,j+(d-1)\cdot k},x_{u,j+d \cdot k})，即 (x_{u,j+k},x_{u,j})，必然处在同一强联通内。

所以不存在处在不同强联通且有直接或间接连边的情况，也就不会有算重的情况。

复杂度 (nd)。

[ABC283D] Scope

被这题卡了好久，气得我直接弃赛了，最后发现是数据的锅（蚌。

直接从左到右用栈模拟，也可以写成递归的形式，然后记录字母是否出现过。

时间复杂度 O(26n)。

E，F计划第四周补。

模拟赛：

省选计划

都和数学相关。

40+66+20=128 rk24。

T302381 A

没想到垂直平分线，寄了。

设原点为 O，污染位置的坐标为 A_{1 \sim n}。不难发现，一个点 P 能到达当且仅当 \lvert OP\rvert \lt \min_ {i = 1} ^ n \{\lvert A_iP \rvert\}。对于每个污染位置分别考虑，OA_i 的垂直平分线会将平面划分成两个区域，其中一部分是不可达到的，计算出该直线与 y = m 的交点后可以求出可达到的范围。将所有污染位置对应的可达范围取交即为最终答案。注意特判 x = 0 的情况。

时间复杂度 O(n)，空间复杂度 O(n)。

代码较短，贴一下。

#include <bits/stdc++.h>
using namespace std;
typedef double db;
int n;
db c, d, m, l = -INT_MAX, r = INT_MAX;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        db c, d, w; scanf("%lf%lf", &c, &d);
        w = (2 * d * m - c * c - d * d) / (-2 * c); //求交点
        if (c == 0 && d >= 0 && d <= 2 * m) {
            printf("0.000\n");
            return 0;
        } if (c < 0) l = max(l, w);
        if (c > 0) r = min(r, w);
    }
    if (r == INT_MAX || l == -INT_MAX) cout << "Infinity" << endl;
    else printf("%.3lf\n", r - l);
    return 0;
}

T302382 B

设 f(x) 表示 b 进制下 x 的非零位个数，设 g_i = \min\{f(x) \mid x \equiv i \pmod n\}，则答案即为 g_0。

考虑 b 进制下在 x 后增加一位 j（0 \le j < b），可以列出以下不等式：

这是一个差分约束模型，可以转化为 01 最短路进行计算。

根据 01 最短路的性质，每个点只会被访问一次。因此在用某个节点更新别的节点时，只需要访问未求出最短路的节点。而每个点连的出边是一段连续的区间，因此问题可以转化为，找到区间中所有未被更新的点并更新。这可以简单地用并查集维护，将每个更新过的点指向它后一个点，那么从某个点开始跳并查集就可以找到它之后第一个未被更新过的位置。

时间复杂度 O(n)，空间复杂度 O(n)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e7 + 5;
ll n, b;
int fa[N], ans[N];
vector<int> q[2];
inline int ff(int x) {
    return fa[x] == x?x:fa[x] = ff(fa[x]);
}
inline void add(int id, int x, int w) {
    if (ans[x] != -1) return;
    ans[x] = w;
    fa[ff(x)] = fa[ff(x + 1)];
    q[id].push_back(x);
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> b;
    if (b >= n) {cout << 1 << endl; return 0;}
    for (int i = 0; i <= n; ++i) ans[i] = -1, fa[i] = i;
    for (int i = 1; i <= b; ++i) add(0, i, 1);
    while (!q[0].empty()) {
        for (int i = 0; i < q[0].size(); ++i) add(0, q[0][i] * b % n, ans[q[0][i]]);
        for (int i = 0; i < q[0].size(); ++i) {
            int l = (q[0][i] * b + 1) % n, r = (q[0][i] * b - 1 + b) % n, w = ans[q[0][i]] + 1;
            if (l <= r) {
                for (int j = ff(l); j <= r; j = ff(j + 1)) add(1, j, w);
            } else {
                for (int j = ff(l); j < n; j = ff(j + 1)) add(1, j, w);
                for (int j = ff(0); j <= r; j = ff(j + 1)) add(1, j, w);
            }
        }
        swap(q[0], q[1]);
        q[1].clear();
    }
    cout << ans[0] << endl;
    return 0;
}

T302383 C

巨巨巨巨好的一道题。

记：

考察 (n, m) \to (n + 1, m), (n, m + 1) 时 F, G, H 的变化情况。可以得到：