音吹高中 - 题解

标签与难度

标签: 动态规划, 0/1背包, 子集和问题, 构造, 博弈论, Bitset优化难度: 2100

题目大意喵~

各位Master，晚上好呀~！今天我们要玩一个超级有趣的擂台游戏，喵~

游戏里有好多人，每个人都有一个体力值 $a_i$ 。当两个人 $i$ 和 $j$ 对决时，他们都会失去 $\min(a_i, a_j)$ 的体力。体力降到 $0$ 或以下的人就会被淘汰下场。游戏会一直进行，直到场上只剩下最后一个人，他就是唯一的胜利者！

我们的主角雨野君可以决定出场顺序，他会安排一个初始所有人的排列 $p$ 。比赛开始后，系统会不断地从排列 $p$ 的开头找到前两个还留在场上的人，让他们进行决斗。

这个游戏还是动态的哦！一开始有 $n$ 个人，之后会陆续有 $q$ 个新角色加入。每当一个新角色加入时，我们都要判断一下，这个刚刚加入的角色有没有可能成为最终的胜利者。如果可能，就要大声喊出 "mono"，并给出一个能让他获胜的出场顺序 $p$ 。如果不行呢，就只能遗憾地说 "nobe" 啦。

简单来说，就是每加一个人，就问这个人能不能赢，能赢的话还要告诉他该怎么站队才能赢，喵~

解题思路分析

这道题看起来像是一个复杂的博弈过程，但只要我们像猫咪一样，找到线头的关键，就能把它理顺啦，喵！

核心思想：把问题转化为集合划分

首先我们来分析一下决斗的本质。当体力为 $h_1$ 的人和体力为 $h_2$ 的人决斗，幸存者的体力会变成 $|h_1 - h_2|$ 。失败者体力归零被淘汰。

我们想让新加入的玩家 T (体力为 $a_T$ ) 获胜。一个非常直接的策略就是，让 T 最后出场。也就是说，在我们的排列 $p$ 中，T 站在最后一个位置。

p = [其他人..., T]

这样一来，所有其他的玩家 O 就会在 T 出场前先进行一轮大乱斗，决出一位“挑战者冠军” C。最后，T 只需要和这位冠军 C 进行最终决战。

T 能否获胜，就取决于他的体力 $a_T$ 是否大于挑战者冠军 C 的最终体力 $h_C$ 。为了让 T 获胜的概率最大化，我们应该想办法让这位挑战者冠军 C 的体力 $h_C$ 尽可能小。

那么问题来了，通过安排 O 中玩家的出场顺序，我们能得到的最小 $h_C$ 是多少呢？

经过一番神奇的思考（挥舞爪子~），我们可以发现，通过巧妙地安排出场顺序，一堆人乱斗后的最终幸存者体力，可以是我们把这群人分成两个集合 $A$ 和 $B$ 后，两个集合的体力总和之差的绝对值，也就是 $|\sum_{i \in A} a_i - \sum_{j \in B} a_j|$ 。

这个问题就变成了经典的 集合划分问题 (Partition Problem)！我们要将集合 O 划分成两个子集 $A$ 和 $B$ ，使得两个子集体力总和的差的绝对值 |S_A - S_B| 最小。

所以，T 能获胜的充要条件是：

a_T > \min_{A \cup B = O} |S_A - S_B|

求解最小体力差：0/1 背包 DP

怎么找到这个最小的差值呢？这可是 0/1 背包问题的经典应用呀！

令 O 中所有玩家的总体力为 $S_O$ 。如果我们把 O 划分成 $A$ 和 $B$ 两组，那么 $S_A + S_B = S_O$ 。我们要最小化的值是 $|S_A - S_B| = |S_A - (S_O - S_A)| = |2S_A - S_O|$ 。

要最小化这个值，我们只需要让 $S_A$ 尽可能地接近 $S_O / 2$ 就好啦。

于是，我们可以用动态规划来解决。设 dp[k] 是一个布尔值，表示在 O 集合中，我们能否选出一部分玩家，使得他们的体力总和恰好为 k。

这是一个典型的 0/1 背包问题：对于 O 中的每个玩家 p（体力为 $a_p$ ），我们有两种选择：选入子集 $A$ ，或者不选。 DP 的状态转移方程是： dp_new[k] = dp_old[k] OR dp_old[k - a_p]

考虑到总体力之和最大可达 $2 \times 10^6$ ，我们可以用 std::bitset 来进行超高速优化！bitset 的或 | 和移位 << 操作可以一次性处理 64 个状态（在64位系统上），速度飞快！ dp_new = dp | (dp << a_p)

当我们处理完 O 中所有玩家后，dp 这个 bitset 就记录了所有可能的子集和。我们只需要在 dp 中找到一个最接近 $S_O / 2$ 的 k，算出 |2k - S_O|，这就是我们要的最小挑战者体力 min_diff。

如果 $a_T > min\_diff$ ，T 就能赢！否则就不能，喵~

如何构造方案？

如果确定了 T 能赢，我们还需要给出一个可行的排列 p。

找出划分方案: 我们需要找到那个能产生 min_diff 的划分 $A$ 和 $B$ 。这可以通过在 DP 过程中记录前驱状态来实现。比如用一个数组 pre[k] 记录为了凑成和为 k，最后一个加入的玩家是谁。通过 pre 数组，我们可以从目标和 k 开始一路回溯，找出集合 $A$ 中的所有玩家。O 中剩下的就是集合 $B$ 了。
构造排列 p: 我们的策略是 p = [p_O, T]，其中 p_O 是其他玩家的排列。现在我们需要构造 p_O，使得其冠军体力恰好是 S_A - S_B (假设 $S_A \ge S_B$ )。
这里有一个非常巧妙的构造方法：
- 我们把玩家分成两队，Team_A (体力总和 $S_A$ ) 和 Team_B (体力总和 $S_B$ ) 。
- 我们维护一个 conceptual 的“当前天平的差值” balance，初始为 $0$ 。
- 我们从 Team_A 和 Team_B 中轮流挑选玩家来构建 p_O：
  - 如果 balance > 0 并且 Team_B 还有人，就从 Team_B 里随便挑一个 b 放入 p_O，然后 balance -= a_b。
  - 否则（balance <= 0 或 Team_B 空了），就从 Team_A 里随便挑一个 a 放入 p_O，然后 balance += a_a。
- 这个过程可以被证明，最终产生的排列 p_O，其乱斗冠军的体力恰好是 $|S_A - S_B|$ ！
最后，把 T 放在 p_O 的末尾，就构成了我们最终的答案排列 p。

整体流程

对于每个新加入的玩家 T：

O 是 T 之前的所有玩家。计算他们的总血量 $S_O$ 。
利用我们维护的 dp bitset，找到一个存在的子集和 k，使得 |2k - S_O| 最小。
判断 $a_T$ 是否大于这个最小差值。
若大于，则 T 能赢。输出 "mono"。利用 pre 数组回溯找到集合 A 和 B，然后用天平法构造排列并输出。
若不大于，则 T 不能赢。输出 "nobe"。
最后，不要忘记把 T 的信息也更新到 dp 和 pre 数组中，为下一个新玩家的到来做准备！dp |= (dp << a_T)。

这样，我们就能优雅地解决这个问题啦！是不是很清晰了呢，喵~

代码实现

cpp

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

// 定义一个足够大的值来表示体力总和的上限
const int MAX_SUM = 2000001;

// dp[k]为true表示可以凑出和为k的体力
std::bitset<MAX_SUM> dp;
// pre[k]记录凑出和k时，最后一个加入的元素的体力值
int pre[MAX_SUM];
// who[k]记录凑出和k时，最后一个加入的元素的索引
int who[MAX_SUM];

// 存储所有玩家的体力值
std::vector<int> a;

// 用于构造排列p的函数
void print_mono_solution(int target_idx, const std::vector<int>& others_indices) {
    std::cout << "mono\n";
    
    // 1. 计算其他玩家的总血量
    long long others_total_health = 0;
    for (int idx : others_indices) {
        others_total_health += a[idx];
    }

    // 2. 找到最接近 others_total_health / 2 的子集和 k
    long long best_k = -1;
    long long min_diff = -1;

    for (long long k = others_total_health / 2; k >= 0; --k) {
        if (dp[k]) {
            best_k = k;
            break;
        }
    }
    
    // 3. 回溯DP找出划分 A 和 B
    std::vector<int> group_A, group_B;
    std::vector<bool> in_group_A(a.size(), false);
    
    long long current_sum = best_k;
    while (current_sum > 0) {
        int player_idx = who[current_sum];
        int player_health = pre[current_sum];
        group_A.push_back(player_idx);
        in_group_A[player_idx] = true;
        current_sum -= player_health;
    }

    for (int idx : others_indices) {
        if (!in_group_A[idx]) {
            group_B.push_back(idx);
        }
    }
    
    // 4. 使用天平法构造其他玩家的排列 p_others
    std::vector<int> p_others;
    long long balance = 0;
    auto it_A = group_A.begin();
    auto it_B = group_B.begin();

    // 确保体力总和较大的一组是A
    if (best_k < others_total_health - best_k) {
        std::swap(group_A, group_B);
        std::swap(it_A, it_B);
    }

    while (it_A != group_A.end() || it_B != group_B.end()) {
        if (balance > 0 && it_B != group_B.end()) {
            p_others.push_back(*it_B);
            balance -= a[*it_B];
            it_B++;
        } else {
            p_others.push_back(*it_A);
            balance += a[*it_A];
            it_A++;
        }
    }

    // 5. 输出最终排列
    for (size_t i = 0; i < p_others.size(); ++i) {
        std::cout << p_others[i] + 1 << " ";
    }
    std::cout << target_idx + 1 << "\n";
}


int main() {
    // 加速输入输出，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // 初始化DP，和为0是总是可以凑出来的（一个都不选）
    dp[0] = 1;
    
    int n, q;
    std::cin >> n;

    std::vector<int> initial_indices;
    long long current_total_health = 0;

    // 处理初始的n个玩家
    for (int i = 0; i < n; ++i) {
        int health;
        std::cin >> health;
        a.push_back(health);
        initial_indices.push_back(i);

        // 更新DP状态
        std::bitset<MAX_SUM> new_additions = (dp << health);
        // 找到所有新产生的和
        std::bitset<MAX_SUM> changed_bits = new_additions & (~dp);
        dp |= new_additions;

        // 记录回溯信息
        for (int k = changed_bits._Find_first(); k < MAX_SUM; k = changed_bits._Find_next(k)) {
            pre[k] = health;
            who[k] = i;
        }
        current_total_health += health;
    }
    
    // 处理q次查询
    std::cin >> q;
    for (int i = 0; i < q; ++i) {
        int new_player_idx = n + i;
        int new_player_health;
        std::cin >> new_player_health;
        a.push_back(new_player_health);

        // 其他玩家就是当前的所有人
        long long others_total_health = current_total_health;
        
        // 寻找最优划分
        long long best_k = -1;
        // 从中间向两边找
        for(long long k = others_total_health / 2; k >= 0; --k) {
            if (dp[k]) {
                best_k = k;
                break;
            }
        }
        
        long long min_diff = std::abs(others_total_health - 2 * best_k);

        if (new_player_health > min_diff) {
            std::vector<int> others_indices;
            for(int j=0; j < new_player_idx; ++j) others_indices.push_back(j);
            print_mono_solution(new_player_idx, others_indices);
        } else {
            std::cout << "nobe\n";
        }

        // 将新玩家加入DP状态，为下一次查询做准备
        std::bitset<MAX_SUM> new_additions = (dp << new_player_health);
        std::bitset<MAX_SUM> changed_bits = new_additions & (~dp);
        dp |= new_additions;

        for (int k = changed_bits._Find_first(); k < MAX_SUM; k = changed_bits._Find_next(k)) {
            pre[k] = new_player_health;
            who[k] = new_player_idx;
        }
        current_total_health += new_player_health;
    }

    return 0;
}

复杂度分析

时间复杂度: $O((n+q) \cdot S / w + q \cdot (\text{construction}))$ , 其中 $S$ 是体力值的总和上限（ $2 \cdot 10^6$ ）， $w$ 是计算机的字长（通常是64）。
- 每次加入一个新玩家，我们都需要更新 bitset，这个操作的复杂度是 $O(S/w)$ 。总共有 $n+q$ 个玩家，所以 DP 部分的总复杂度是 $O((n+q) \cdot S/w)$ 。
- 对于每个查询，如果需要构造方案，回溯和构造排列的时间主要取决于玩家数量，远小于 DP 更新的时间。因此，这部分可以认为是 $O(n+q)$ 。
- 总体来看，时间主要消耗在 bitset 的更新上。
空间复杂度: $O(S)$ 。
- 我们需要一个大小为 MAX_SUM 的 bitset dp，以及同样大小的 pre 和 who 数组来支持回溯。所以空间复杂度由体力总和的上限决定。

知识点总结

这道题是多种思想的美妙结合，就像一杯调配完美的猫薄荷茶，喵~

问题转化: 最关键的一步！将复杂的博弈过程和排列组合问题，转化为一个清晰的数学模型：目标玩家 T 对战所有其他玩家的“冠军”。这大大简化了问题。
集合划分问题: 认识到决定“冠军”最小体力的核心是集合划分问题，即将一组数分成两堆，使其和的差最小。
0/1背包与DP: 使用动态规划是解决集合划分问题的标准方法。本题中，我们用DP来找出所有可能的子集和。
Bitset 优化: 当DP的状态是布尔值且状态空间很大时，std::bitset 是一个超级给力的优化工具。它利用位运算，将复杂度除以一个常数 $w$ ，对于此题是至关重要的。
构造性算法: 不仅要判断“是否可行”，还要给出“如何可行”的方案。本题中，回溯DP找出划分，再用巧妙的“天平法”来构造排列，都是构造性算法的体现。

希望这篇题解能帮到你，Master！如果还有不明白的地方，随时可以来问我哦，喵~

音吹高中 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

核心思想：把问题转化为集合划分 ​

求解最小体力差：0/1 背包 DP ​

如何构造方案？ ​

整体流程 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​