Eliminate++ - 题解

标签与难度

标签: 动态规划, 线段树, 有限自动机, 构造思想, 博弈论难度: 2400

题目大意喵~

你好呀，指挥官！今天我们来玩一个叫做 "Eliminate++" 的消除游戏，喵~

游戏是在一个写着 $N$ 个不同整数的黑板上进行的，这里的 $N$ 是一个奇数哦。我们要重复进行一种特殊的操作，直到黑板上只剩下一个数字为止。

这个操作是这样的：

在黑板上选择连续的三个数。
擦掉这三个数里最大的和最小的那个，只留下它们的中位数。

每操作一次，黑板上的数字就会减少两个。因为 $N$ 是奇数，所以经过 $(N-1)/2$ 次操作后，一定会剩下唯一一个数字。

我们的任务是，对于最初的 $N$ 个数字中的每一个，判断它有没有可能成为最后那个幸运的“幸存者”，喵~？

输入：一个奇数 $N$ ，和一行 $N$ 个不同的整数。

输出：一个长度为 $N$ 的 01 字符串。如果输入序列中第 $k$ 个数可能存活，那么输出字符串的第 $k$ 位就是 '1'，否则就是 '0'。

解题思路分析

这道题看起来像是个游戏或者搜索问题，但如果直接去模拟所有可能的操作，那状态空间可就大得像宇宙一样啦，肯定会超时的说！所以，我们需要找到一些规律和不变量，用更聪明的办法来解决，喵~

关键转化：幸存者 `x` 和它的伙伴们

让我们换个角度思考。如果我们想让某个特定的数字 x 存活下来，需要满足什么条件呢？

为了方便分析，我们可以把黑板上除了 x 之外的所有数分成两类：

S类 (Smaller)：比 x 小的数。
L类 (Larger)：比 x 大的数。

现在，我们来看看一次操作 (a, b, c) -> median(a, b, c) 会对 S 和 L 类数的数量产生什么影响：

如果 a, b, c 都是 S 类，中位数也是 S 类。这次操作会消耗掉 2个S类数。我们称之为 “纯S操作”。
如果 a, b, c 都是 L 类，中位数也是 L 类。这次操作会消耗掉 2个L类数。我们称之为 “纯L操作”。
如果 a, b, c 中既有 S 类又有 L 类（比如 S, S, L 或 S, L, L），那么中位数可能是 S 或 L，但无论如何，最大的和最小的一定是一个 S 和一个 L。这次操作会消耗掉 1个S类数和1个L类数。我们称之为 “混合操作”。
如果 x 参与了操作，比如 (S, x, L)，为了让 x 存活，它必须是中位数。这样会消耗掉 1个S类数和1个L类数。

全局平衡的奥秘

要让 x 最终存活，我们必须消除掉所有的 S 类和 L 类数。假设最初有 $N_S$ 个 S 类数和 $N_L$ 个 L 类数。

设我们进行了 $op_S$ 次纯S操作， $op_L$ 次纯L操作，以及 $op_{mix}$ 次混合操作（包括 x 参与的那些）。为了消除所有 S 和 L，必须满足下面的方程：

\begin{cases} 2 \cdot op_S + op_{mix} = N_S \\ 2 \cdot op_L + op_{mix} = N_L \end{cases}

两式相减，我们能得到一个超级重要的关系！

2 \cdot (op_S - op_L) = N_S - N_L

op_S - op_L = \frac{N_S - N_L}{2}

这个公式告诉我们一个惊人的事实：为了让 x 存活，我们必须执行的纯S操作和纯L操作的数量之差，是一个由 $N_S$ 和 $N_L$ 唯一确定的常数！

举个例子，如果 S 类数比 L 类数多 10 个（ $N_S - N_L = 10$ ），那么我们必须想办法执行比纯L操作多 5 次的纯S操作（ $op_S - op_L = 5$ ）。我们把这个差值 $|op_S - op_L|$ 称为必需的纯操作差额。

局部操作的能力

知道了全局需要满足的条件，接下来的问题是：在“数字必须连续”这个苛刻的规则下，我们真的能做到需要的目标吗？

纯操作（SSS -> S 或 LLL -> L）有一个特点：它们必须在连续的三个同类数上进行。而且，这些操作不能跨越我们想要保留的 x。如果一个操作是 (a, b, c)，而 x 在 c 的右边，那么这个操作就完全发生在 x 的左侧。

这意味着，所有纯操作都必须完全在 x 的左边子序列，或者右边子序列内完成。

所以，我们的问题就变成了：

计算出全局必需的纯操作差额，即 $|\frac{N_S - N_L}{2}|$ 。
计算出 x 左、右两边的序列，在遵守连续规则的情况下，最多能提供多少次纯S操作和纯L操作。
比较“能提供的”和“必需的”，如果能满足需求，x 就有可能存活！

例如，如果 $N_S > N_L$ ，我们需要满足：

(\text{左侧最大纯S操作数} + \text{右侧最大纯S操作数}) - (\text{左侧最大纯L操作数} + \text{右侧最大纯L操作数}) \ge \frac{N_S - N_L}{2}

实际上，我们可以简化一下。我们只需要关心数量较多那一类的纯操作。比如 $N_S > N_L$ ，我们只需要计算最多能提供多少次纯S操作，然后看它是否足够。

\text{最大可执行纯S操作数} \ge \frac{N_S - N_L}{2}

这个最大可执行纯S操作数就是 x 左边和右边子序列能提供的纯S操作数之和。

用线段树和自动机加速计算

最棘手的部分来了：如何快速计算一个序列能提供的最大纯操作数呢？

我们可以把这个问题看作一个有限自动机。想象我们从左到右扫描一个 S/L 序列，只关心 S 数（把 L 看作分隔符）。我们用一个状态来表示当前连续遇到的 S 数能产生的“潜力”。

状态0：当前没有连续的S。
状态1：当前有1个连续的S。
状态2：当前有2个连续的S。

当一个新的 S 到来时：

状态0 -> 状态1
状态1 -> 状态2
状态2 -> 状态1，并产生 1次纯S操作！（因为 SSS -> S，3个S变成了1个S，相当于消耗了2个，完成1次操作）

当一个 L 到来时，它会打断连续的 S，所以状态直接回到0。

这个状态转移是满足结合律的，喵！这意味着我们可以把状态转移函数封装成一个 $3 \times 3$ 的矩阵（或者一个结构体），然后用线段树来维护序列上的状态转移。线段树的每个节点存储一个区间对应的状态转移函数。合并两个子区间的函数，就相当于两个状态转移函数的复合。

这样，我们就能在 $O(\log N)$ 的时间里查询任意一个区间的最大纯操作数啦！

最终算法流程

直接对每个 x 都计算一次太慢了。我们可以按 x 的值（或排名）从小到大/从大到小来处理，这样每次只有一个数字的类别会改变，我们只需要在线段树上做单点修改！

预处理：对原始数值进行排序，得到每个数的排名 rank[v] 和每个排名对应的位置 pos[r]。令 mid_rank = (N+1)/2。
检查排名大于中位数的数：我们从大到小遍历排名 i from N down to mid_rank + 1。
- 对于当前要检查的排名 i，S类数是所有排名 < i 的数，L类数是排名 > i 的数。我们需要计算最大可执行纯S操作数。
- 我们维护一棵线段树。在检查排名 i 之前，树上所有排名 < i 的数的位置被标记为“激活”（可以参与纯S操作），其他为“未激活”。
- 当从检查 i 变为检查 i-1 时，只有排名为 i-1 的数从“未激活”变成了“激活”。我们只需在线段树上更新一个点。
- 对每个 i，查询 pos[i] 左边和右边区间的最大纯S操作数之和，记为 max_S_ops。
- 如果 max_S_ops >= (N_S - N_L) / 2，即 max_S_ops >= (i - 1 - (N - i)) / 2 = i - mid_rank，则排名为 i 的数可能存活。
检查排名小于中位数的数：同理，我们从小到大遍历排名 i from 1 to mid_rank - 1。
- 这次 S类数是 < i 的，L类数是 > i 的。我们需要计算最大可执行纯L操作数。
- 我们另维护一棵线段树，在检查 i 时，所有排名 > i 的数被标记为“激活”。
- 如果 max_L_ops >= (N_L - N_S) / 2，即 max_L_ops >= (N - i - (i - 1)) / 2 = mid_rank - i，则排名为 i 的数可能存活。
中位数：排名为 mid_rank 的数， $N_S = N_L$ ，必需差额为0，所以它总是可能存活的。

这样，我们用两遍 for 循环，每一步都是一次线段树的单点修改和两次区间查询，总时间复杂度就是 $O(N \log N)$ ，非常高效，喵~

代码实现

这是我根据上面的思路，精心重构的一份代码，希望能帮到你，喵~

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// 定义自动机的状态转移结构体
// 它可以看作一个3x3的矩阵，描述了一个区间如何改变状态和操作数
struct StateAutomaton {
    // next_state[i]: 输入状态为i时，经过本区间后，输出的状态
    int next_state[3];
    // ops_count[i]: 输入状态为i时，经过本区间后，产生的纯操作数
    int ops_count[3];

    // 默认构造一个“空”区间，它不改变任何状态，也不产生操作
    StateAutomaton() {
        next_state[0] = 0; next_state[1] = 1; next_state[2] = 2;
        ops_count[0] = ops_count[1] = ops_count[2] = 0;
    }
};

// 合并两个区间的状态转移函数 (A followed by B)
StateAutomaton merge(const StateAutomaton& a, const StateAutomaton& b) {
    StateAutomaton result;
    for (int i = 0; i < 3; ++i) {
        // 状态i先经过A区间，变成状态 a.next_state[i]
        // 这个新状态再经过B区间
        result.next_state[i] = b.next_state[a.next_state[i]];
        // 总操作数 = A区间产生的 + B区间产生的
        result.ops_count[i] = a.ops_count[i] + b.ops_count[a.next_state[i]];
    }
    return result;
}

// 全局变量
const int MAXN = 1000005;
StateAutomaton tree[4 * MAXN];
int original_values[MAXN];
int value_to_rank[MAXN];
int rank_to_pos[MAXN];
bool can_survive[MAXN];
int n;

// 定义两种基本单元的自动机
StateAutomaton active_node;   // 代表一个激活的数 (S或L)
StateAutomaton inactive_node; // 代表一个未激活的数 (分隔符)

// 初始化两种基本节点的自动机
void init_automata() {
    // 激活节点：S或L
    // 状态0(空) -> 状态1(1个)
    active_node.next_state[0] = 1; active_node.ops_count[0] = 0;
    // 状态1(1个) -> 状态2(2个)
    active_node.next_state[1] = 2; active_node.ops_count[1] = 0;
    // 状态2(2个) -> 状态1(1个), 并产生1次操作 (SSS->S)
    active_node.next_state[2] = 1; active_node.ops_count[2] = 1;

    // 未激活节点：不改变状态，相当于重置
    inactive_node.next_state[0] = 0; inactive_node.ops_count[0] = 0;
    inactive_node.next_state[1] = 0; inactive_node.ops_count[1] = 0;
    inactive_node.next_state[2] = 0; inactive_node.ops_count[2] = 0;
}

// 构建线段树
void build(int node, int start, int end) {
    if (start == end) {
        // 初始时，所有节点都看作未激活
        tree[node] = inactive_node;
        return;
    }
    int mid = start + (end - start) / 2;
    build(2 * node, start, mid);
    build(2 * node + 1, mid + 1, end);
    tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
}

// 单点更新
void update(int node, int start, int end, int idx, const StateAutomaton& val) {
    if (start == end) {
        tree[node] = val;
        return;
    }
    int mid = start + (end - start) / 2;
    if (start <= idx && idx <= mid) {
        update(2 * node, start, mid, idx, val);
    } else {
        update(2 * node + 1, mid + 1, end, idx, val);
    }
    tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
}

// 区间查询
StateAutomaton query(int node, int start, int end, int l, int r) {
    if (r < start || end < l || l > r) {
        return StateAutomaton(); // 返回一个不产生影响的单位元
    }
    if (l <= start && end <= r) {
        return tree[node];
    }
    int mid = start + (end - start) / 2;
    StateAutomaton p1 = query(2 * node, start, mid, l, r);
    StateAutomaton p2 = query(2 * node + 1, mid + 1, end, l, r);
    return merge(p1, p2);
}

void solve() {
    std::cin >> n;
    std::vector<std::pair<int, int>> sorted_values(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> original_values[i];
        sorted_values[i] = {original_values[i], i};
    }

    // 预处理排名和位置
    std::sort(sorted_values.begin(), sorted_values.end());
    for (int i = 0; i < n; ++i) {
        value_to_rank[sorted_values[i].first] = i;
        rank_to_pos[i] = sorted_values[i].second;
    }
    
    std::fill(can_survive, can_survive + n, false);

    int mid_rank = n / 2;

    // 中位数总是可以存活
    can_survive[rank_to_pos[mid_rank]] = true;

    // 检查排名 > mid_rank 的数
    build(1, 0, n - 1);
    for (int i = 0; i < mid_rank; ++i) {
        update(1, 0, n - 1, rank_to_pos[i], active_node);
    }

    for (int i = mid_rank + 1; i < n; ++i) {
        int required_ops = i - mid_rank;
        int current_pos = rank_to_pos[i];
        
        StateAutomaton left_res = query(1, 0, n - 1, 0, current_pos - 1);
        StateAutomaton right_res = query(1, 0, n - 1, current_pos + 1, n - 1);
        
        int available_ops = left_res.ops_count[0] + right_res.ops_count[0];
        
        if (available_ops >= required_ops) {
            can_survive[current_pos] = true;
        }
        // 为下一次迭代做准备，将当前排名i的数也激活
        update(1, 0, n-1, rank_to_pos[i], active_node);
    }

    // 检查排名 < mid_rank 的数
    build(1, 0, n - 1);
    for (int i = mid_rank + 1; i < n; ++i) {
        update(1, 0, n - 1, rank_to_pos[i], active_node);
    }

    for (int i = mid_rank - 1; i >= 0; --i) {
        int required_ops = mid_rank - i;
        int current_pos = rank_to_pos[i];
        
        StateAutomaton left_res = query(1, 0, n - 1, 0, current_pos - 1);
        StateAutomaton right_res = query(1, 0, n - 1, current_pos + 1, n - 1);
        
        int available_ops = left_res.ops_count[0] + right_res.ops_count[0];

        if (available_ops >= required_ops) {
            can_survive[current_pos] = true;
        }
        update(1, 0, n-1, rank_to_pos[i], active_node);
    }

    // 输出结果
    for (int i = 0; i < n; ++i) {
        std::cout << can_survive[i];
    }
    std::cout << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    init_automata();
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析

时间复杂度: $O(N \log N)$
- 预处理排序和建立映射关系是 $O(N \log N)$ 。
- 我们进行了两轮 for 循环，每轮大约 $N/2$ 次。在每次循环中，我们执行一次线段树的单点更新 update ( $O(\log N)$ ) 和两次区间查询 query ( $O(\log N)$ )。
- 所以，主要部分的复杂度是 $O(N \log N)$ 。
- 总的时间复杂度就是 $O(N \log N)$ 啦，对于 $N=10^6$ 来说是完全可以接受的！
空间复杂度: $O(N)$
- 线段树需要 $4N$ 的空间。
- 我们还需要一些辅助数组来存储排名、位置等信息，大小都是 $O(N)$ 。
- 所以总的空间复杂度是 $O(N)$ ，喵~

知识点总结

这真是一道融合了多种思想的超棒题目呢！让我来总结一下吧：

问题转化：解题的关键第一步，是把复杂的博弈过程，转化为一个关于 S/L 两类数消除的平衡问题。
不变量与必要条件：通过分析操作对 S/L 数量的影响，我们推导出了 op_S - op_L = (N_S - N_L)/2 这个核心的必要条件。这是从全局视角找到的约束。
有限自动机建模：对于“一个序列最多能执行多少次纯操作”这个子问题，我们巧妙地用一个三状态自动机来描述其计算过程。这体现了将动态过程抽象为状态转移的思想。
线段树优化：自动机的状态转移满足结合律，这是使用线段树进行优化的前提。线段树让我们能快速地对动态变化的序列进行区间查询，是解决这类问题的强力工具。
离线处理/扫描线思想：我们没有对每个候选 x 都独立计算，而是按 x 的排名顺序处理。这样每次候选者变化时，序列的 S/L 属性只有微小变动，可以用数据结构高效维护。

希望这篇题解能让你感受到算法的魅力，喵~ 如果还有不懂的地方，随时可以再来问我哦！

Eliminate++ - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

关键转化：幸存者 x 和它的伙伴们 ​

全局平衡的奥秘 ​

局部操作的能力 ​

用线段树和自动机加速计算 ​

最终算法流程 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​