模拟赛 1
Published:
过于 SB 的题会忽略部分分。会保留带有迷惑性质的部分分，即并没有算法可以只解决这一部分分。
1 套 (Hard)
P1846 游戏 (Hard)
给定两个正整数序列 $a,b$，长度分别为 $n,m$。进行若干次操作：你可以选择两个正整数 $k_1, k_2$，从 $a$ 末尾取出 $k_1$ 个数，计算他们的和 $s_1$；从 $b$ 末尾取出 $k_2$ 个数，计算它们的和 $s_2$。这样一次操作花费 $(s_1 - k_1) (s_2 - k_2)$。求同时清空两个序列的最小总花费。
$n,m \le 2000$。
- 对于 20pts，$n,m \le 20$。
- 对于 40pts，$n,m \le 200$。
令 $n,m$ 同阶。
首先是一个 trivial 的优化，我们把所有数都 $-1$，花费就可以变为 $s_1 \times s_2$。
设 $f_{i,j}$ 为 $a_{[1,i]}$ 与 $b_{[1,j]}$，求出 $a,b$ 的前缀和 $sa,sb$，直接 DP：
\[f_{i,j} = \min_{x<i, y<j}(f_{x,y} + (sa_i - sa_x) (sb_j - sb_y))\]时间复杂度 $O(n^4)$。洛谷神机发力了，得 45pts，照理来说只能过 20pts 才对吧。
TODO:
注意性质，优化为 $O(n^3)$。
- 斜率优化：https://www.luogu.com.cn/article/h35tfygm
- 直接注意到
优化为 $O(n^2)$。
P5769 [JSOI2016] 飞机调度 (Normal)
P3732 [HAOI2017] 供给侧改革 (Hard)
2 套
[未知来源] 小 W 的数字 (Hard)
TODO:
P12669 「TFXOI Round 2」最小价值最大树
抽象题。
BZOJ6074 Dash Speed (Normal)
离线、线段树分治、树的直径、可撤销并查集
3 套✅️ (Easy)
P3216 [HNOI2011] 数学作业✅️ (Easy)
口胡 AC！略。
P3601 签到题✅️ (Easy)
口胡 AC！略。
P2056 [ZJOI2007] 捉迷藏✅️ (Easy)
口胡 AC！
线段树分治、树的直径
4 套 (Normal)
P2173 [ZJOI2012] 网络 (Normal)
给定一张无向图，点有点权，边有颜色（颜色数 $C \le 10$）。
这个无向图永远满足以下条件：取出一种颜色的子图，
- 每个点度数 $\le 2$。
- 没有环。
$k$ 次操作，保证以上条件依然满足（若不满足你需要报错并不进行任何操作）：
- 修改点权。
- 修改边颜色。
- 求颜色 $c$ 的子图中，$u \leftrightsquigarrow v$ 任意路径上点权最大值。
$n \le 10^4$，$m \le 10^5$，$k \le 10^5$。
令 $n,m,k$ 同阶。
首先每种颜色的子图都是一堆链的并。
链也是树，我们可以用 LCT 维护，开 $C$ 棵 LCT 即可。
TODO: 题解区说时间复杂度 $O(C n \log n)$。
P2175 小Z的游戏分队✅️ (Normal)
把一张 $n$ 个点的图的点集分为不重不漏两部分，使得两部分各自形成完全图，且两个点集的大小之差最小。求出这个差或报告无解。
$n \le 2 \times 10^3$。
- 对于 30pts，$n \le 10$。
口胡 AC！
求补图，团转独立集。有解等价于补图是二分图。
对于每个连通块黑白二染色，接下来只要考虑每个连通块的黑点放左部还是右部（最终要左部右部差值最小）。设该连通块黑点 $a$ 个白点 $b$ 个，则其实我们关心的只是 $a-b$。
也就是说，我们对于每个连通块，我们希望判断在最终的总和中应该加 $a-b$ 还是 $b-a$，使得总和最接近 $0$。注意到这可以看成背包问题，可以 $O(n^2)$ 甚至 $O(\frac {n^2} w)$ 解决。
时间复杂度 $O(n^2)$。
P2350 [HAOI2012] 外星人✅️ (Normal)
$T$ 组数据。给定一个数 $n$ 的质因数分解 $\prod\limits_{i=1}^m p_i^{q_i}$，求对它求至少几次 $\varphi$ 会变成 $1$。
$T \le 50$，$p_i \le 10^5$，$q_i \le 10^9$，$m \le 2 \times 10^3$。
- 对于 30pts，$n \le 10^6$。
- 对于 60pts，答案 $\le 100$。
口胡 AC！
首先发现前 60pts 是白送的，考虑正解。
对于 $p \ne 2$：
\[\varphi(p^q) = (p-1) p^{q-1}\]而 $p-1$ 是 $2$ 的倍数，所以对于 $p^q$ 每次取 $\varphi$ 都能产至少一个 $2$。
每次取 $\varphi$ 只能消掉一个 $2$（如果开局没 $2$ 则开局这次 $\varphi$ 消不掉，要特判），因此我们考虑每个 $p^q$ 能产几个 $2$ 即可。
设 $f(k)$ 表示 $k$ 能产 $f(k)$ 个 $2$，则可以线性筛：
- $k$ 是质数，$f(k) = f(k-1)$。特别地，$f(2) = 1$。
- $k = i \times j$（其中 $j$ 是 $k$ 的最小质因子），$f(k) = f(i) + f(j)$。
不难发现 $f(p^q) = q f(p)$，做完了。
时间复杂度 $O(V + T m)$，$V$ 是 $p_i$ 的值域。
5 套
P2664 树上游戏🟡
树上差分
P2505 [HAOI2012] 道路✅️ (Normal)
给定一张正权有向图。对于每条边，求出有多少条最短路经过它，对 $10^9 + 7$ 取模。
$n \le 1500$，$m \le 5000$。
- 对于 30pts，$n \le 15, m \le 30$。
- 对于 60pts，$n \le 300, m \le 1000$。
是最短路 DAG 的题，但是之前没学过最短路 DAG。
100pts 解析扔到《图论 1》去当模板题了。
感觉这个题只有 0 和 100 的区别啊，但凡能写出暴力基本上就能写出正解。
P2839 [国家集训队] middle
TODO:
6 套
P2261 [CQOI2007] 余数求和✅️ (Easy)
略。
P4284 [SHOI2014] 概率充电器 (Hard)
给定一棵无根树。边 $(u,v)$ 有 $p_{(u,v)}$ 概率亮起。点 $u$ 有 $q_u$ 概率直接亮起；若点 $u$ 通过亮起的边可以到达亮起的点，则点 $u$ 会跟着亮起。
求亮起的点数期望。答案保留 $6$ 位小数。
$n \le 5 \times 10^5$。
- 对于 30pts，$n \le 5 \times 10^3$。
设随机变量 $x_u \in {0,1}$ 表示 $u$ 是否点亮。但是只设这个无法得到 DP 式子，因为点亮是有先后关系的。
额外设一个 $y_{u,v} \in {0,1}$ 表示若 $(u,v)$ 被删除时 $u$ 是否被点亮，即 $u$ 被点亮是否不依赖于 $v$ 被点亮。
DP 式子：
（记号不严谨。）
\[y_{u,v^*} = \begin{cases} 1 & q_u \\ \bigcup\limits_{v \ne v^*} p_{(u,v)} x_v & \text{otherwise} \\ \end{cases}\] \[\mathbb E[y_{u,v^*}] = q_u + (1 - q_u) \left( 1 - \prod\limits_{v \ne v^*} (1 - p_{(u,v)} \mathbb E[x_v]) \right)\]TODO:
P11160 【MX-X6-T6】機械生命体🟡(Hard)
7 套 (Easy)
P4107 [HEOI2015] 兔子与樱花 (Normal)
P1822 魔法指纹 (Easy)
P2442 分数统计 (Easy)
8 套 (Normal)
P4151 [WC2011] 最大XOR和路径✅️
略。
P3279 [SCOI2013] 密码✅️ (Normal)
已知一个字符串的 Manacher $r$ 数组，求字典序最小方案。
$n \le 10^5$。
口胡 AC！
翻转原串，区间回文化为区间相等。倍增并查集即可。时间复杂度 $O(n \log n \alpha(n))$。
另一种方法则是直接模拟 Manacher，这样时间复杂度为 $O(n \alpha(n))$。
P3653 小清新数学题 (Normal)
求
\[\sum\limits_{i=l}^r \mu(i)\]$1 \le l \le r \le 10^{18}$，$r - l \le 10^5$。
口胡 AC！
首先 $r - l$ 很小，肯定是区间筛。但是 $\sqrt r$ 太大，正常区间筛过不了。
考虑设一个阈值 $B$，筛出 $[1,B]$ 中的质数后区间筛。不妨令 $B = 10^6$ 或 $10^7$。
设一个数筛去所有 $B$ 以内因子后为 $x$，则现在我们要求 $\mu(x)$。注意到，一个数 $>B$ 的质因子数量最多只有 $2$。
首先 Miller-Rabin 可以判断 $x$ 是否是质数，如果不是，说明 $x$ 有两个质因子，注意判断这两个质因子是否相同。
时间复杂度 $O(B + (r-l) (\log \log B + MR))$，其中 $MR$ 是一次 Miller-Rabin 的复杂度。
9 套
P2425 小红帽的回文数 (Normal)
P3676 小清新数据结构题
树剖
\[ans_u = ans_1 + k a_0^2 - 2 a_0 \sum\limits_{i=1}^k a_i\]LCT 也可
P3794 签到题IV✅️ (Normal)
给定一个长为 $n$ 的正整数序列 $a$，和一个参数 $k$。求有几个区间使得区间 $\gcd$ 异或上区间 $\text{bitor}$ 等于 $k$。
$n \le 5 \times 10^5$，值域 $5 \times 10^5$。
- 对于 30pts，$n \le 500$。
- 对于 60pts，$n \le 10^5$。
30pts $O(n^2 \log V)$ 暴力解决（事实上是 $O(n^2)$，后文会说）。
这种对于全部区间 $[l,r]$ 统计的题目，考虑固定端点或分治。分治想了半天没法做，那就是固定端点。
我们固定 $r$ 找 $l$。首先我们发现一个关键的性质：$\gcd$ 和 $\text{bitor}$ 在 $l$ 从 $r$ 开始向左扩张时都只会变化 $O(\log V)$ 次。
通过二分找出这些变化点。进行 $O(\log V)$ 次二分，每次二分 $O(\log n)$，ST 表求 $\gcd$ 需要 $O(\log V)$，时间复杂度 $O(n \log n \log^2 V)$，可以获得 60pts。但是 $\gcd$ 的 $O(\log V)$ 常数很小，说不定能过。
优化。我们发现 $r$ 在右移时其实不需要再次二分计算那 $O(\log V)$ 个变化点，我们可以直接继承 $r-1$ 的——新的变化点除 $r$ 以外一定是 $r-1$ 的变化点的子集。
我们省去了 $O(\log n)$ 次二分，与此同时不再需要 ST 表，时间复杂度 $O(n \log^2 V)$。
事实上这个做法的时间复杂度是 $O(n \log V)$ 的。有结论：辗转相除法计算 $n$ 个数的 $n$ 个前缀 $\gcd$，时间复杂度是 $O(n + \log V)$。
我们对 $O(\log V)$ 个数计算 $\gcd$，时间复杂度显然是 $O(\log V)$。__gcd 函数内部实现是辗转相除法（注意 C++17 std::gcd 不是，它使用的是 Binary GCD，在此题无法均摊），可以直接使用。
ll ans = 0;
vector<int> vec;
vec.push_back(0);
rep(r, 1, n) {
vec.push_back(r);
int cur_gcd = 0, cur_bitor = 0;
vector<int> tmp;
per(i, vec.size()-1, 1) {
int l = vec[i];
int last_gcd = cur_gcd, last_bitor = cur_bitor;
cur_gcd = __gcd(cur_gcd, a[l]);
cur_bitor = cur_bitor | a[l];
if (last_gcd != cur_gcd || last_bitor != cur_bitor)
tmp.push_back(l);
if ((cur_gcd ^ cur_bitor) == k)
ans += l - vec[i-1];
}
tmp.push_back(0);
reverse(tmp.begin(), tmp.end());
vec = tmp;
}
cout << ans << '\n';