本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-11-05 12:29:05

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

以后或许会补。