A. 睡觉大王（PID 5690）

题目简介

你今天有 n 节课，用一个 01 字符串表示。s_i = 1 表示这是重要课程，必须清醒听课。听完一节重要课后，接下来的 k 节课你也必须保持清醒。其余课程可以逃课睡觉。问最多能睡几节课。

思路分析

直接模拟即可。从左到右扫描每一节课：

• 如果当前课程是重要课（s_i = 1），必须清醒，同时设置一个"强制清醒计时器"为 k。
• 如果当前课程不是重要课：
  • 计时器 > 0：虽然不想听，但被迫保持清醒，计时器减 1。
  • 计时器 = 0：可以睡觉，答案加 1。

时间复杂度 O(n)，非常高效。

C++ 代码

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    
    while (t--) {
        int n, k;
        scanf("%d%d", &n, &k);
        
        char s[105];
        scanf("%s", s);
        
        int ans = 0;       // 能睡觉的课数
        int timer = 0;     // 强制清醒的剩余时长
        
        for (int i = 0; i < n; i++) {
            if (s[i] == '1') {
                // 重要课程，必须清醒，并重置计时器
                timer = k;
            } else {
                if (timer > 0) {
                    // 还在强制清醒期间，不能睡
                    timer--;
                } else {
                    // 可以睡觉！
                    ans++;
                }
            }
        }
        
        printf("%d\n", ans);
    }
    
    return 0;
}

---

B. 日期差值计算（PID 5687）

题目简介

输入两个合法日期（格式 YYYY-MM-DD，范围 0001～2099），计算两个日期之间相差多少天。

思路分析

将每个日期转换为从公元 1 年 1 月 1 日起的天数，然后取差的绝对值。

• 年份贡献：遍历 1 到 year-1 年，闰年加 366 天，平年加 365 天。
• 月份贡献：累加当年 1 到 month-1 月的天数。
• 日期贡献：加上 day。

闰年判断：能被 4 整除且不能被 100 整除，或能被 400 整除。

注意：1900 年能被 4 整除，但也能被 100 整除且不能被 400 整除，所以 1900 年是平年（2 月只有 28 天）！

C++ 代码

#include <iostream>
#include <cstdio>
using namespace std;

// 判断是否为闰年
bool isLeap(int y) {
    return (y % 4 == 0 && y % 100 != 0) || (y % 400 == 0);
}

// 每月天数，下标1~12
int daysInMonth[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

// 计算从公元1年1月1日起，该日期是第几天
long long dateToDays(int y, int m, int d) {
    long long days = 0;
    
    // 累加之前每年的天数
    for (int i = 1; i < y; i++) {
        days += isLeap(i) ? 366 : 365;
    }
    
    // 累加当年之前每月的天数
    for (int i = 1; i < m; i++) {
        if (i == 2 && isLeap(y)) {
            days += 29;  // 闰年2月有29天
        } else {
            days += daysInMonth[i];
        }
    }
    
    // 加上当月的天数
    days += d;
    return days;
}

int main() {
    int y1, m1, d1, y2, m2, d2;
    
    // 按 YYYY-MM-DD 格式读入
    scanf("%d-%d-%d", &y1, &m1, &d1);
    scanf("%d-%d-%d", &y2, &m2, &d2);
    
    long long days1 = dateToDays(y1, m1, d1);
    long long days2 = dateToDays(y2, m2, d2);
    
    // 输出绝对差值
    printf("%lld\n", days1 > days2 ? days1 - days2 : days2 - days1);
    return 0;
}

---

C. 宝藏寻宝游戏（PID 4907）

题目简介

给定一个长度为 n 的序列，q 次询问。每次询问给定区间 [l, r]，求区间内所有正数的和（可以选不连续的元素，但只选正数才能使和最大）。

样例验证：序列 [2, -1, 2, 3, -5, 2]

• 区间 [1,2]：正数只有 a₁=2，答案 = 2
• 区间 [1,3]：正数有 a₁=2, a₃=2，答案 = 2+2 = 4
• 区间 [2,4]：正数有 a₃=2, a₄=3，答案 = 2+3 = 5

思路分析

预处理前缀和：设 pre[i] 表示前 i 个元素中所有正数的和。

pre[i] = pre[i-1] + max(0, a[i])

对于每次询问 [l, r]，答案就是 pre[r] - pre[l-1]。

• 时间复杂度：预处理 O(n)，每次查询 O(1)，总计 O(n + q)。
• 数据范围 n, q ≤ 10⁶，|aᵢ| ≤ 10⁹，最大答案约 10¹⁵，需要用 long long。

C++ 代码

#include <iostream>
#include <cstdio>
using namespace std;

const int MAXN = 1000005;
long long pre[MAXN];  // 前缀和：前i个数中正数的和

int main() {
    int n;
    scanf("%d", &n);
    
    // 读入序列，同时计算正数的前缀和
    for (int i = 1; i <= n; i++) {
        long long x;
        scanf("%lld", &x);
        if (x > 0) {
            pre[i] = pre[i - 1] + x;  // 正数才累加
        } else {
            pre[i] = pre[i - 1];      // 非正数跳过
        }
    }
    
    int q;
    scanf("%d", &q);
    
    while (q--) {
        int l, r;
        scanf("%d%d", &l, &r);
        // 区间 [l, r] 内正数的和 = 前缀和之差
        printf("%lld\n", pre[r] - pre[l - 1]);
    }
    
    return 0;
}

---

D. 卡牌游戏（PID 5691）

题目简介

有两副牌组 A 和 B（由 0~9 的数字组成）。可以对 A 进行两种操作：

1. 全局数字替换：选择两个不同数字 n₁ 和 n₂，将 A 中所有 n₁ 换成 n₂，所有 n₂ 换成 n₁。
2. 位置交换：交换 A 中任意两张牌的位置。

问能否通过若干次操作使 A 变成 B。

思路分析

核心观察：

• 操作 1 可以对 10 种数字做任意排列（多次操作 1 可以组合出任意置换）。
• 操作 2 可以对牌的位置做任意排列。

因此，A 能变成 B 当且仅当：对 A 的每种数字的出现次数排序后，与 B 的排序结果相同。

做法：统计 A 和 B 各自 0~9 每种数字的出现次数，分别排序后比较是否相同。

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    
    while (t--) {
        char a[200005], b[200005];
        scanf("%s%s", a, b);
        
        // 统计 A 和 B 中各数字的出现次数
        int cntA[10] = {0}, cntB[10] = {0};
        
        int len = strlen(a);
        for (int i = 0; i < len; i++) {
            cntA[a[i] - '0']++;
            cntB[b[i] - '0']++;
        }
        
        // 排序后比较（只关心每种频率出现几次，不关心是哪个数字）
        sort(cntA, cntA + 10);
        sort(cntB, cntB + 10);
        
        // 频率分布相同 → 可以互相转换
        bool same = true;
        for (int i = 0; i < 10; i++) {
            if (cntA[i] != cntB[i]) {
                same = false;
                break;
            }
        }
        
        printf(same ? "Yes\n" : "No\n");
    }
    
    return 0;
}

---

E. 霸王龙的新符号（PID 5692）

题目简介

定义运算 a++b：将 a 和 b 的十进制数字拼接成新整数（如 14++2 = 142）。给定 n 个正整数，求有多少个无序对 (i, j)（i ≠ j）使得 nums[i]++nums[j] 是 3 的倍数。

思路分析

关键数学性质：一个整数能被 3 整除 ⟺ 它的各位数字之和能被 3 整除。

拼接操作只是把 a 和 b 的数字连在一起，所以拼接结果的数位和 = a 的数位和 + b 的数位和。

因此：a++b 是 3 的倍数 ⟺ (a 的数位和 + b 的数位和) mod 3 = 0。

做法：

1. 对每个数，计算数位和对 3 取模的余数（0、1 或 2）。
2. 统计余数为 0、1、2 的数各有多少个（cnt[0], cnt[1], cnt[2]）。
3. 合法配对：
   • 余数 0 + 余数 0：C(cnt[0], 2) = cnt[0] × (cnt[0] - 1) / 2
   • 余数 1 + 余数 2：cnt[1] × cnt[2]
4. 总数 = 两者之和。

注意：题目中数字可达 10³⁰，必须当字符串读入，不能用整数类型。

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    
    // cnt[i] 表示数位和 mod 3 == i 的数有多少个
    long long cnt[3] = {0, 0, 0};
    
    for (int i = 0; i < n; i++) {
        char s[35];  // 数字最大 10^30，最多 31 位
        scanf("%s", s);
        
        int len = strlen(s);
        int digitSum = 0;
        
        // 逐位累加数位和
        for (int j = 0; j < len; j++) {
            digitSum += s[j] - '0';
        }
        
        // 对 3 取模，归类计数
        cnt[digitSum % 3]++;
    }
    
    // 余数 0 配 余数 0：从 cnt[0] 个中选 2 个
    long long ans = cnt[0] * (cnt[0] - 1) / 2;
    // 余数 1 配 余数 2：直接相乘
    ans += cnt[1] * cnt[2];
    
    printf("%lld\n", ans);
    return 0;
}

---

总结

题目	难度	算法	时间复杂度
A. 睡觉大王	⭐	模拟	O(n)
B. 日期差值计算	⭐⭐	模拟 / 日期处理	O(y + m)
C. 宝藏寻宝游戏		前缀和	O(n + q)
D. 卡牌游戏		思维 / 排序	O(n)
E. 霸王龙的新符号	⭐⭐⭐	数论 + 计数	O(n * m)