题解：P14405 [JOISC 2015] 复制粘贴 2 / Copy and Paste 2

Fengwuy1 · 2025-11-07 20:04:36 · 题解

思路：

我们发现 K 的值很小。在 \mathcal{O}(NK) 的时间复杂度可过。我们可以让时间倒流，找到最终字符串的位置 i 在原字符串的位置即可。我们直接对其模拟即可。那么动态规划在哪？

模拟过程只需简单推导即可。具体地，有如下讨论：

其中 l_i 是复制字符串的长度。这个题就做完了。

::::success[AC code:]

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int k, m, n;
char s[N];
struct node {
    int a, b, c, l;
} ac[N];
int main() {
    cin >> k >> m ;
    scanf("%s", s + 1);
    cin >> n;
    for (int i = n; i >= 1; i--) {
        cin >> ac[i].a >> ac[i].b >> ac[i].c;
        ac[i].l = ac[i].b - ac[i].a;
    }
    for (int i = 1; i <= k; i++) {
        int now = i;
        for (int j = 1; j <= n; j++) {
            if (ac[j].c + 1 <= now && now <= ac[j].c + ac[j].l) {
                now = ac[j].a + (now - ac[j].c);
            } else if (ac[j].c + ac[j].l < now) {
                now -= ac[j].l;
            }
        }
        cout << s[now] ;
    }
    return 0;
}

::::