「JOISC 2015 Day1」复制黏贴 2 题解

First Post:

Last Update:

给定一个串 和 次操作以及长度上限 , 每次操作是形如 的一个三元组, 意味把串中的 复制并插入到 位置, 那之后如果串中有多于 个字符, 则会删至 个. 求最后串中的前 个字符.

. 保证操作都是合法的.

考虑倒序模拟操作. 设 为考虑在一个长度无穷的串上执行 中的操作, 串中的第 个字符最终映射到哪个位置. 倒序枚举 , 考虑第 次操作对 的影响.

  • 若 : 无影响, 即 .
  • 若 : 变为 中的数, 也即 .
  • 若 : 向前推 位, 也即 .
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
#include<bits/stdc++.h>
#define f(i,x,y) for(int i=x, i##end=y; i<=i##end; ++i)
#define d(i,x,y) for(int i=y, i##end=x; i>=i##end; --i)
#define uf(i,x,y) for(int i=x, i##end=y; i<i##end; ++i)
#define ll long long
#define pir pair<int, int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back 
char ch;
int rd() {
  int f=1, x=0; ch=getchar();
  while(!isdigit(ch)) { f=((ch=='-')?-1:f); ch=getchar(); }
  while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
  return x*f;
}
void rd(int& x) { x=rd(); }
using namespace std;
#define _ 200005
int k, m, n; char str[_]; int a[_], b[_], c[_], p[_];
int main() {
  rd(k); rd(m); scanf("%s", str+1); rd(n); f(i,1,n) rd(a[i]), rd(b[i]), rd(c[i]);
  f(j,1,k) p[j]=j;
  d(i,1,n) {
    f(j,1,k) {
      if(p[j] <= c[i]) continue;
      else if(p[j] <= c[i] + b[i] - a[i]) p[j] = p[j]-c[i]+a[i];
      else p[j] = p[j] - (b[i] - a[i]);
    }
  }
  f(j,1,k) putchar(str[p[j]]);
  return 0;
}