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

思路：

我们发现

K

的值很小。在

\mathcal{O}(NK)

的时间复杂度可过。我们可以让时间倒流，找到最终字符串的位置

i

在原字符串的位置即可。我们直接对其模拟即可。~~那么动态规划在哪？~~

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

\begin{aligned} & now \gets A_i+(now-C_i) &(C_i+1\le now \le C_i+l_i)\\ & now \gets now-l_i &(C_i+l_i<now) \end{aligned}

其中

l_i

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

AC code:

CPP

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

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

文章操作

相关推荐

评论

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