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

· · 题解

出题人题解。

题意简述

有 n 个单词，每个单词在第 d_i 天首次学习。又有 m 天特殊情况，该天单词顺延至第二天学习。

有一个适用于每个单词的遗忘曲线数组 t，长度为 k，其中 t_i 代表这个单词在顺延后的首次学习时间之后 t_i 天会安排复习。

问几天可以学完单词（从数值为 1 的那一天开始计算），以及每一天新学多少单词，复习多少单词。

解题思路

本题根据题意模拟即可。枚举每一个单词的新学时间，再加上 t_i，不就做完了？上代码！

......

是这样的吗？这样的时间复杂度 O(nk)，考虑到 n 较大，最后一个 Subtask 运行时间为 10^9 数量级，会 TLE。但是怎么优化呢？

需要注意的是我们并不关心具体某个单词，只关心每天学习单词数量。而且单词多个复习点重叠不需要进行去重，并且所有单词遗忘曲线相同，所以使用数组累加答案。用数组 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 次特殊情况，直接将单词数量往下一个位置上累加即可。具体细节见代码注释。

由于数组 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;
    }

    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;
}