-
拜谢丁真
首先题目有一个很明显的性质：我们肯定只会对前 \(\cfrac{n+1}{2}\) 个数进行操作使它变小。
最后的答案很明显
\[f_{i,j}=\min(f_{i-1,j},f_{i,\frac{j}{i}}+c_i) \]没看出来具有二分答案的性质，考虑怎么 check。实则就是要判断前 \(\cfrac{n+1}{2}\) 个数是否都能 \(\le mid\)。我们可以方便的找出 \(a_i\) 变成 \(\le mid\) 所需的除以的倍数，怎么统计代价。设 \(f_{i,j}\) 表示考虑了前 \(i\) 种操作，除以的倍数为 \(j\) 的代价，然后跑完全背包即可，转移为：最后只在找所需除以的倍数的时候需要考虑一些细节。
-
拜谢 GGrun
将询问的 \(x\) 离线下来从小到大排序，考虑每条边会对哪些询问有贡献。建一颗 \(x\) 的 01 trie 树，每次从小到大往里插入 \(x\)。怎么判断每条边会对哪些询问有贡献？
如果 \(k\) 该位为 \(1\)，另 \(c_i\) 该位为 \(c\)，则在 trie 树上可以往 \(c\oplus 1\) 走，此时异或为 \(1\)；也可以往 \(c\) 走，此时异或为 \(0\)，由于题目要求 \(c_i\oplus x<k\)，所以往 \(0\) 走的这颗子树下的所有 \(x\) 区间都是 \(c_i\) 能有贡献的询问。重复这个操作，我们能找到所有的 \(c_i\oplus x<k\) 的区间，由于 trie 树的树高不超过 \(\log k\)，所以每个 \(c_i\) 能产生贡献的区间个数不超过 \(\log k\)。
找到这些区间有什么用，考虑线段树分治。（虽然叫分治，但好像和分治没什么关系？）在线段树上每个点记录该区间有哪些 \(c_i\) 可以产生贡献，开一个 vector 即可。由于上面已经得知区间个数 \(\le n\log k\) 个，所以显然是开的下的。我们在 trie 树上找 \(c_i\) 能贡献的区间的时候就相当于区间加，直接 update 即可。
查询的时候怎么办？首先，如果查询到线段树上的一个叶子节点 \(x\)，则说明我们肯定把所有能对 \(x\) 有贡献的边都算进来了，（考虑从上往下递归，每经过一个区间，就加上该区间 vector 里的标记）此时直接得出答案即可。然后，我们会退出该叶子节点，退出一个节点的时候，我们应该把该节点的标记都清空，减掉在该节点增加的贡献。用可撤销并查集即可维护，考虑一条边把两个连通块连接到一起，则 \(ans\leftarrow ans+ siz_u\times siz_v\)，退出该节点的时候要减掉这些贡献。
-
拜谢 Qyun
题目要求用 \(n\) 个子串（可以选任意多次）拼成一个母串，每次可以删 \(k\) 个数的最小操作次数。考虑 \(n^2\) 的 DP，设 \(f_i\) 表示母串匹配到了第 \(i\) 个数，转移为：\(f_i=f_j+w_{j+1,i}\)，其中 \(w_{x,y}\) 为用子串凑出母串中区间 \((x,y)\) 的最小代价。
怎么预处理出这个 \(w_{x,y}\) 数组？可以用一个 unordered_map 来存得到字符串 \((x,y)\) 所需的代价。我们发现添加一个子串肯定都是想留下它的一个前缀，而得到这个前缀的所需的代价即为：删去多余部分（长度设为 \(t\)）所需的代价 \(+1\)。如果 \(t\) 的长度不为 \(k\) 的倍数，那我们肯定要想办法在后面添上其他的子串凑出另一个长度 \(t'\)，使得 \(t+t'\equiv 0\pmod k\)。
所以说我们还需处理出一个数组 \(g_i,i\in [1,k)\) 表示在模 \(k\) 意义下，凑出长度为 \(i\) 的字符串的所需代价。类似于“同余最短路”，可以用 dijkstra 转移。
DP 复杂度为 \(O(|S|^2)\)，求出 \(w\) 数组的复杂度为 \(O(\sum |S_i|)\)，预处理 \(g_i\) 数组为 \(O(k\log k)\)。
-
拜谢 9G
首先 \(O(n^2)\) 的暴力很显然，直接枚举每个 \(i\)，check 它是否可以获胜即可。怎么 check？有一个总的限制就是 \(f_x<siz_i-1\)（除 \(i\) 节点以外），其中 \(f_x\) 为 \(x\) 获得的票数。对于每一个节点，我们贪心的考虑，它的儿子都把票投给它，如果满足限制则是合法的，否则就把多余的票上传到它的父亲节点。最终只需检验 \(f_0\) 是否等于 \(0\) 即可，在递归的时候可以不递归 \(i\) 的子树。
正解其实是在这上面的进一步优化。考虑先二分出一个最小的 \(s\)，满足全局的 \(f_x<s-1\)。对于 \(siz\ge s\) 的点，肯定是可以获胜的，对于 \(siz<s-1\) 的点，肯定是不能获胜的。对于 \(siz=s-1\) 的点，有可能获胜，因为该点不合法是因为某点的 \(f_x\ge s-2\)，但其实对于 \(i\) 来说 \(f_i\) 可以等于 \(s-2\)。我们把 \(s-2\) 再带进去跑一遍，如果 \(f_0=1\) 的话，则说明该点能够获胜，否则不能获胜。（考虑可以从 \(i\) 节点到根的路径上撤回一票，因为 \(f_i\) 是可以等于 \(s-2\) 的）
p
