Codeforces Round 556

Posted on | In ,

题目链接

4/5

D. Three Religions

题意

给出一个长度为 $n$ 的字符串，每个字符可以属于三个子序列中的任意一个(只能被一个子序列拥有)，一开始三个子序列都为空，有 $q$ 次询问，每次询问有三个属性，给第 $i$ 个子序列增加/减少一个字符 $c$，问每次询问的合法性。

$(n\le 10^5,q\le10 ^4)$，每个子序列长度最长为 $250$。

题解

  • 显然对于每个子序列每个字符选取的位置是关键的，这个可以转化为每个子序列字符选取的顺序。
  • 定义：$dp[i][j][k]$ 表示第一个子序列匹配了前i个字符，第二个子序列的字符匹配了前j个，第三个子序列匹配了前k个字符的最后一个字符的位置。
  • 为什么上面这个东西一定是对的，这样枚举了三个子序列每个中的每个字符摆放相对顺序，求出来的一定是一个最小位置。
  • 代价也是显然易见的，每次增加看起来都要重新求 $n^3$ 个状态，仔细观察只有 $n ^ 2$ 个。
  • 上面的东西，显然需要一个序列自动机预处理一下。
  • 维护上面的dp是 $n^3$ 的，显然对于每次询问都这样处理是不可行的。
  • 观察可以发现，每次任意一个子序列增加一个字符，只有 $n^2$个状态会修改。
  • 时间复杂度: $O(q·n^2)$

代码

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <stack>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define ll long long

const int maxn = 100000 + 7;

int dp[253][253][253], n, q, k;
char s[maxn], op[7], qc[7];
int nxt[maxn][32];
int str[5][257];

int main() {
  scanf("%d%d", &n, &q);
  scanf("%s", s + 1);
  for (int i = 0; i <= 26; i++)
    nxt[n + 1][i] = n + 1;
  for (int i = n; i >= 0; i--)  {
    for (int j = 0; j < 26; j++) {
      nxt[i][j] = nxt[i + 1][j];
    }
    if (i < n)
      nxt[i][s[i + 1] - 'a'] = i + 1;
  }
  int a, b, c;
  a = b = c = 0;
  while (q--) {
    scanf("%s", op);
    if (op[0] == '+') {
      scanf("%d", &k);
      scanf("%s", qc);
      int cp = qc[0] - 'a';
      if (k == 1) {
        ++a;
        str[1][a] = cp;
        for (int i = 0; i <= b; i++) {
          for (int j = 0; j <= c; j++) {
            dp[a][i][j] = n + 1;
            if (a) dp[a][i][j] = min(dp[a][i][j], nxt[dp[a - 1][i][j]][str[1][a]]);
            if (i) dp[a][i][j] = min(dp[a][i][j], nxt[dp[a][i - 1][j]][str[2][i]]);
            if (j) dp[a][i][j] = min(dp[a][i][j], nxt[dp[a][i][j - 1]][str[3][j]]);
          }
        }
      } else if (k == 2) {
        ++b;
        str[2][b] = cp;
        for (int i = 0; i <= a; i++) {
          for (int j = 0; j <= c; j++) {
            dp[i][b][j] = n + 1;
            if (i) dp[i][b][j] = min(dp[i][b][j], nxt[dp[i - 1][b][j]][str[1][i]]);
            if (b) dp[i][b][j] = min(dp[i][b][j], nxt[dp[i][b - 1][j]][str[2][b]]);
            if (j) dp[i][b][j] = min(dp[i][b][j], nxt[dp[i][b][j - 1]][str[3][j]]);
          }
        }
      } else {
        ++c;
        str[3][c] = cp;
        for (int i = 0; i <= a; i++) {
          for (int j = 0; j <= b; j++) {
            dp[i][j][c] = n + 1;
            if (i) dp[i][j][c] = min(dp[i][j][c], nxt[dp[i - 1][j][c]][str[1][i]]);
            if (j) dp[i][j][c] = min(dp[i][j][c], nxt[dp[i][j - 1][c]][str[2][j]]);
            if (c) dp[i][j][c] = min(dp[i][j][c], nxt[dp[i][j][c - 1]][str[3][c]]);
          }
        }

      }
    }
    else {
      int p;
      scanf("%d", &p);
      if (p == 1) --a;
      else if (p == 2) --b;
      else --c;
    }
    if (dp[a][b][c] != n + 1)
    puts("YES");
    else
     puts("NO");
  }
}