「CROI · R1」浣熊的语言

GitHub 跳转原题关系图返回列表

按日期统计每天原计划首学人数，再把特殊日顺延和复习偏移都压成批量计数转移，避免逐单词模拟。

OJ: luogu

题目 ID: P9553

难度:普及+/提高

标签:模拟计数推导

日期: 2026-06-19 02:45

题意

每个单词有一个原计划首次学习日 d_i，以及固定的 k 个复习偏移 t_j。

如果某个学习或复习事件落在特殊日，就要顺延到后面第一个非特殊日。题目要求输出最后一天，以及每天新学和复习的数量。

样例过程表

这张表展示样例 3 中，特殊日如何把事件推迟：

天数	新学数量	复习数量
1	1	0
2	1	1
3	0	0
4	2	4

这里最关键的是第 3 天为特殊日，所以原本落在这一天的事件都会整体顺延到第 4 天。

思路

先看一个逐单词模拟的朴素程序：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;

    vector<int> d(n + 1), special_days(m + 1), t(k + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> d[i];
    }

    set<int> special;
    for (int i = 1; i <= m; ++i) {
        cin >> special_days[i];
        special.insert(special_days[i]);
    }
    for (int i = 1; i <= k; ++i) {
        cin >> t[i];
    }

    map<int, long long> learn, review;
    int last_day = 0;

    for (int i = 1; i <= n; ++i) {
        int first_day = d[i];
        while (special.count(first_day)) {
            ++first_day;
        }
        ++learn[first_day];
        last_day = max(last_day, first_day);

        for (int j = 1; j <= k; ++j) {
            int day = first_day + t[j];
            while (special.count(day)) {
                ++day;
            }
            ++review[day];
            last_day = max(last_day, day);
        }
    }

    cout << last_day << '\n';
    for (int day = 1; day <= last_day; ++day) {
        cout << learn[day] << ' ' << review[day] << '\n';
    }
    return 0;
}

这个写法很好理解，但 n 可以到 10^6。继续逐个单词处理会有很多重复工作。

注意到题目给了两个很重要的限制：

d_i <= 1000
t_j <= 1000

也就是说，真正会涉及的日期范围不大，而且同一天原计划首次学习的所有单词，之后的复习安排完全相同。

因此可以按“日期桶”统计：

first_plan[day]：原计划在这天首次学习的人数；
learn[day]：真实在这天首次学习的人数；
review[day]：真实在这天复习的人数。

再预处理 next_day[day]，表示从 day 开始往后第一个非特殊日。

做法分两步：

扫描 first_plan：
- 如果当天是特殊日，就把这一天的人数整批推到下一天；
- 否则它们全部成为 learn[day]。
对每个 learn[day] 和每个复习偏移 t_j：
- 先看原计划复习日 day + t_j；
- 再通过 next_day 找到真实复习日；
- 把这批人数加到 review[target]。

这样就把逐单词的重复操作压成了按日期的批量加法。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76#include <bits/stdc++.h>
using namespace std;

const int MAX_DAY = 5000;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;

    vector<long long> first_plan(MAX_DAY + 5, 0);
    int max_day = 0;
    for (int i = 1; i <= n; ++i) {
        int d;
        cin >> d;
        ++first_plan[d];
        max_day = max(max_day, d);
    }

    vector<int> special_days(m + 1), review_offset(k + 1);
    vector<int> is_special(MAX_DAY + 5, 0);
    for (int i = 1; i <= m; ++i) {
        cin >> special_days[i];
        is_special[special_days[i]] = 1;
        max_day = max(max_day, special_days[i]);
    }
    for (int i = 1; i <= k; ++i) {
        cin >> review_offset[i];
        max_day = max(max_day, review_offset[i]);
    }

    vector<long long> learn(MAX_DAY + 5, 0), review(MAX_DAY + 5, 0);

    // 先求每一天实际新学多少单词。特殊日上的任务整体顺延到下一天。
    for (int day = 1; day <= MAX_DAY - 2; ++day) {
        if (first_plan[day] == 0) {
            continue;
        }
        if (is_special[day]) {
            first_plan[day + 1] += first_plan[day];
        } else {
            learn[day] += first_plan[day];
        }
    }

    vector<int> next_day(MAX_DAY + 5, 0);
    next_day[MAX_DAY] = MAX_DAY;
    for (int day = MAX_DAY - 1; day >= 1; --day) {
        if (is_special[day]) {
            next_day[day] = next_day[day + 1];
        } else {
            next_day[day] = day;
        }
    }

    int last_day = 0;
    for (int day = 1; day <= MAX_DAY - 2; ++day) {
        if (learn[day] == 0) {
            continue;
        }
        last_day = max(last_day, day);
        for (int j = 1; j <= k; ++j) {
            int real_day = next_day[day + review_offset[j]];
            review[real_day] += learn[day];
            last_day = max(last_day, real_day);
        }
    }

    cout << last_day << '\n';
    for (int day = 1; day <= last_day; ++day) {
        cout << learn[day] << ' ' << review[day] << '\n';
    }
    return 0;
}

复杂度

设有效日期范围为 D，时间复杂度 $O(D * k)$ ，空间复杂度 $O(D)$ 。

总结

这题看上去像事件模拟，真正的突破点是把“单词”换成“日期计数桶”。相同计划日的一批单词会一起移动，这样就能避免处理一百万个独立对象。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P9553 「CROI · R1」浣熊的语言

题目背景

$\texttt{[2023.08.17 21:44]：}$ 为防止神奇的暴力做法通过，本题时限改为 $500\ ms$ 。

他复瞑着，沙地上的文字。
词句，日忆夜诵，挥翰成风；夜幕下，星罗棋布。
新意，呼之欲出，似即却离；叹气里，功败垂成。
她释然一笑，潇然起身，轻叩他的后背。
却见流光间，熊爪翻飞；夜风中，新词真切。
“你做到了……”
平凡的仲夏夜，深刻的文字。
忆诵的努力，闪烁着星光……

题目描述

小浣熊 CleverRaccoon 遵循浣熊的单词遗忘曲线，从第 $1$ 天开始背单词。

一共有 $n$ 个单词，正常情况下，第 $i$ 个单词将在第 $d_i$ 天首次学习。

同时，每个单词都会安排 $k$ 次复习，对于第 $j$ 次复习有复习点 $t_j$ ，表示正常情况下，每个单词在首次学习后 $t_j$ 天都会安排这个单词的复习。换言之，第 $i$ 个单词的第 $j$ 次复习时间为第 $d_i+t_j$ 天。

另外，还有 $m$ 天为特殊情况，第 $i$ 次特殊情况发生在 $s_i$ 天。小浣熊 CleverRaccoon 在当日忘记背单词了，与当日冲突的首次学习或复习时间将顺延至第二天学习或复习。

若某单词的首次学习时间顺延至第二天，则该单词按顺延后的首次学习时间安排复习。
若某单词的当次复习时间顺延至第二天，则不影响该单词的后续复习时间。
若多个学习或复习时间重合于一天，则当天需要进行多次学习或复习。

小浣熊 CleverRaccoon 想知道：学习和复习完所有单词需要的天数、每天新学单词数、每天复习单词数。

输入格式

第一行，三个整数 $n,m,k$ ，表示需背单词的总数、特殊情况的天数、每个单词均需复习的次数。

第二行， $n$ 个整数 $d_i$ ，表示每个单词的首次学习时间。保证 $d$ 单调不减。

第三行， $m$ 个整数 $s_i$ ，表示特殊情况日期。保证 $s$ 单调递增。特别地，若 $m=0$ ，则没有该行数据。

第四行， $k$ 个整数 $t_i$ ，表示所有单词的每个复习点。保证 $t$ 单调递增。

输出格式

第一行，一个整数，表示小浣熊 CleverRaccoon 学习和复习完所有单词需要的天数 $x$ 。

接下来有 $x$ 行，每行两个整数，表示每天的学习单词数量和复习单词数量。

输入输出样例 #1

输入 #1

text

输出 #1

text

输入输出样例 #2

输入 #2

text

输出 #2

text

输入输出样例 #3

输入 #3

text

输出 #3

text

说明/提示

设依次输入的单词编号分别为 $1 \sim n$ 。

样例解释 #1

天数	新学单词编号	新学单词数量	复习单词编号	复习单词数量
$1$	$1,2,3$	$3$	$-$	$0$
$2$	$4$	$1$	$1,2,3$	$3$
$3$	$5$	$1$	$1,2,3,4$	$4$
$4$	$-$	$0$	$4,5$	$2$
$5$	$-$	$0$	$5$	$1$

样例解释 #2

天数	新学单词编号	新学单词数量	复习单词编号	复习单词数量
$1$ (special)	$-$	$0$	$-$	$0$
$2$	$1,2,3,4$	$4$	$-$	$0$
$3$	$5$	$1$	$1,2,3,4$	$4$
$4$	$-$	$0$	$1,2,3,4,5$	$5$
$5$	$-$	$0$	$5$	$1$

样例解释 #3

天数	新学单词编号	新学单词数量	复习单词编号	复习单词数量
$1$	$1$	$1$	$-$	$0$
$2$	$2$	$1$	$1$	$1$
$3$ (special)	$-$	$0$	$-$	$0$
$4$	$3,4$	$2$	$1,1,2,2$	$4$
$5$	$5$	$1$	$2,3,4$	$3$
$6$	$-$	$0$	$3,4,5$	$3$
$7$	$-$	$0$	$3,4,5$	$3$
$8$	$-$	$0$	$5$	$1$

数据范围

本题采用 Subtask 捆绑测试。

对于 $100\%$ 的数据，保证 $1\leq n\leq 10^6,0\leq m\leq 200,1\leq k,d_i,t_i\leq 10^3,s_m < d_n$ 。保证 $d$ 单调不减， $t,s$ 单调递增。

Subtask	$n$	$m$	$k$	$d_i$	$t_i$	Score
$0$	$\leq 100$	$=0$	$\leq 10$	$\leq 100$	$\leq 100$	$5$
$1$	$\leq 10^3$	$=0$	$\leq 100$	$\leq 10^3$	$\leq 100$	$20$
$2$	$\leq 100$	$\leq 10$	$\leq 10$	$\leq 100$	$\leq 100$	$15$
$3$	$\leq 10^3$	$\leq 100$	$\leq 100$	$\leq 10^3$	$\leq 100$	$25$
$4$	$\leq 10^6$	$\leq 200$	$\leq 10^3$	$\leq 10^3$	$\leq 10^3$	$35$

「CROI · R1」浣熊的语言

目录

题意

样例过程表

思路

代码

复杂度

总结

一图流解析