CSP-J 2020 真题精讲(上):优秀的拆分与直播获奖

文章首发于公众号 CSP信奥资料交流共享，专注信息学奥赛资料与经验分享。

本期是「CSP-J/S 历年真题���讲」系列第 3 篇，精讲 CSP-J 2020 年 T1「优秀的拆分」和 T2「直播获奖」。

一、写在前面

CSP-J 2020 是疫情后恢复正常比赛的第一年，T1 考察对二进制本质的理解，T2 考察「求第 k 大元素」的数据结构选择。

二、T1 优秀的拆分：二进制分解

2.1 题目背景（原题精炼）

给定一个正整数 n（1 <= n <= 10^7），判断能否将 n 拆分成若干不同的 2 的正整数次幂之和（即 2^1, 2^2, 2^3... 注意不含 2^0=1！）。如果能，输出拆分方案（从大到小排列）；如果不能，输出 -1。

举例：6 = 2 + 4（YES）；7 = 不能拆（NO，输出 -1）；10 = 2 + 8（YES）。

2.2 考点分析

• 核心知识：二进制表示、位运算（&, <<）
• 关键洞察：所有 2 的正整数次幂（2, 4, 8, 16...）都是偶数 → 它们的和也是偶数。因此奇数一定无法拆分！
• 大纲难度：入门 ~ 普及-

2.3 解题思路

思路 1（部分分 · 拼手气）：直接输出 -1。当 n 是奇数时正确（能过部分测试点），但偶数会丢分。

思路 2（满分 · 位运算法）：

1. 先判断 n 是否为奇数 → 输出 -1
2. 如果是偶数，扫描 n 的二进制每一位
3. 对于第 i 位（bit i，2^i），如果该位为 1 且 i >= 1（跳过 bit0），则输出 2^i
4. 从大到小输出

**为什么跳过 bit0？**bit0 = 2^0 = 1，不是「正整数的次幂」，题目要求 2^1, 2^2, 2^3...

2.4 完整代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    // 奇数无法拆分为偶数之和
    if (n & 1) {  // n & 1 等价于 n % 2 == 1
        cout << -1 << "\n";
        return 0;
    }
    
    // 从高位到低位扫描，找到所有 2^k (k>=1)
    vector<int> ans;
    // 从 2^1 开始（i=1），一直到 2^24 ≈ 1.6*10^7 足够覆盖 n
    for (int i = 1; (1 << i) <= n; i++) {
        if (n & (1 << i)) {         // 检查第 i 位是否为 1
            ans.push_back(1 << i);  // 2^i
        }
    }
    
    // 从大到小输出
    for (int i = ans.size() - 1; i >= 0; i--) {
        cout << ans[i];
        if (i > 0) cout << " ";
    }
    cout << "\n";
    
    return 0;
}

更简洁的写法：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    if (n & 1) { cout << -1 << "\n"; return 0; }
    
    // p 从 2 开始（跳过 1），每次左移一位（乘2）
    for (int p = 2; p <= n; p <<= 1) {
        if (n & p) cout << p << " ";
    }
    cout << "\n";
    return 0;
}

2.5 部分分策略

2.6 易错点

1. 忘记奇数输出 -1：最常见的错误，直接按位拆分而不先判断奇偶 → 奇数也能��出 bit0=1
2. 包含了 2^0 = 1：题目要求「正整数的次幂」，不包含 1
3. 输出顺序：题目要求从大到小，注意扫描顺序或最后反转

三、T2 直播获奖：维护动态第 k 大

3.1 题目背景（原题精炼）

一场比赛有 n 位评委依次打分，每位评委打一个分数（1 到 600 之间）。每打完一个分数，就要立即公布当前的获奖分数线：当前已有 w 个人打分，获奖人数 k = max(1, ceil(w × p%) )，分数线 = 第 k 大的分数。求每轮打完后的分数线。

数据范围：n <= 100000，p 为百分数（0100），分数范围 1600。

3.2 考点分析

• 核心知识：第 k 大元素、计数排序（桶排序思想）
• 关键洞察：分数范围只有 1~600！用计数数组 O(600) 查找第 k 大，总复杂度 O(600n)，远优于 O(n^2) 的暴力排序
• 大纲难度：普及- ~ 普及/提高-

3.3 解题思路

思路 1（部分分 · 暴力排序）：每次打完分就 sort，取第 k 大。复杂度 O(n^2 log n)，n=1000 可过，n=10^5 超时，大约 30 分。

思路 2（满分 · 计数排序）：

1. 维护 cnt[601] 数组，cnt[score] = 分数为 score 的人数
2. 每次新打分后：cnt[新分数]++
3. 计算 k = max(1, ceil(w × p / 100))
4. 从 600 到 1 累加 cnt[s]，当累加和 >= k 时，s 就是分数线

复杂度：每轮 O(600)，总 O(600n) ≈ 6×10^7，稳过。

思路 3（更优 · 二分 + 树状数组）：如果分数范围更大（如 10^9），可用树状数组 + 二分，复杂度 O(n log n)。

3.4 完整代码

#include <bits/stdc++.h>
using namespace std;

const int MAX_SCORE = 600;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, w;
    cin >> n >> w;  // w 在这里是获奖比例（百分数）
    // 注意：题目中 w 实际表示百分数 p%，以下用 p 代替
    
    int cnt[MAX_SCORE + 1] = {0};  // cnt[i]: 分数为 i 的人数
    
    for (int i = 0; i < n; i++) {
        int score;
        cin >> score;
        cnt[score]++;   // 记录当前评委的分数
        
        // 计算获奖人数 k = ceil(已打分人数 * p% / 100)
        int people = i + 1;  // 当前已打分人数
        int k = max(1, (people * w + 99) / 100);  // ceil 整数公式
        
        // 从高到低累加，找到第 k 大的分数
        int sum = 0;
        int line = 0;
        for (int s = MAX_SCORE; s >= 1; s--) {
            sum += cnt[s];
            if (sum >= k) {
                line = s;
                break;
            }
        }
        cout << line << " ";
    }
    cout << "\n";
    
    return 0;
}

3.5 部分分策略

3.6 易错点

1. ceil 整数公式：(a + b - 1) / b，这里 (people * w + 99) / 100
2. k = max(1, ...) ：w 可能为 0（取 0% 时），必须强制 k >= 1
3. cnt 数组大小：分数范围 1~600，声明 cnt[601] 防越界
4. 输出格式：数字间用空格分隔（题目通常允许行末空格）

四、部分分策略总表

五、易错点与练习推荐

关联大纲推文：

以上推文均已发布于本公众号历史消息中。

练习题：

1. 洛谷 P7071 优秀的拆分 —— 本题原题
2. 洛谷 P7072 直播获奖 —— 本题原题
3. 洛谷 P1010 幂次方 —— 位运算 + 递归进阶
4. 洛谷 P1923 求第 k 小的数 —— 第 k 大/小通用练习

六、下一期预告

CSP-J 2020 真题精讲（中）：表达式

2020 年 T3 是一道经典的「表达式求值」题，需要用到栈（stack）和表达式树来解析后缀表达式 —— 这可是初赛和复赛都常考的重难点！

关注公众号 CSP信奥资料交流共享，每日推送 CSP-J/S 真题精讲，二进制分解、计数排序这些基础技巧，在复赛里可是送分利器！