2015 北京省队集训
Day 1
训练题
树的难题
给定 n 个点的边带权三色树（黑白灰），定义“均衡的”三色树为“不存在黑点”或“只存在不超过 1 个白点”。
删掉一些边得到“均衡的”森林，最小化删掉的边权和。
数据范围 \(n\le 3*10^5\)
key：dp
\(f(u,op)\) 代表 u 子树合法，且 u 所在连通块满足条件 op，最小删掉的边权和，转移平凡。
秘密任务
给定 n 个点的边带权无向图，定义“逃跑路线”为从 1 到 n 的任意一条最短路。在边 (u,v) 上设置检查点，代价为 \(\min(a_u,a_v)\)，当“逃跑路线”经过 (u,v) 时拦截成功。特别的，点 n 不能设置检查点。
可以设置任意多个检查点，最小化总代价，使选择任意“逃跑路线”，都可以拦截成功，并判断最优方案是否唯一。
数据范围 \(n\le 400, m\le 4000\)
key: 最短路图 + 最小割唯一性
- 求出 1 到 n 的最短路
- 保留在最短路上的边 (\(dis(1,u)+w(u,v)+dis(v,n)=dis(1,n)\))
- 求最小割
- 判断最小割是否唯一
当且仅当所有必定出现的边权和等于最小割。
引理：有向边(u, v)必定出现在任意最小割中，当且仅当在最终的残留网络中点 1 可达点 u，点 v 可达点 n。
数对统计
给定序列 \(\{A_n\}\)，\(m\) 次询问 \((v,L,R)\)，求满足 \([l,r] \subseteq [1,n],r-l+1\in [L,R],\forall j\in [l,r],A_j\ge v\) 的数对 \((l,r)\) 数量。
数据范围 \(n,m\le 3*10^5\)，\(0\le A_i,v\le 1000\)
key: 离线排序 + 合并答案区间
对于单个 v，删去所有小于 v 的数后，序列分成若干个区间，合法答案一定包含在这些区间之中，计算平凡。
离线询问，按 v 从大到小排序，每次修改 v 相当于合并区间。
Day 2
训练题
冻结
给定平面上 n 个点，m 次询问求距离小于等于 \(R_i\) 的最大连通块。
数据范围 \(T\le 100,n\le 100 ,m\le 1000\)
key: 离线 + 并查集
把距离排序一下，瞎搞就行。
灵魂宝石
初始有 m 颗宝石，每天减少一颗宝石，没有宝石就会死。
现在有 n 个 boss，描述为 \((t_i,p_i,w_i)\)。
在第 \(t_i\) 天，可以打 boss，也可以不打。
若挑战：
- 先 失去一颗宝石
- \(p_i\) 的概率成功，获得 \(w_i\) 颗宝石（若当前宝石数大于 m，自动变成 m）
- \(1-p_i\) 的概率失败，立即死亡
钦定一个挑战选择，最大化存活天数的期望，输出这个期望值。
数据范围 \(n\le 300,m\le 100\)
key: 倒推概率dp
\(f[i][j]\) 表示第 i 个 boss，当前有 \(j\) 颗宝石，期望下最大存活天数。
若不打 \(f[i][j] \leftarrow
\begin{cases}
f[i+1][j-(d[i+1]-d[i])]& j \ge d[i+1]-d[i]\\
d[i] + j & otherwise
\end{cases}\)
若打 \(f[i][j] \leftarrow (1-p[i])*d[i] + p[i]*f[i+1][\min(m, j-1+w[i])]\)。
孵化者
n 个人，每人两个 bool 属性 \((g,p)\)，m 对关系 \((i,j)\in R\)
按顺序操作：
- 赋值 \(g_i\leftarrow True\)
- \(\forall g_i|p_i ,(i,j)\in R, p_j\leftarrow True\)
可以操作任意次，最大化 \(g_i=True \And p_i=Fause\) 的数量。
数据范围 \(T\le 100,n\le 50,m\le 1000\)
建有向图，两个条件：
- 若 i 可以到达 j，则 i,j 只能选一个
- 环上的点一定不选
key: DAG 的最大独立集等于最小可相交路径覆盖
证明显然，一条路径只能选一个点。
在原图中算一下连通性，若 i 可以到达 j ，则在二分图中连边。答案是有效点数 \(-\) 最大匹配。
Day 3
训练题
串匹配
给 n 个模式串和 m 个母串，对于每个模式串，输出是否出现过；对于每个母串，输出出现了多少（个 \(\cdot\) 次）模式串。
数据范围：\(\sum |T| \le 5\times 10^5,\sum |S|\le 10^6\)
key：AC 自动机
宝石迷阵
纯模拟，不说了
*加权 n 皇后
给定 n*n 方格，每个格子上有权值。放 n 个皇后，最大化皇后所在格子的权值和。
数据范围：\(n\le 3000\)
一些可能性：Dancing-Links(X-links)，模拟退火\(\dots\)
讲课
搜索和非确定性算法
Day 4
训练题
有向图
n 个有向图，开始所有棋子在 1 号点，每次选一个棋子移动，不能移动者输。问是否有先手必胜策略，并给出第一步的某个可行方案。
key: SG 函数
组合数
求 \(\binom{n}{m} \bmod Q\) 的值。
数据范围 \(n,Q\le 2\times 10^9,m\le 2\times 10^5\)
第一眼你可能想使用 exlucas 定理，但是 \(O(Q+\log Q)\) 是不能接受的。
突破口在非常小的 m，考虑写成 \(\frac{n^{\underline m}}{m!}\) 的形式，于是分子分母都只有 2e5 个数。
暴力：质因数分解，对每个质因数求 \(m!\) 中它的次数，在分母中直接约去，最后乘起来即可。复杂度 \(O(m\log m)\)
std：应用 exlucas 的思想，先中国剩余定理拆开再算同余式。
买零食
类似二维偏序查找的一个东西（？
二分、st表等瞎搞一下即可。
Day 5
训练题
*基因测序
给定 n 个长度不超过 64 的 A T G C 模式串，求最短的母串，包含所有模式串。
数据范围 \(n\le 1.5\times 10^5\)
常规的，我们使用 AC 自动机上状压 dp 来解决这个问题。
但是数据范围并不允许
基因对齐
求两个字符串的最长公共子序列。
数据范围 \(|S|\le 10^5\)
直接使用空间 O(n)，时间 O(n^2) 的 dp，跑大约 400s
基因发现
给定一个文本串，求最长的出现至少 3 次的子串。
数据范围 \(|S|\le 10^5\)
key：二分 + hash
若存在长度为 k 的合法子串，则一定存在长度为 \(k-1,k-2,\dots,1\) 的，故可以二分答案，转化为判断是否存在长为 k 的子串。
显然，长度为 k 的子串只有 \(O(n)\) 个，利用 hash，直接判断是否存在某个值出现 3 次即可。
预处理前缀 hash 值，就可以 O(1) 查询任意子串的 hash。
复杂度 \(O(n\log n)\)
Day 6
训练题
路径排序（Luogu 5353 树上后缀排序）
key：基数排序
利用 SA 中的基数排序思想，倍增的排序就好了。
Luogu 5353 还需考虑去重
后两题太过诡异，跳过好了。
结业测试
骑士的旅行
一棵 n 个点的树，上面有 m 个 boss \((p_i,w_i)\)。支持单点修改位置和武力值，询问路径上武力值前 K 大的 boss 是谁。
数据范围 \(n,m\le 4\times 10^4,Q\le 8\times 10^4,K\le 20\)
key: 树剖 + 线段树
k 很小，故可以线段树暴力维护，复杂度 \(O((n+Q)k\log n)\)
树的同构
给 m 棵 n 个点的有根树（无根树），判断它们的同构关系。
数据范围 \(n,m\le 50\)
key1：AHU 树的最小表示法（括号序）
每棵树都可以转化成若干个 dfs 括号序列，其中字典序最小的是最小表示法。
定理：最小表示法相同的两棵树同构。
于是直接求最小表示法就好了，复杂度 \(O(n^2m)\)
key2：树 hash
找一种不会被卡的哈希方式，直接比较哈希值就可以了。
复杂度可以做到 \(O(nm\log n)\)
一种较好的哈希方式是 \(f(S)=\left(c+\sum\limits_{x\in S}g(x)\right)\bmod P\)
c 是常数，随便设一个就行。g 是整数到整数的映射，最好不用多项式，可以用类似 xor shift，xor 完再随机异或一个常数。
糖果
n 行 m 列表格，填 1 ~ k 的数。要求：
- 每行单调不减
- 任意两行不完全相同
问有多少种不同的填写方案，答案模 P 输出（不保证 P 是质数）。
数据范围 \(n,m\le 10^5,k,P\le 2\times 10^9\)
key: 插板法 + 组合数取模
只需知道每个数有几个，就可以排出一行的方案，有 \(M=\binom{m+k-1}{m-1}\) 种。故 n 行的方案是 \(\binom{M}{n}\) 种。
于是我们可以使用 D4T2 的方法计算这两个数。
隐身术
给定两个串A，B。请问B中有多少个非空子串和A的编辑距离不超过K？
- 子串：B中连续的一段，不同位置算作多个。
- 编辑距离：把一个串变成另一个串需要的最小操作次数，每次操作可以插入、删除或者替换一个字符。
数据范围 \(|A|+|B|\le 10^5,K\le 5\)
key：SA + 暴搜跳 lcp
枚举起点，每次跳到一个需要修改的位置，结束后记录一下个数。
复杂度只有 \(O(n\log n +n 3^k)\)
标签：10,le,最小,times,key,2015,集训,省队,范围 From： https://www.cnblogs.com/Cindy-Li/p/18288719