杂题20200623
杂题
(T) 次询问，每次给定 (n, m) ，定义一个 (n) 的排列的权值为满足 (1, 2, cdots, m) 均在其中出现过的最短前缀长度，求 (n) 的所有排列的权值的期望(mod 998244353)
- (Tleq10^7)
- (n, mleq9 imes10^8)
做法一：
包含 (1, 2, cdots, m) 的最短前缀长度等于 (n-(不存在权值 1, 2, cdots, m 的最长后缀长度)) ，这个后缀长度期望等于 (displaystylesum_{i=m+1}^nP(这个数不出现在 1cdots m 中的任意一个数前)) ，即 ((n-m) imesfrac{1}{m+1}) 。所以答案等于 (n-frac{n-m}{m+1})
做法二：
答案可以看做 (frac{displaystylesum_{i=m}^ni imesinom{n-m}{i-m}}{displaystyleinom nm}) ，考虑先求出 (frac{displaystylesum_{i=m}^n(n-i) imesinom{n-m}{i-m}}{displaystyleinom nm}) ，上面是一个组合恒等式
杂题
有 (n) 个元素 (a_i) 和 (m) 个不相同的盒子，你需要将 (n) 个元素放入盒子中，且每个盒子至少有一个元素。定义一种方案的权值为每个盒子内部元素的 (operatorname{and}) 之和，问权值最大值与使得权值最大的分配方案数
(nleq10^5; a_ileq10^9)
考虑从高位到低位考虑，对于当前这一位 (b) ：
- 没有这一位为 (1) 的元素，这一位对权值和方案数均没有贡献
- 所有元素这一位均为 (1) ，这一位会对权值造成 (k imes2^b) 的贡献
- 这一位为 (1) 的元素个数 (cnt<k) ，对每一个这样的元素分配一个盒子，这些盒子不会再添加任何元素，对权值造成这些元素和的贡献，对方案数造成 (A_{k}^{cnt}) 的贡献，剩下的变成了一个子问题
- 否则，将这一位为 (0) 的所有元素 (operatorname{and}) 起来，合并成一个新元素，这一位会对权值造成 ((k-1) imes2^b) 的贡献，剩下的变成了一个子问题
递归完成后会剩下一些元素和 (k') ，对方案数的贡献相当于有 (n') 个互不相同的球放入 (k') 个互不相同的盒子的方案数，可以容斥
杂题
给定 (n) 个串 (s_i) ，有 (q) 个询问，每次询问两个区间 ([l_1, r_1]) 与 ([l_2, r_2]) ，让你给这两个区间的字符串配对，使得每个字符串恰好和另一个区间的字符串一一匹配，我们称这组配对的价值为每组字符串最长公共后缀之和，而你想知道所有配对中最大的价值。
(n, displaystylesum s_ileq10^4; qleq5 imes10^5)
将两个区间的反串建出 trie ，答案是 (displaystylesummin(c_{1, u}, c_{2, u})) 其中 (c_{1, u}, c_{2, u}) 分别表示结束位置在 (u) 节点子树中的 ([l_1, r_1]) 与 ([l_2, r_2]) 中的串的出现次数
标算是四维莫队。。复杂度貌似是 (O(nq^{frac{3}{4}}))
luogu5251 [LnOI2019]第二代图灵机
有 (n) 个位置， (q) 次操作， (c) 种颜色，初始给定每个位置权值 (a_i) 与颜色 (b_iin[1, c])
共有四种操作：
- 修改一个位置的权值
- 将一段区间的颜色赋值为 (x)
- 询问区间中包含 (c) 种颜色，权值和最小的子区间的权值和
- 询问区间中没有重复颜色，权值和最大的子区间的权值和
保证数据随机， (n, qleq10^5; cleq100)
用珂朵莉树维护即可，两个询问可以直接双指针，时间复杂度 (O(nlog n+nc))
有 (n) 个位置，每个位置有权值和颜色， (q) 次询问区间中没有重复颜色权值和最大的子区间的权值和
对于每个位置 (i) ，求出最大的 (pos_i) 满足 ([i, pos_i]) 没有重复颜色。将这些 ([i, pos_i]) 称为特殊区间
对于询问 ([l, r]) ，首先考虑严格包含于 ([l, r]) 的特殊区间的贡献，二维数点统计，否则，答案一定是区间的一段前缀或后缀，预处理即可
貌似也可以离线后拿数据结构维护
hdu6326 Monster Hunter
给定一棵以 (1) 为根的树，所有非根节点上都有一个怪物，这个怪物的属性是二元组 ((a_i, b_i))
你需要击败所有怪物。你初始时在 (1) 节点上，只有击败了 (u) 节点的父亲节点上的怪物才能挑战 (u) 节点上的怪物。对于怪物 (u) ，挑战它会使得你的血量减少 (a_u) ，战胜它后会使得你的血量增加 (b_i) ，在任意时刻你的血量都不能低于 (0) 。
你需要求出你初始时最少需要多少血量，才存在一种合法的击败所有怪物的顺序
(nleq10^5, displaystylesum nleq10^6)
考虑没有树的限制怎么做
将怪物分为两种： (a_ileq b_i) 与 (a_i>b_i)
显然你会按照 (a_i) 升序击败所有 (a_ileq b_i) 的怪物
对于满足 (a_i>b_i, a_j>b_j) 的怪物 (i, j) ，如果 (i) 在 (j) 之前被挑战，需要的血量至少为 (max(a_i, a_i+a_j-b_i)) ；否则，至少需要 (max(a_j, a_i+a_j-b_j))
对于 (a_i+max(a_j-b_i, 0), a_j+max(a_i-b_j, 0)) ：
- 若 (a_j<b_i, a_i<b_j) ，与 (a_i>b_i, a_j>b_j) 矛盾
- 若 (a_j<b_i, a_ige b_j) ，则上式等于 (a_i, a_i+a_j-b_j) ， (i) 排在前面更优秀（此时 (b_i>b_j)）
- 若 (a_jge b_i, a_i<b_j) ，同理， (j) 排在前面更优秀（此时 (b_j>b_i)）
- 若 (a_jge b_i, a_ige b_j) ，则上式等于 (a_i+a_j-b_i, a_i+a_j-b_j) ，选择 (b) 较大的一项更优秀
综上所述，对于 (a_u>b_u) 的怪物，按 (b) 降序选择更优秀
如果有了树的限制，对于当前不考虑树的限制下最优秀的点 (u) ，显然它的父节点 (v) 被选择后，下一次操作一定会选择节点 (u) ，因此可以将 (u) 节点的信息合并到 (v) 节点上
(a_v'=max(a_v, a_u+a_v-b_v))
若 (max(a_v, a_u+a_v-b_v)=a_v) ，则 (b_v'=b_v-a_u+b_u) ；否则， (b_v'=b_v)
用堆维护节点权值即可
杂题
给定两个括号序列 (A, B) ，将它们归并成序列 (C) ，你可以决定归并顺序，问最少在 (C) 中添加多少个括号，使得 (C) 合法
(n=|A|, m=|B|leq10^6)
将左括号 '(' 看做 ((0, 1)) ，将右括号 ')' 看做 ((1, 0)) ，将 (A, B) 分别建成一条链，再将 (A_1, B_1) 与新建虚点 (0) 连接，使用上一道题的做法将树合并，设合并完成后整棵树得到权值 ((a, b)) ， (a) 相当于将 (C) 所有可配对括号删掉后前缀右括号的数量， (b) 相当于将 (C) 所有可配对括号删掉后后缀左括号的数量，因此答案即为 (a+b) ，时间复杂度 (O(nlog n))
记点 (i) 的权值 (val_i) 为 ((a<b?n+m-a:b)) ，若点 (u) 被合并到了点 (v) ，有结论 (val_v'leq val_u)
证明：
开个桶替代堆即可，时间复杂度 (O(n))
luogu6584 重拳出击
给定一棵 (n) 个点，边权为 (1) 的树，树上有 (m) 个 Youyou
初始时，小 Z 在 (x) 号节点上，并且有一把射程为 (k) 的枪。
因为小 Z 技术精湛，所以 Youyou 一打就死，而小 Z 永远不会死掉。
小 Z 和 Youyou 都按回合行动，在每一回合中，按照下面的顺序行动：
- 回合计数器 (+1)（初始为 (0) ）。
- 小 Z 可以用枪射死与小 Z 树上距离小于等于 (k) 的所有 Youyou。
- 如果所有 Youyou 都被消灭了，游戏结束，这时回合计数器的值就是小 Z 用的回合数。
- 小 Z 可以选择沿着一条边，移动到任意相邻节点，也可以选择不动。
- 所有 Youyou 都会沿着他和小 Z 的简单路径向小 Z 移动一条边的距离。如果此时他们在同一个节点，则不动。
小 Z 需要求出消灭所有敌人需要的最小回合数
(n, mleq4 imes10^5)
一定存在一种最优决策使得小 Z 不访问重复节点
因此枚举小 Z 最终停在树上的哪一个节点，用 线段树 / 换根dp 求出这个点到所有点的距离的最大值，即可统计答案
CF1370E Binary Subsequence Rotation
给定两个 (01) 串 (S, T) ，定义一次对 (S) 的操作为，选择 (S) 的一个子序列，将这个子序列内的元素顺时针旋转一次，即 (a_1'=a_k, a_2'=a_1, cdots, a_k'=a_{k-1})
求最少的操作次数使得将 (S) 变为 (T) ， (|S|=|T|=nleq10^6)
贪心地考虑，首先不用考虑 (S_i=T_i) 的位置，其次，会被操作的子序列一定形如 (01010cdots) 或 (10101cdots) ，因此暴力模拟即可
如果记序列 (a_i=egin{cases}0&(S_i=T_i)\1&(S_i=0, T_i=1)\-1&(S_i=1, T_i=0)end{cases}) ，则答案等于 (displaystylemax_{1leq lleq rleq n}{|displaystylesum_{i=l}^ra_i|})
证明：之后填坑（雾）
CF1370F2 The Hidden Pair (Hard Version)
交互题， (T) 组数据
给定一棵 (n) 个点的树，有两个既定的未知节点 (u, v) ，你每次可以向交互器询问 ({1, 2, cdots, n}) 的一个子集 (S) ，交互器会返回 (d=displaystylemin_{xin S}{dis(x, u)+dis(x, v)}) ，和 (d) 对应的 (x) ，其中 (dis(x, y)) 表示树上 (x, y) 之间的路径的边数
F1：你需要在 (14) 次询问内求出 (u, v)
F2：你需要在 (11) 次询问内求出 (u, v)
(Tleq10; nleq2000)
先询问 ({1, 2, cdots, n}) 全集，会得到路径 (u, v) 上的一个点 (rt) 和长度 (len)
以 (rt) 为根，考虑二分 (u) 的深度（假设 (dep_u>dep_v) ， (dep_{rt}=0) ），对于二分中点 (mid) ，将 ({x | dep_x=mid}) 丢进询问，若 (dep_uge mid) ，则返回的 (d=len) ，否则返回的 (d>len)
这样可以求出 (u) ，只需要再询问一次 ({x | dep_x=len-dep_u}) 就可以求出 (v)
这样能够通过 F1 ，可以把二分的初始上界设为 (l=lceilfrac{len}{2} ceil, r=min(len, max{dep_i})) ，再注意一下二分姿势即可通过 F2