(2021) 省选模拟总结
2021.2.20
T1. 人生如一叶
题目要求最大团，而最大团 = 补图的最大独立集。考虑原图的补图，可以发现其有优美的性质——补图是一张二分图。
二分图的最大独立集 = 点数 - 最大二分匹配 ( imes) 2，匈牙利 / 网络流求最大二分匹配即可。
2021.3.29
T1. 要换换名字(name)
可以发现，当一个字符串有不少于 (m) 个不同的子序列时，其一定有解。
所以对于每个字符串，只需要找出前 (n) 小的子序列，设 (Next_{i, c}) 表示第 (i) 位后第一个字符 (c) 的位置，(BFS) 找子序列，由于不同字符串之间可能有相同子序列，所以需要 (trie) 或 (hash) 判重。
每个字符串向子序列连边，发现是一张二分图，二分 + 匈牙利找最大匹配即可。
T3. 获取名额(orz)
最终答案显然为 (1 - prod_{i = l}^{r}(1 - frac{a_i}{x}))。
当 (a_i / x) 比较大(即 (1 - a_i / x) 较小)时，(prod{1 - a_i / x}) 收敛得会很快((0.5^{20} < 10^{-6}))，当其小于 (10^{-6}) 时就可以直接输出了。
但是当 (a_i / x) 比较小精度就过不去了，有 (prod{1 - a_i / x} = exp(sum{ln(1 - a_i / x)}))。
又知道 (ln(1 + x)) 的泰勒展开 (sum_{n = 0}^{infty}{frac{n + 1}{(-1)^{n}} x^{n + 1}})。
所以我们可以设定阈值 (L = 0.5)，每次询问将区间中的数分为两部分，由以上分析可知第一部分的数大概在 (25) 左右；对于第二部分，可以分别预处理出泰勒展开的前 (25) 项的前缀和。最后答案为 (1) - 两部分的贡献相乘。
注意 (x > max(a_i))，所以可以将 (x) 代换为 (x / max(a_i))，(a_i) 代换为 (a_i / max(a_i)) 以避免高精。
2021.3.30
T1. 神奇纸牌(uno)
对于每一张纸牌有 (2^4) 种颜色存在状态，所以我们可以 (2^{2^4}) 枚举所有点数的颜色存在状态并，并查集判断并的合法性，注意！一个并合法当且仅当 并中出现的颜色 全部联通。
那么问题就转化为了有 (n) 个带标号的球和 (m) 个带标号的盒子，要求每个盒子非空的方案数，
简单容斥可以得出方案数为 (sum_{i = 0}^{m}{(-1)^{m- i} i^n inom{m}{i}})。
T3. 打扫笛卡尔(cartesian)
考虑递推，设 (f_i) 为序列长度为 (i) 的期望舒适度的和，(g_i) 为序列长度为 (i) 时期望打扫得到的树的大小之和。
易得：
简单转换可得：
类似地可以得到：(g_i = i! + sum_{j = 0}^{i - 1}{frac{(i - 1)!}{j} g_j})。
(f) 和 (g) 显然可以 (O(n)) 递推，时间复杂度 (O(n))。
2021.4.1
T1. 异或(inception)
令二进制下 (x) 的最高位为 (k)，将消去最低 (k) 位后相同的 (a_i) 归为一组。
可以发现，一组内的选择方案只可能是 (0, 1, 2)，(0, 1) 的方案数显然，(2) 的方案数可以用 (trie) 简单求出。组与组之间的方案数直接相乘。
T2. 计数(interwoven)
等价地求小于等于 (x) 方案数，令 (f_i) 为到第 (i) 位地方案数，转移简单：(f_i = k f_{i - 1} - (k - 1) f_{i - x})。
可以发现转移式等价于：一张 (N) 个点的图，(i) 到 (i + 1) 有 (a) 条边，(i) 到 (i + x) 有 (b) 条边，求 (1) 到 (N) 的方案数，这个问题可以枚举 (b) 的个数计算：
而代回原问题可得:
(O(frac{n}{i})) 预处理 (f_i)，总时间复杂度 (O(n log{n}))。
2021.4.2
T1. 盗梦空间(inception)
首先以题目所给的 (K) 个点为关键点建出虚树，分情况计算 (u) 点：
-
(u) 在虚树的点上，令 (f_i) 表示据 (i) 最近的关键点的距离，简单树形 (dp) 计算。
-
(u) 在虚树边上的某一点，对于长为 (len) 的边 ((x,y))，答案显然为 (lfloor frac{f_x + f_y + len}{2} floor)。但是当 (|x - y| geq len) 时需要特判。
-
(u) 在虚树边上的某一点延伸出的子树的深度最大的点上(不包括端点)，对于边 ((x, y))，找出边上的分界点 (z) 使得 (z) 一下的点离 (f_y) 更近，(z) 以上的点离 (f_x) 更近。
对于 (z) 以上的点，贡献为 (f_x + dep_{max} - dep_u)，(dep_{max}) 表示 (z) 以上子树中最大深度，倍增维护。
对于 (z) 一下的点，贡献为 (f_y + dep_y + dep_max - 2dep_v)，其中 (v) 为 (z) 一下子树深度最大的点，(dep_max) 为其子树最大深度，同样可以倍增维护。
-
(u) 在虚树某一点延伸出子树中深度最大的点，其实与 (3) 本质相同，但是为了方便计算所以分开了。
将每个点的儿子提前按最大深度排序，每次遍历儿子找到第一个不在虚树或虚树的边上的儿子，这样每次询问遍历的点不会超过 (K)，从而保证的时间复杂度的正确。贡献为 (f_x + dep_{max}- dep_x)。
最后还需要注意一些细节。
T2. 爱乐之城(lalaland)
令 (g(n) = sum_{i = 1}^{n}{i sum_{j = 1}^{n}{[i perp j] k}})，(f(n) = sum_{i = 1}^n sum_{j = 1}^n mu(ij))，然后大力推式：
由此我们可以 (O(n)) 预处理出 (g(n))。然后对 (f(n)) 大力推式：
可以发现， (n) 只会影响 (d|n) 的项，所以可以增量求解，时间复杂度调和级数。
最后考虑答案 (F(S) = sum_{T in S} f(gcd(a in T)) prod_{a in T} g(a))，构造函数 (h(d)) 使得 (f(n) = sum_{d|n} h(d))，代入得：
可以发现 (S) 中每加入一个 (a_i)，只会影响约束个数个 (d)，由于保证 (a_i) 互不相同，复杂度依旧是调和计数。
2021.4.5
T1. 悄悄话(word)
考虑从后往前做，令 (f_i) 表示最后一句话是 (i) 串的最大权值和。
将所有串拼接并求出 (sa)，可以发现包括整个串 (i) 的后缀构成一个区间，(st) 表 + 二分可以 (O(log n)) 找出区间。
区间求 (max) 线段树维护即可，每求出 (f_i)，遍历其所有后缀更新线段树上节点。
总时间复杂度 (O(sum |s_i| log (sum |s_i|)))。
2021.4.7
T1. 染色(coloring)
设第 (i) 条横线包括的横线范围为 ([l_i, r_i])，可以发现排序后 (l_i, r_i) 都是单调不下降的。
考虑先染斜线，为了不算重，保证每一条不染的斜线都没有被染的横线 完全包含。考虑 (dp)，设 (f_{i, j}) 为第 (i) 条斜线必选且 ([r_i - j + 1, j]) 的横线都被染的方案数，同时令 (g_i = sum f_{i, j})
枚举上一条染的斜线 (k)，分情况讨论：
-
(r_k < l_i)，此时需要保证 ([r_i - j + 1, j]) 被染，(r_i - j) 不染，([l_i, r_i - j - 1]) 可染可不染，斜线 (k) 染色状态不会对 (i) 造成影响，所以总的贡献为 (2^{r_i - l_i - j} g_k)。
-
(r_i - j > r_k)，同上需保证 ([r_i - j + 1, j]) 被染且 (r_i - j) 不染，但是可选择横线区间变为 ([r_k + 1, r_i - j - 1])，斜向 (k) 的染色状态同样无影响，总贡献为 (2^{r_i - r_k - j - 1} g_k)。
-
(r_i - j <= r_k)，此时斜线 (k) 后 (r_k - r_i + j) 位必染，且 (r_k - r_i + j - 1) 位不染，总贡献为 (f_{k, r_k - r_i + j})。
最终答案为 (sum g_i)。