Grakn Forces 2020 题解

· · 个人记录

A

直接从左到右确定即可，因为每个位置有 3 个不同选择，但是相关的限制只有 2 个，所以必然有解。

\Theta(n)

B

记 cnt = a 序列中不同的数的个数。

不难发现如果确定了 m ， 那么 cnt \leq m * (k-1) + 1 的数列都能被表示出来。

至于证明，考虑一下差分数组即可。

每一个 b_i 都可以使差分数组上的 k-1 个位置有值，那么就可以表示出有不超过 m * (k-1) + 1 个不同数字的 a_i 了。

最后特判一下 -1 即可。

\Theta(n)

C

对每个点计算左边的车到达这个点的时间，以及右边的车到达这个点的时间，然后找到两辆车相遇的位置即可。

\Theta(n)

D

记坐标整体右移的距离为 X , 整体上移的距离为 Y .

枚举每一对点 (a,b) (c,d) , 它给答案的贡献就是对于一段 X 的前缀 , Y 必须 \geq 一个值的限制。

对限制做个后缀 max 即可。

\Theta(nm+max(a_i,b_i,c_i,d_i))

E

删掉的权值最小，考虑转化为保留的权值最大。

把集合和数字都看成点，集合里有数字就把这个数字往集合连边，求最大生成树即可。

不难发现这个最大生成树的权值可以达到，并且如果出现环，那么必然会有 rainbow cycle .

证明 : 如果这张图上存在环，那么我们考虑一个环

如果这上面有相同的集合，那么就把它们缩起来，这个环显然还是存在的，并且因为有环，所以我们在缩边的时候**一定能保证环内仍然有 $\geq 2$ 个不同的集合.** $Kruskal$ 即可。 $\Theta((n+m)\log (n+m))

F

难写的做法

一开始 n 个数互不相等，我们把这个局面记为 n 个大小为 1 的下标集合。

不难发现，我们可以做以下两种操作：

1、花费 n 次操作的代价，把两个大小为 n 的集合合并为一个大小为 2n 的集合，这个下标集合内所有下标对应的数仍然是全相等的。

2、花费 0 次操作，分裂两个下标集合。

那我们只需要合并到最后只有两个集合即可。

考虑二进制合并，然后剩下 \Theta(\log n) 个集合，其中最大的集合大小大于 n 的一半。

然后利用最大的集合，把其它集合一一合并起来，这样就只剩两个集合了。

实际测试中对于 n = 15000 的情况只需要 100068 次操作 。

好写的做法

还有一种做法，先求出 k 满足 2^{k+1} \geq n , 然后直接做两次,先使前 2^k 个数变为相等的，再让后 2^k 个数变为相等的即可，操作数比我当场写的做法多一点，但是很好写。

G

一些怨念：当时差 2min 没冲完这个题……

建出 Kruskal 重构树. 不难发现我们取的联通块必然是 Kruskal 重构树上的一个子树。

那么 check 每个子树能否成为一个联通块，然后做一个树上背包即可。

H

记 0 的个数为 cntz , 不难发现答案有一个上界为 \lfloor \frac{cntz}{2}\rfloor .

考虑把序列分为两个部分， L 和 R , 满足 L 部分中的点右边都有 \geq \lfloor \frac{cntz}{2}\rfloor 个 0 , 而 R 部分中的点左边都有 \geq \lfloor \frac{cntz}{2}\rfloor 个 0 , 那么 L 部分只需要考虑在左边的匹配， R 部分只需要考虑在右边的匹配即可 ， 最后答案需要对 \geq \lfloor \frac{cntz}{2}\rfloor 取 \min .

不难发现，对于每个权值只需要在 L 中保留其最靠右的点 l_x , 在 R 中只需要保留其最靠左的点 r_x .

不难构造出一个网络流模型 :

S -> 权值 , 权值 -> l_x , 权值 -> r_x , a_i = 0 的 i -> T. 这些边权值为 1

答案即为这个网络流图的最大流。 最大流 = 最小割 ， 考虑计算最小割。 不难发现，割掉的边一定是一些 S -> 颜色 和 0 的一段在 $L$ 中的前缀 、 一段在 $R$ 中的后缀。 枚举割掉的 0 的在 $L$ 中的前缀的长度，然后用线段树维护对于每个 $R$ 中的后缀的答案即可。 $\Theta(n\log n)

I

考虑观察数列 x \oplus (x-1) , (x-1) \oplus (x-2) \cdots (x-k+1) \oplus (x-k) .

可以发现如果对 x 这个数进行了 k' 次减少操作 , 那么就是把整体的异或异或了 x 所对应的数列的长度为 k' 的前缀。

考虑事先异或上所有 a_i 的异或和，那么问题可以转化为 : 对于每个 x , 只能取它对应的数列x \oplus (x-1) , (x-1) \oplus (x-2) \cdots (x-k+1) \oplus (x-k) .的一段前缀，求取出来的部分的异或和为 0 \cdots 2^c 的方案数。

不难发现数列 x \oplus (x-1) , (x-1) \oplus (x-2) \cdots (x-k+1) \oplus (x-k) 中的数都是形如 2^d - 1 的形式，记 Logk = \lceil \log_2{k}\rceil , 这个数列对于任意的 x ，都最多只有一个 2^d-1 中的 d > Logk .

把完全相同的数列合并到一起，不同的数列一共只有 192 种。

对于这 192 种数列进行 DP 预处理，具体是记 f_{0/1,v,i,now} 为当前决策到第 i 位，前 i 位被选中的数有 now 个，当前异或出来的结果低于 2^{Logk} 的位置为 v , 高于 2^{Logk} 的位置是否有值， 0/1,v 可以唯一确定异或出来的数。

然后把所有的 DP 预处理出来的结果 FWT 合并即可。

如果先多项式 \ln 再用加法来实现这个合并的过程，可以达到一个很优秀的复杂度，参见 EI的提交 , 最慢的点只跑了 93ms .