「CROI · R1」浣熊的语言 题解

· · 题解

被出题人 hack 掉然后重新发出的出题人题解。

需要注意的是我们并不关心具体某个单词，只关心每天学习单词数量。而且单词多个复习点重叠不需要进行去重，并且所有单词遗忘曲线相同，所以使用数组累加答案。用数组 new_words 累加新学单词数量（以下简称 nw），用数组 old_words 累加复习单词数量（以下简称 ow）。

因为只关心学习单词个数，所以读入数组 d 时就可以预处理每天的新学单词数量。又因为数组 d 单调不减，所以 d_n 一定为数组元素最大值。

因此从 1 枚举到 d_n，对于每一天，如果新学单词数量非零，那么把这一天所有单词对应的复习点的复习单词数量加上这一天的新学单词数量。形式化地，就是对于每一个 nw_i≠0，将每一个 ow_{i+t_j}(1\leq j \leq k) 加上 nw_i。注意在枚举前后都需要进行一次对于特殊情况的向后累加。

在累加复习单词数量的同时，记录 maxd 表示列举到的最大时间数值。

对于 m 次特殊情况，直接将单词数量往下一个位置上累加即可。注意在这个过程中需要更新 maxd 数值，有一半题解和原 std 因为没考虑这个被 hack 了。具体细节见代码注释。

由于数组 d 单调不减，所以正解总体算法复杂度为 O(d_nk)。

AC code

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

typedef long long ll;
int n, m, k;
int d[1000006], s[1003], t[1005];
int new_word[1001006];
int old_word[1001006];

int main() {
    scanf("%d%d%d", &n, &m, &k);
    int maxd = 0;
    for (int i = 1; i <= n; i ++) {
        scanf("%d", &d[i]);
        new_word[d[i]] ++;
        maxd = max(maxd, d[i]);
    }
    for (int i = 1; i <= m; i ++) {
        scanf("%d", &s[i]);
    }
    for (int i = 1; i <= k; i ++) {
        scanf("%d", &t[i]);
    }

    for (int i = 1; i <= m; i ++) {
        new_word[s[i] + 1] += new_word[s[i]];
        new_word[s[i]] = 0;
    }

    for (int i = 1; i <= maxd; i ++) {
        if (new_word[i] != 0) {
            for (int j = 1; j <= k; j ++) {
                old_word[i + t[j]] += new_word[i];
                maxd = max(maxd, i + t[j]);
            }
        }
    }

   for (int i = 1; i <= m; i ++) {
        new_word[s[i] + 1] += new_word[s[i]];
        new_word[s[i]] = 0;
        old_word[s[i] + 1] += old_word[s[i]];
        old_word[s[i]] = 0;
        maxd = max(maxd, s[i] + 1); // 更新数值！！！
    }

    while (new_word[maxd] == 0 and old_word[maxd] == 0) maxd --;
    printf("%d\n", maxd);
    for (int i = 1; i <= maxd; i ++) {
        printf("%d %d\n", new_word[i], old_word[i]);
    }
    return 0;
}