ABC380 题解

赛时秒了 ABCDE（好吧其实还是略有卡顿，写完大概花了 55min），看到 F 有博弈直接跑了，没注意到数据范围这么小，看到 G 一下就会了大致思路，但具体细节上搞复杂了，快写完了才发现不用维护这么多（恼），然后因为某些神秘错误现在都还没有调出来。至于 F，赛后看见数据范围这么小，自己独立做出来了，所以说现在其实有 AK ABC 的潜力（？

A - 123233

直接模拟即可。

B - Hurdle Parsing

直接模拟即可。

C - Move Segment

直接模拟即可。

D - Strange Mirroring

下面下标都从 \(0\) 开始，记 \(n = |S|\)。

假设询问的数为 \(x\)，记 \(p = \left\lfloor \dfrac{x}{n} \right\rfloor\)，\(q = x \bmod n\)，也就是说 \(x\) 在第 \(p\) 的第 \(q\) 位。如果不考虑大小写，那么其字母和原串的第 \(q\) 位相同。接下来判断是否转换其大小写。

记 \(A = S\) 表示操作前的原串，\(B\) 表示把 \(A\) 大小写反转后得到的串。原串经过 \(3\) 次操作后变成 \(A|B|BA|BAAB\)，其中 ”\(\texttt{|}\)“ 用于表示每次操作后结束的位置。其中具有递归性质：对于 \(4 \le q < 8\)，第 \(q\) 段和第 \((q - 4)\) 的大小写相反。于是可以递归地解决这个问题，边界条件为 \(q = 0\)，此时返回原串的大小写。

bool type(i64 x)
{
    if(!x)
        return false;
    return !type(x - (1ll << __lg(x)));
}

char solve(i64 x)
{
    x--;
    i64 p = x / N, q = x % N;
    return type(p) ? to(S[q]) : S[q]; // to(c): 转换大小写
}

E - 1D Bucket Tool

注意到关键性质：颜色段只会合并而不会分裂，这让我们处理起来方便得多。具体实现可以用 set 或并查集。如果颜色段会分裂，并查集根本就处理不了，而强行用 set 无法保证良好的时间复杂度。

set 的实现 | 并查集的实现

P.S：现在才知道往 set 中增加和删除元素不会让原有的迭代器失效。

F - Exchange Game

为了方便，下面称 Takahashi（先手）为 A，Aoki（后手）为 B。

看到数据很小，可以接受指数级的时间复杂度，这启示我们往爆搜或状压的方向去想。

总结题意可以发现：一张牌只有三个去处：要么在 A 手上，要么在 B 手上，要么在桌上。因此我们用每张牌的状态来表示一个游戏局面 \(S\)，代码实现上可以用三进制状压。下面考虑 dp 的具体实现。

记 \(f(S)\) 表示游戏局面为 \(S\)，且轮到 A 时，A 是否必胜。类似地，记 \(g(S)\) 表示游戏局面为 \(S\)，且轮到 B 时，B 是否必胜。这里必须分别设轮到 A 和轮到 B 的状态，因为两人的手牌状态不同，能做的决策也不同。这样 dp 的总状态数为 \(2 \times 3^{N + M + L}\)，可以接受。

• 初始化：注意到一个玩家会输，当且仅当轮到他时他手上没有牌了，因此初始化“某人手上没有牌且轮到此人”的状态为必败状态。
• 转移：如果当前局面为 \(S\)，定义玩家操作后的后继局面为 \(S'\)。我们可以直接暴力枚举出哪张牌以及拿哪张牌，得到所有可能的 \(S'\)。在这些 \(S'\) 中，如果有一个使得轮到对手时对手必输，那么他总可以选择达到这个后继状态，因此对于他来说 \(S\) 是必胜状态。反之，\(S\) 对他就是必败状态。
• 答案统计：记游戏的初始局面为 \(S_0\)，若 \(f(S) = 1\)，则 A 胜，否则 B 胜。

如果你现在就开始兴致冲冲地写代码，你很快会发现一个问题：虽然我们已经有转移方程了，但我们该以什么顺序转移呢？甚至，这样 dp 究竟能否被转移？它有没有可能是有后效性的？可能很多人直接写个记忆化搜索就跑路了，但我认为这个问题还是值得研究的。

（以下分隔线内的内容选读）

一句话概括：每个人手牌上数字的和单调减小，所以每个状态最多被计算一次。

不妨先想想有的状压 dp 为什么可以转移。ABC354E 是一道和本题类似的打牌问题，但区别在于，玩家只能从桌上拿牌，而不能往桌面上放牌。如果记桌面上牌的集合为 \(s\)，拿走了牌之后的状态为 \(s'\)，把它们状压成整数，那么显然有 \(s' < s\)——因为拿走牌的操作就相当于把 \(s\) 的两个二进制位从 \(1\) 变成 \(0\)。这样，我们就可以简单地从小到大枚举状态来转移。

但这样解释没有触及到更本质的东西。如果我们把 dp 中的状态看作图中的节点，而状态之间的依赖关系看作有向边（即，如果状态 \(i\) 要从状态 \(j\) 转移过来，那么连一条 \(j \to i\) 的边）。那么，dp 的无后效性体现在转移图\(\ ^{*}\)上就是没有环，即转移图是 DAG，而 dp 的转移过程就相当于在转移图上做拓扑排序。如果我们要证明 dp 具有无后效性，就相当于要证明转移图上没有环。而在 ABC354E 这道题中，\(s'\) 和 \(s\) 满足 \(s' \sub s\)，而真包含关系是不会形成环的，因此可以转移。

\((*)\)：《算法导论》中“动态规划”一章也提到了这个概念，书中称为“子问题图”，并且边的方向和本文中的定义相反，但本质上没有区别。

我们有没有办法给本题中的状态找到某种关系呢？题目中提到了关键的一点性质：从桌上拿的牌的数字必须小于打出去的牌的数字。这意味着，每次操作后，玩家手上的数字之和单调减小。那么我们就可以从手牌数字和从小到大的顺序转移。实际上这还解释了为什么游戏一定会终止：每次操作都会导致手牌的数字和减小，那么一定会减到 \(0\)，此时游戏就结束了。

严谨地说，我们用三元组 \((S_A, S_B, S_C)\) 来表示一个局面，其中 \(S_A\)，\(S_B\) 和 \(S_C\) 分别表示 A 手牌的集合、B 手牌的集合和桌上的牌的集合。定义 \(\operatorname{sum}(T)\) 表示牌的集合 \(T\) 中，所有牌上面数字的和。定义局面之间的关系 \(<\)，若 \(S' < S\)，则 \(\operatorname{sum}(S'_A) < \operatorname{sum}(S_A)\) 且 \(\operatorname{sum}(S'_B) = \operatorname{sum}(S_B)\)，或 \(\operatorname{sum}(S'_B) < \operatorname{sum}(S_B)\) 且 \(\operatorname{sum}(S'_A) = \operatorname{sum}(S_A)\)。这样我们就成功地找到了一个状态和它的后继状态之间的关系，并且能证明这种关系不会形成环。

（这里用离散数学中“关系”的知识来解释会更好，但本人相关知识的水平相当民科，所以还是算了。）

当然，从代码实现上，真的去找这种状态的关系是很繁琐的，这时可以简单地用记忆化搜索实现转移。实际上你会发现即使没有找到这种关系也可以写出代码，但这并不意味着它不重要。如果转移之间有环，用记搜也是会死循环的。换句话说，知道这种关系存在比它具体是什么更重要。

关键代码实现：

（和上文中的状态定义略有不同：f[0/1][s] 分别表示局面为 s 且轮到 A 或 B 时，其是否必胜。）

int dfs(int o, int s)
{
    if(f[o][s] != -1) // 记忆化
        return f[o][s];
    if(count(s, o) == 0) // 初始化
        return f[o][s] = 0;
    f[o][s] = 0;
    for(int i = 0; i < N + M + L; i++) // 枚举出哪张牌
    {
        if(get(s, i) != o)
            continue;
        f[o][s] |= !dfs(o ^ 1, s - o * pw[i] + 2 * pw[i]); // 不拿任何牌
        for(int j = 0; j < N + M + L; j++) // 枚举拿哪张牌
        {
            if(get(s, j) != 2 || val[j] >= val[i])
                continue;
            int t = s - o * pw[i] + 2 * pw[i] - 2 * pw[j] + o * pw[j]; // 后继状态
            f[o][s] |= !dfs(o ^ 1, t);
        }
    }
    return f[o][s];
}

get(s, i) 表示三进制数 s 的从低位开始的第 i 位，count(s, o) 表示三进制数 s 中为 o 的位数。

局面 s 的第 i 位为 0/1/2 分别表示第 i 张牌在 A 手上/在 B 手上/在桌上。

答案为 f[0][S0]，其中 S0 为初始状态。

完整代码

G - Another Shuffle Window

并不难的期望题。记 \(F(i)\) 表示随机打乱 \([i, i + K - 1]\) 中的元素后，整个序列逆序对数的期望值。把整个序列分成三段：\([1..i - 1]\)，\([i..i + K - 1]\) 和 \([i+K..N]\)，可以发现在操作之后，只有中间这段的逆序对会变化，其它两段之内的和段之间的逆序对都不会改变。而经典结论告诉我们对于长度为 \(K\) 的随机排列，其逆序对的期望数为 \(\dbinom{K}{2}/{2} = \dfrac{K(K-1)}{4}\)。记 \(S\) 代表操作前全局的逆序对数，\(f(i)\) 表示操作前 \([i..i+K-1]\) 中的逆序对数，那么 \(F(i) = S - f(i) + \dfrac{K(K-1)}{4}\)。

接下来就是快速求出 \(f(i)\)。要求逆序对，通常会想到归并排序（分治）和树状数组。前者难以处理动态的问题，而暴力地对每个长度为 \(K\) 的区间求一遍逆序对，时间复杂度无法接受。考虑用树状数组。

我们先求出 \([1..K]\) 之内的逆序对数。思考从 \([i-1,i+K]\) 转移到 \([i,i+K-1]\) 的过程：这相当于从区间中删除 \(P_{i-1}\)，然后加入 \(P_{i+K-1}\)。分别讨论这两个操作对逆序对数的影响：

1. 删除 \(P_{i-1}\)：我们要减去以 \(P_{i - 1}\) 开头的逆序对数量，这等于区间中小于 \(P_{i - 1}\) 的数的个数。
2. 加入 \(P_{i+K-1}\)：要加上以 \(P_{i + K -1}\) 结尾的逆序对数量，这等于区间中大于 \(P_{i + K - 1}\) 的数的个数

可以证明两个操作的顺序无关紧要，但先删除再加入似乎比较好理解。

用权值树状数组维护即可。由于每个数最多进一次区间、出一次区间，所以时间复杂度为 \(O(N \log N)\)。