2023 国庆集训 Day 2B 笔记
更佳的阅读体验:2023 国庆集训 Day 2B 笔记,本文同步发表于 洛谷博客。
以下内容为个人总结,如有错误或您有不同见解,欢迎指出。
搜索
NOIP2009 提高组 - 靶形数独
- 可行性剪枝:每次最先搜索可能性最少的点。
- 最优化剪枝:剩下的数最优情况下也不超过全局最优解的剪枝。
Example 2
有
- 对
x 做质因数分解可以使用\texttt{Pollard-Rho} 算法,期望复杂度为O(n^{0.25}) 。 - 假设得到了
x = a_1^{p_1}a_2^{p_2}a_3^{p_3}\cdots a_k^{p_k} ,因此只有(p_1, p_2, p_3, \cdots, p_k) 的无序元组有意义。 - 这样本质不同的元组数量的一个粗略上限是考虑
2^{50} \sim 10^{15} ,而50 的拆分数只有2 \times 10^5 级别,事实上会少很多。 - 直接暴搜出所有可能的元组组合并排列组合一下计算答案即可。
SDOI2015 - 排序
- 首先操作的顺序是无关紧要的,所以我们只需要关心每个操作做没做。
- 我们从小到大 DFS,对于第
i 次操作我们将序列分成2^{n-i} 段,每段长度2^i 。 - 我们找到序列中不是连续递增的段,如果这样的段超过
2 个则不行。如果没有这样的段,就不需要执行这个操作。 - 如果有一个这样的段,判断将这个段的前半部分和后半部分交换后是否连续递增,如果是就交换然后继续 DFS。
- 如果有两个这样的段,判断四种交换情况然后 DFS。
二分
最大平均子段和
给定一个长度为
- 考虑二分答案
p ,然后让b_i = a_i - p ,只需要看b_i 构成的序列是否有大于0 的子段,就可以知道a_i 序列有没有平均值大于p 的子段。 - 看
b_i 构成的序列是否有大于0 的子段可以直接找b 的最大子段和。
LOJ 2776 - 蠕虫之忧
Subtask 1
- 二分、三分次数都不够,需要使用黄金分割比分。
- 因为黄金分割比位置在下一层二分处还是该位置。
Subtask 2
- 复制一维二分到二维,每次询问中线上最大值点,看看他左右两侧哪一侧增高就去哪边,不过注意可以每次二分较短的一维。同时如果之前查询到的全局最大值比当前线上最大值大,则向全局最大值位置继续二分。
Subtask 3
- 注意到
Q 很大,可以使用乱搞随机做法。 - 先用
\frac{q}{2} 次随机询问,问一个最大的点,然后用这个点爬山。 - 期望到山顶的路径长度其实很短。
Example 3
你在玩一个游戏,游戏中的一个关卡是这样的:
有一张
求在现实世界过关所需要的最小期望时间,输出实数。
- 二分答案
T ,在游戏中加入一个虚拟按钮,这个按钮的功能是立刻以T的时间通关。 - 用动态规划算出人物在每一个点的期望通关时间和为了达到这个通关时间的决策(继续走、重开还是按按钮),如果最后我们发现在
1 号点按按钮是最优的则实际通关最小期望时间\ge T ,否则< T 。
分治
Example 1
给定一个排列,随机做
-
- 考虑直接在
k \ne 0 的时候也硬上分治。 - 对于
(l, r) 节点,我们只统计k 轮过后期望(l, mid) 与(mid + 1, r) 之间的贡献。于是我们的第二个状态变成了f[k][0 / 1 / 2][0 / 1 / 2] ,表示第一个数在区间左 / 区间右 / 区间外,第二个在区间左 / 区间右 / 区间外,过k 轮他们产生贡献的概率。 - 这个 DP 可以用矩阵快速幂加速计算,同时只跟区间长度有关,注意到分治只会产生
O(\log n) 种不同长度的区间,所以矩阵快速幂不在瓶颈上。
Example 2:随机点分治
给定一棵树
- 本题考查了分治过程,考虑一下发现两个距离为
l 的点u ,v 发生贡献的情况是u 到v 的链上第一个作为分治点的点是u 或者v ,也就是说贡献只和l 有关\frac{2}{l} 。然后相当于统计一颗树每一种长度的链有多少个。 - 点分治 + FFT 即可。
点分治:ZJOI2016 - 旅行者
- 考虑将所有询问放在一起分治,从
n\times m 的网格图划一道中线,求出两侧的每一个点到中线的距离,然后如果一个询问起点终点跨过中线就在这一层解决,用两测每一个点到中线的距离求解即可。 - 剩余在同侧的询问递归下去即可。
CDQ 分治
-
一类给定一个序列,前面的项/修改对后面有影响但独立,求每一个前缀的影响和。
-
计算
[1, mid] 。 -
计算
[1,mid] 对[mid + 1, r] 的贡献。 -
计算
[mid+1,r] 。
-
贪心
Example 1
有
- 首先考虑
a_i \le b_i 的怪物,即会帮你加血的,显然要先打。 - 显然是先打
a_i 小的。 - 比较困难的是
a_i \ge b_i 的怪物,考虑简单的n = 2 的情况,有(a_1,b_1) ,(a_2,b_2) ,先打1 对血量x 的限制是x \ge \max(a_1, a_1+a_2-b_1) ,先打2 是x \ge \max(a_2,a_1+a_2-b_2) 。可以证明\max(a_2,a_1+a_2-b_2) 和\max(a_1,a_1+a_2-b_1) 比大小只和b_1 与b_2 大小有关。所以一定先打b_i 最大的。 - 对于
n 任意的情况我们可以考虑,对于任意方案,我们都可以交换其中两个i < j 且b_i<b_j 的怪物使得答案变不劣,所以对任意n 也成立。
IOI 2019 - 排列鞋子
- 因为存在同颜色的多个鞋子,所以我们首先先将鞋子对应关系找出,可以发现对于某种颜色的左脚鞋所在位置
l_1 < l_2 < \cdots < l_k 和与之对应的右脚鞋的位置r_1 < r_2 < \cdots < r_k 则配对方法一定是l_i 配r_i ,即对应匹配。 - 考虑一种可能的答案下界,发现对于一对鞋的位置
u 、v ,需要的次数至少为v-u-1 ,如果右脚在左边则还需要再来一次交换左右脚。 - 考虑两组鞋子的位置
u_1 < v_1 和u_2 < v_2 ,如果区间[u_1, v_1] 和区间[u_2, v_2] 有交则可能将交换次数减少一次,因为最多有一次交换使得两组鞋子都向目的地前进了一步。 - 所以若配对鞋子位罝为
(u_1, v_1) ,(u_2, v_2) ,\cdots ,(u_n,v_n) ,其中u_i < v_i ,则答案最小可能就是每一个鞋子自己的匹配长度相交的区间个数。事实上,这个下界就是答案。 - 相交个数可以将
u_i 从小到大排序后用树状数组求出所有u_j<u_i 且u_i<v_j<v_i 的个数(单点修改,前缀查询)。
正确性证明
- 如果要使得答案到达答案下界,则需要让每个相交的区间都产生贡献且每个鞋子都不向反方向走,一种可行的方法是考虑与第
1 个位置配对的鞋子的位置p ,先将p 一路向左跟1 位置匹配,然后这两个鞋子已经就与后面的无关了。 - 直接递归地将第
3 个位置视为第1 个位置继续做这样的操作,显然在这样的情况下每组配对的鞋子都不会绕远,且每个相交的区间都会产生贡献。
快速幂
- 实现幂运算。
- 求逆元。
- 矩阵快速幂实现、线性递推。
- Floyd 矩阵快速幂,图论里的路径相关问题。
NOI2020 - 美食家
-
使用 Floyd 矩阵,
A_{i, j} 表示i 到j 只经过1 条边的最短路,A_{i, j}^k 表示经过恰好k 条边的最短路。 -
-
先预处理出
A 的2 的倍数次幂,询问时二进制分解,访问答案后相乘。 -
时间复杂度
O(\log^T n^3 + k \log Fn^2) 。 -
首先考虑没有特殊事件的情况。由于每条边很短(
w_i \le 5 )我们可以把每条边拆点,这样就会得到一个n \times 5 个点的无权有向图,然后使用 Floyd 矩阵乘法快速幂计算f[t][i][j] 表示用t 天从i 走到j 的最大愉悦值。 -
如果有特殊事件,值假设第一次特殊事件在
t1 天,那么维护一个向量g ,g_i 表示花t_1 天从1 走到i 号点的最大愉悦。g=f^{t1} \times (0, \infin, \infin \cdots \infin)^T 。然后令g_{x_i} 加上y_i ,代表特殊事件,然后再继续考虑下一个特殊事件,每次用f 转移。 -
但是每次都算
f^t 太慢了,所以我们预处理出f,f^2,f^4,f^8\cdots 然后每次要算f^t \times g 的时候利用t 的二进制分解一个一个把对应的f^{2^q} 乘到g 上,这样避免了矩阵乘矩阵。
二维 RMQ
Example 1
给定一个
- 对于 RMQ 问题,考虑 ST 表,本题适用二维 ST 表。
- 和一维一样,令
f_{i,j,k,l} 表示子矩阵[i, i + 2^k) \times [j,j + 2^l) 的最小值。f_{i, j, k, l} = \min_{x \in [i, i + 2^k],y \in [j, j + 2^l]} a_{x, y} 。 - 注意空间复杂度
O(nm \log n \log m) ,如果卡空间可以选择一维线段树,另一维 RMQ。
LCA
Tarjan 算法
- 先把 LCA 的询问记录下来,在树上做 DFS,将已访问的点连到一个并查集内。
- 对于已访问的点,表明 LCA 一定在递归调用栈内,返回并查集的父亲;对于未访问的点,跳过,直到访问到该点。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct edge {
int to, nxt;
} e[N << 1];
int n, m, id, h[N], fa[N], ans[N];
vector<pair<int, int> > q[N];
bool vis[N];
void add(int u, int v) {
e[++id] = (edge){v, h[u]};
h[u] = id;
}
int getroot(int u) {
return u == fa[u] ? u : fa[u] = getroot(fa[u]);
}
void dfs(int u, int f) {
vis[u] = true;
for (int i = h[u]; i; i = e[i].nxt)
if (e[i].to != f) dfs(e[i].to);
for (int i = 0; i < q[u].size(); ++i) {
int to = q[u][i].first, id = q[u][i].second;
if (vis[to]) ans[id] = getroot(to);
} fa[u] = f;
}
int main() {
cin >> n;
for (int i = 1, u, v; i < n; ++i)
cin >> u >> v, add(u, v), add(v, u);
for (int i = 1; i <= n; ++i) fa[i] = i;
cin >> q;
for (int i = 1, u, v; i <= q; ++i) {
cin >> u >> v;
q[u].emplace_back(make_pair(v, i));
q[v].emplace_back(make_paur(u, i));
} dfs(1, 0);
for (int i = 1; i <= q; ++i) cout << ans[i];
return 0;
}
求 LCA 加强版
给定一棵
- 以
w 为根的树上u ,v 的 LCA 只有五种可能:u 、v 、w 、以1 为根u 、v 的 LCA,以1 为根u 、w 的 LCA,以1 为根v 、w 的 LCA。 - 为什么是五种?一定有两个是一样的。这些点和他们之间的关系又被称为
u ,v ,w 构成的“虚树”。 - 求出这五个点,特判即可。