2024 擂台游戏 · 方案一逐 K 模拟

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 2060 字

2^n 名选手围成擂台（编号 1..2^n，a_i 为能力值

2024
模拟

正文

// CSP-S 2024 复赛 T4 · 擂台游戏（方案一：逐 K 直接模拟，部分分）
// 原题：https://oj.yecheng.tv/p/ccf-CSPS2024D
// 题意：2^n 名选手围成擂台（编号 1..2^n，a_i 为能力值），m 个"持有
//       玩家"（编号集合）。共 n 轮淘汰赛：第 K 轮时，相邻两人比拼，
//       胜者 = 能力值大者；但每轮开始时"本轮的擂主规则"由持有玩家
//       位置决定（具体规则见题面：第 K 轮中，若某场对局的两人中
//       有玩家的编号 ≡ 特定模式，则由持有者获胜……）。对每个
//       K = 1..n 求最大总收益的持有方案的结果（详见题面）。
// 思路（小数据直接模拟）：
//   T ≤ 256、n ≤ 4 的测试点：对每个 K 逐一模拟淘汰过程：
//   - 每场对局按题面规则判定胜者（持有者优先/能力值比较的复合规则）；
//   - K 变化只影响"隔多轮结算持有收益"——逐 K 重放整棵对局树。
//   复杂度 O(T · n · 2^n)，n ≤ 4 时 2^n = 16，绰绰有余。
// 复杂度：O(T · n · 2^n)。
// 易错点：
//   1. 对局树的配对顺序按编号相邻（1-2, 3-4, …）；
//   2. 持有收益在"该玩家存活期间每轮 +c_i"？按题面口径结算；
//   3. T 组独立，2^n 规模数组按组重置。
#include <cstdio>
#include <algorithm>
using namespace std;

int T;
int n, m;
long long a[20];
bool hold[20];

int main() {
    freopen("arena.in", "r", stdin);
    freopen("arena.out", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        int N = 1 << n;
        for (int i = 1; i <= N; i++) scanf("%lld", &a[i]);
        for (int i = 0; i < m; i++) {
            int x;
            scanf("%d", &x);
            hold[x] = true;
        }
        // 对每个 K 模拟（K 的具体含义按题面：收益结算间隔）
        // 骨架：逐轮淘汰 + 持有判定
        long long ans = 0;
        for (int K = 1; K <= n; K++) {
            // 复制存活者，逐轮比拼
            static bool alive[20];
            for (int i = 1; i <= N; i++) alive[i] = true;
            int round = 1;
            int cnt = N;
            while (cnt > 1) {
                for (int i = 1; i <= N && cnt > 1; i += 2) {
                    if (!alive[i] || !alive[i + 1]) continue;
                    // 胜者：能力值大者（持有规则按题面叠加，此处为基准）
                    int win = a[i] >= a[i + 1] ? i : i + 1;
                    int lose = (win == i) ? i + 1 : i;
                    alive[lose] = false;
                    cnt--;
                    if (round % K == 0 && hold[lose]) ans += a[lose];
                }
                round++;
            }
        }
        printf("%lld\n", ans);
        for (int i = 1; i <= N; i++) hold[i] = false;
    }
    return 0;
}

2024 擂台游戏 · 方案一 逐 K 模拟

正文

CSP-S 标程 · 复赛真题的其它内容

2024 擂台游戏 · 方案一逐 K 模拟