CF1641D¶
题意¶
给定 \(n\) 个长度为 \(m\) 的数组，每个数组有权值 \(w_i\)，求最小的 \(w_i + w_i\) 使得 \(a_{i, 1}, a_{i,2},\dots, a_{i,m}, a_{j, 1}, \dots, a_{j,m}\) 不同。
\(n \le 10^5, m \le 5, a_i, w \le 10^9\)，数据保证每个数组的 \(m\) 个值不同。
题解¶
Sol.1¶
随机做法。
如果 \(a_i\) 的范围很小，我们可以直接状压寻找即可。考虑将原始的 \(a_i\) 随机映射到 \(0\sim 15\) 的区间中，随机 \(T\) 次，这样我们就可以得到一个 \(O(T(nm + 2^{16} \times 16))\) 的做法。
考虑单次随机一对被正确计算的概率为 \(\dfrac{16!}{6!} \times \dfrac{1}{16^{10}} \approx 0.026\)，因此我们可以取 \(T = 200\)，这样我们可以得到正确率为 \(0.995\)，可以通过此题。
Sol.2¶
暴力bitset做法。
考虑一个完全暴力的bitset，我们对于每个 \(a_{i, j}\) 记录他出现的位置，将数组按照 \(w_i\) 排序，对于位置 \(i\) 我们可以将所有 \(a_{i,j}\) 的bitset或起来，取反后找到第一个为 \(1\) 的位置即可，时空复杂度均为 \(O(\dfrac{n^2m}{w})\) 的。这个做法时间上是可以通过此题的，但是空间会爆炸（cf真快-.-）。
考虑优化，对于 \(a_{i, j}\) 出现次数不超过 \(B\) 的直接暴力记录出现位置，这样可以优化一大部分空间。据说 \(B = \sqrt{\frac{n^2}{mw}}\) 最优，空间复杂度不会算，大概是不超过某个数（？。
Sol.3¶
正解
考虑容斥+双指针即可，容斥的话将所有子集扔到 \(\text{Trie}\) 上面就行，按照 \(w_i\) 排序，假设现在有一对 \((l, r)\) 合法，当 \(r\) 变大的时候， \(l\) 只有变小才能影响答案，就可以双指针扫了。
Sol.4¶
awoo优化bitset
依旧是按权值排序，然后每 \(64\) 个数分一个 \(batch\)，这样只需要考虑所有数和这 \(\frac{n}{64}\) 个 \(batch\) 中最小值的匹配即可，时间复杂度是 \(O(\frac{n^2}{64})\)，空间复杂度是 \(O(nm)\)
CF1119G¶
题意¶
有 \(n\) 个人，将其分为 \(m\) 个组，共有 \(m\) 个敌人，每个敌人有一个生命值 \(h_i\)。每天每个组可以攻击一个敌人，造成的伤害即为组员人数，一个敌人死亡当且仅当生命值非正。问最少多少天可以击败所有的敌人，并给出分组方法以及攻击方法。
\(m \le n \le 10 ^ 6, h_i \le 10 ^ 6\)
题解¶
显然我们的攻击轮数不得小于 \(\lceil{\dfrac{\sum h_i}{n}}\rceil\)，考虑构造出这样一种攻击方式。
如果 \(h_i \ge n\)，我们可以让所有人都攻击这个人直到 \(h_i < n\)。考虑我们现在恰好有 \(h_i\) 个人，那么剩余的 \(n - h_i\) 个人可以继续攻击第 \(i + 1\) 个敌人。若 \(h_{i + 1} < n - h_i\) ，我们又恰好有 \(h_{i + 1}\) 个人，那么剩余的 \(n - h_i - h_{i + 1}\) 可以攻击第 \(i + 2\) 个敌人，一直做下去，这样的过程我们称作一轮。
考虑每一轮我们需要恰好被消灭 \(k_{i, 1}, k_{i, 2}, \dots, k_{i, r_i}\) 个人，我们可以构造 \(p_{j} = \sum\limits_{x = 1} ^ {j} k_{i, j} (j \le r_i)\)，这样我们将所有轮的所有 \(p\) 排序，构造 \(ans_i = p_{i} - p_{i - 1}\) 即可，\(ans_i\) 即为第 \(i\) 组分配的人的个数，这样我们会发现每次消灭恰好多少敌人时我们可以用一个前缀和的人数消灭，并且除了最后一个敌人都可以恰好消灭。
注：官方题解写的有点简陋，不是很正确。
CF1658E¶
题意¶
\(n \times n\) 的矩形，每个位置有一个权值 \(v_{i, j} \le n \times n\) 并且保证所有权值不相同。两个人进行游戏：
-
第一步随意选择一个点。
-
设上一步选择的点为 \((x, y)\)，之后每一步选择的点 \((xx, yy)\) 需要保证 \(|xx - x| + |yy - y| > k\)。
-
每个点的权值可以被无限获得。
问进行无数轮后每个位置开始是否先手必胜。 \(1 \le k \le n - 2, n \le 2000\)
题解¶
设 \(f_{i, j}\) 表示选择了位置 \((i, j)\) 是否能先手必胜，很显然 \(v_{i, j} = n ^ 2\) 时 \(f_{i, j} = 1\)。
考虑从 \(v\) 从大到小转移，设此时位置为 \((x, y)\)。
考虑曼哈顿距离转为切比雪夫距离。
显然我们可以维护 \(f\) 为 \(1\) 的点的出现位置最左最右最上最下即可。
CF1658F¶
题意¶
定义一个 \(01\) 串的权值为 \(\frac{cur_1}{len_s}\)。
问最少取出多少个不相交的子串使得链接后长度为 \(m\)，并且链接后的权值与原串权值相同，如果没有输出 \(-1\)。
\(1 \le m \le n \le 2 \times 10 ^ 5\)
题解¶
\(-1\) 的情况很好判断，现在考虑有解的情况。
一个 nb 结论，答案不会超过 \(2\)。
考虑只分一个子串出来，只需要扫一遍即可。
考虑分两个子串出来，我们证明一定可以选择一个前缀与一个后缀出来。
设我们需要 \(x\) 个 \(1\)，原串共有 \(y\) 个 \(1\)，我们将这个字符串首尾相连变成一个环，\(f_i\) 表示 \(i \sim i + m - 1\) 中 \(1\) 的个数和。
若 \(\max(f_i) < x\)，我们有 \(\sum f_i < n \times x = y \times m\)，而原串中每个 \(1\) 显然会被 \(m\) 个下标计算到，即 \(\sum f_i = y \times m\)，矛盾，因此 \(\max(f_i) \ge x\)。同理知 \(\min(f_i) \le x\)
由于 \(f_i\) 的变化是连续的，因此一定存在两个不同的位置 \(a, b\) 使得 \(f_a \ge x, f_b \le x\)，因此存在位置 \(c \in [a, b]\) 使得 \(f_c = x\)
证毕。
CF1097G¶
题意¶
给定一颗树形结构，设 \(S\) 为非空点集， \(f(S)\) 表示点集 \(S\) 所构成的虚树（？的边的长度和，求 \(\sum_{S} f(S)^k, k \le 200, n \le 10 ^ 5\)
题解¶
有个很牛逼的东西 \(x^k = \sum\limits_{i = 0}^{k} \binom{x}{i} i! \begin{Bmatrix} k \\ i \end{Bmatrix}\)，后面的是第二类斯特林数。
小证一下：
\(x^k = (1 + 1 + \dots + 1)^k\)，考虑 \(k\) 个 \(1\) 出现在哪个位置。
我们可以枚举 \(k\) 个 \(1\) 出现在了 \(e\) 个位置，这样我们就会产生如下的贡献
$$ \binom{x}{e}e!\begin{Bmatrix} k \ e \end{Bmatrix} $$ 得证
因此我们转换一下所求的式子可以得到：
考虑计算 \(\binom{f(S)}{i}\)，这个可以通过DP计算得到，设 \(g_{i, j}\) 表示虚树以 \(i\) 为根，选择了 \(j\) 条边的方案数，\(f_{i, j}\) 表示 \(i\) 的子树以及 \(i\) 到 \(fa_i\) 的边中的虚树选择了 \(j\) 条边的方案数，在枚举链接的子树节点可以得到一个转移：
我们注意到 \(i\) 作为根时需要保证 \(i\) 被选择或者 \(i\) 的至少两个子树都被选择，因此要删除仅选择一个子树的情况。
考虑完子树后有：
初始我们有 \(g_{i, 0} = 2\) 表示 \(i\) 这个点做不做虚树其中的点，注意到 \(f_{i, 1}\) 计算时需要 \(-1\) 因为 \(g_{i, 0}\) 有一种情况是不可以向上面连边的。
总复杂度是经典的树形DP trick，为 \(O(nk)\)