传送门
https://codeforces.com/contest/1616
Table of Contents
和 去年一样 。。。今年的 GoodBye Round 的 Pretest 也很强。。。
大家新年快乐啦。。。
Problem D. Keep the Average High
数列选数，要求如果原序列中多于1个连续的全被挑中，则满足平均值大于给定的 x，问最多可以选多少
dp，只要考虑长度为 2、3 的段满足条件即可，其它长度自动满足。
Problem E. Lexicographically Small Enough
给定两个字符串 s, t ，每次可以交换两个相邻字符，问至少几次交换可以使得 s 字典序小于 t。
考察 t[0]，方案一：找小于 t[0] 的字符交换到 s[0] 位置。方案二：找等于 t[0] 的字符交换到 s[0] 位置，之后迭代到下个位置。
每次都贪心的找最靠前的，可以开 26 个 deque
Problem F. Tricolor Triangles
给定一个无向图 (n <= 64,m <= 256) 要求对边进行三染色，使得对于任意三元组，如果存在三条边的话，要么颜色全相等，要么全部不相等。
貌似可以随机化乱搞或者高斯消元，后者非常直接，我们的必要条件就是 xi + xj + xk = 0，我们建立模 3 非齐次线性方程组吗，对其增广矩阵进行高斯消元即可，未知数规模是 m，方程组数为 $n^3$ = $m\sqrt(m) $。。最后单组 Case 的复杂度应该是 $O(m^3\sqrt(m))$，复杂度爆炸。。。但是因为这个矩阵非常稀疏，大家都这么爆过去了。。。。。
（直播里 Neal Wu 说一眼就看出要 Gauss 但是估计了一下复杂度认为不可做就跳去做 H 了囧）。
（赛后去爬了一下 Neal Wu 的吐槽，果然被他成功 cha 掉了 AC 的程序，看来 300iq 的数据还是有点弱的。。。）
Problem G. Just Add an Edge
给定一个 dag，问有多少种加一条边的方案，使得加完后图中存在 Hamiltonian path。
dp？
Problem H. Keep XOR Low
给一个数集，问有多少种 subset 方案，使得 subset 种任意两个数的 xor < 给定的数 x。
2-sat？二进制 tire?
看了一下 这个 python 代码，果然容易丽洁。。
简单来说。。先考虑 x = 000111.. 这样的情况。那么显然我们只要进行分组即可，组与组之间相互独立，每个组里可以随便选。考虑一般情况，相当于在一个 binary tire 树上 dp，实际中，我们不需要把这个 tire 构建出来。。。只要用 std::sort() + std::partition_point() 递归处理下去即可。。。
这里有两种定义递归函数的方式：
– f(a,b,i) 表示 a 集合和 b 集合至少都选了一种数，当前考察到 x 的第 i 位的方案数。
– g(a,b,i) 表示允许不选 a 集合或 b 集合的方案数。
显然我们有 g = f + 2^|a| + 2^|b| – 1。
然后我们对第 i 位进行讨论，我们发现一种情况下用 f 表示更方便，另一种情况下用 g 表示更方便。。然后 f 和 g 可以用上面简单的式子进行互相换算，所以我们现在都只看比较短的那一种转移即可，也就是：
- f(a,b,i) = f(a0, b0,i-1) + f(a1, b1,i-1) | x 的第 i 位为 0。
- g(a,b,i) = g(a0, b1,i-1) * g(a1, b0,i-1) | x 的第 i 位为 1。
