Educational Codeforces Round 157 (Rated for Div. 2) Solution

· · 个人记录

md，D 题想到了 01trie 结果赛时脑子进水，以为会 TLE，E 题大水题结果没做。

A

Greedy.

B

本质上是把原数组按升序或降序后划分成两个长度相等的子序列，答案是两个数组分别的最大值减最小值的绝对值。

暂且按照升序来。

先把原数组排序，并且考虑划分后的第一个序列包含哪些位置。

显然必然是连续 n 个位置。

C

预处理长度为 i，总和为 j 的数组数量，然后没啥了。

D

b_{n-1} = b_n \oplus a_{n-1} b_{n-2} = b_{n-1} \oplus a_{n-2} = b_n \oplus a_{n-1}\oplus a_{n-2} \cdots b_{1} = b_{n} \oplus a_{n-1} \oplus a_{n-2} \cdots a_1

把 b_1 \oplus b_n,b_2 \oplus b_n ,\cdots,b_{n-1 }\oplus b_n 插入 01trie，然后枚举 b_n，由于题目保证有解，所以无论 b_n 取值如何，最终 b 数组一定满足第一条要求；每次枚举 b_n 只需要检查 b_n 和 01trie 里面插入的值的异或最大值是否小于 n。

E

容易想到，也容易证明， 当一个人打出一个血量为 a，伤害为 b 的牌时，另一个人打出的牌应在伤害大于 a 的基础上，满足血量尽可能高。

也就是说可以对于每张牌，预处理出打出它之后另一个人应该选择什么牌，用 set 维护可以轻松解决这一部分。

注：一张牌打出后，如果有多张最优的牌可以应对，那么随便选一张标记上，都一样。

然后每个牌向应对它的牌建边。

一张牌打出后，满足以下条件时打出者获胜：

一张牌打出后，满足以下条件时打出者平局：

一张牌打出后，满足以下条件时打出者失败：

F

首先，如果单单计算满足一种条件的方案数，非常简单。

先计算满足条件 2 情况下的方案数，由此寻找突破口。

剩下计算满足条件 2 时，同时满足条件 1 的方案数，此时考虑总方案数减不合法方案数。

设 f(l,r) 代表满足条件 2，且所有元素分布在 [l,r] 的长度为 n 的数组数量。

不合法方案数即 f(0,\infty) - f(0,x-1) - f(x+k,\infty)

这些看上去很难计算，先把它们表示出来。

\cdots

然后发现 f(0,\infty) - f(x+k,\infty) 可以直接算出来。

另外 f(0,x-1) 可以设计一个 O(nx) 的 dp（第 i 位填了 j 的方案数）。

发现复杂度炸了，注意 n \le 10^9，而 x 极小，而第一维转移过程是从 1,2 一直到 n，每次转移整个第二维，可以用矩阵快速幂优化。

未完待续。

G

以后或许会补。