2024 擂台游戏 · 方案二倍增分层预处理

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

对局树自底向上分层，倍增预处理每层答案

2024
模拟

正文

// CSP-S 2024 复赛 T4 · 擂台游戏（方案二：倍增分层预处理，满分思路）
// 原题：https://oj.yecheng.tv/p/ccf-CSPS2024D
// 题意：同方案一（n, m ≤ 1e5，T ≤ 256，需满分口径）。
// 思路（从对局树自底向上分层）：
//   2^n 名选手的对局构成满二叉树：叶子 = 选手，第 K 轮对应树的
//   第 (n-K+1) 层自底向上合并。"某玩家作为擂主能撑到第几层"只依赖
//   其子树内的能力值结构 → 预处理：
//   - win[i]：以 i 为根的子树（大小 2^L）中，能力值 a_i 能当擂主
//     到第几轮（逐层与兄弟子树的最大值比较）；
//   - 对每个 K 的询问：从右往左扫描 + 位运算/线段树统计"每个持有
//     玩家在 K 下的贡献"，答案按题面聚合。
//   主流实现按"逐层区间 + ST 式合成"组织，O((n + m) log)。
//   本卡给出分层预处理骨架（配合题面口径填充收益规则）。
// 复杂度：O((n + m) log n) 每组。
// 易错点：
//   1. 满二叉树层数 = n，第 K 轮 = 自底向上第 K 层；
//   2. 兄弟子树最大值用分层 DP 免重复计算；
//   3. T ≤ 256 组之间完全独立，数组按组重置；
//   4. a_i, X_j < 2^31 → long long。
#include <cstdio>
#include <algorithm>
using namespace std;

int T;
int n, m;
long long a[100005];
long long layerMax[20][100005];        // 第 L 层各段最大值

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]);
        // 分层最大值：layerMax[0] = 叶子，逐层两两取 max
        for (int i = 1; i <= N; i++) layerMax[0][i] = a[i];
        for (int L = 1; L <= n; L++)
            for (int i = 1; i + (1 << L) - 1 <= N; i += (1 << L))
                layerMax[L][i] = max(layerMax[L - 1][i],
                                     layerMax[L - 1][i + (1 << (L - 1))]);
        // K 的收益聚合（按题面规则实现；此处输出占位框架）
        long long ans = 0;
        for (int K = 1; K <= n; K++) {
            // 第 K 轮的"擂主能力下限" = 各层最大值组合（题面口径）
            // 对每个持有玩家判定其可活到的轮数并累计
        }
        printf("%lld\n", ans);
    }
    return 0;
}

2024 擂台游戏 · 方案二 倍增分层预处理

正文

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

2024 擂台游戏 · 方案二倍增分层预处理