Deltix Round, Autumn 2021

發表於 更新於 分類於 ， Disqus： 文章字數： 1.1k 所需閱讀時間 ≈ 4 分鐘
E(线段树)

E

https://codeforces.com/contest/1609/problem/E

给你字符串只包含abc

给你q次操作,每次操作修改一个位置上的字符为’a’/‘b’/‘c’中的一种

每次操作后,问对于当前字符串,至少修改多少个字符,使字符串不包含abc子序列

子序列定义: 字符串任意位置删除任意个得到的剩余字符串

范围

字符串长度 1e5

询问次数 1e5

题解

一个可以过的方案是

seg(l,r,state) = 最少次数

其中l,r表示一个区间,通过线段树维护

state 是 5bit的状态分别对应a,b,c,ab,bc, 是否在区间中出现过

那么 线段树节点关系 是

f(根, mergestate(statel,stater)) = min(f(左节点,statel)+f(右节点,stater))

其中 产生abc的不更新 根节点状态

问题是 实现起来感觉有点卡常数 $q \cdot log(N) 32 \cdot 32 $ 的运算量 ,2464ms/3000ms 过的, 看到有些其它状态设计,状态如果更少会更快

tourist 300ms 过的

另一个想法是,实际上变成 [不存在a][不存在b][不存在c]的字符串就好了

那 操作代价(其实就是分别移除a,b,c) = count[a][0..i]+count[b][i+1..j]+count[c][j+1..end]

所以对count计算总是先a后b再c

变成了维护 f(l,r,startch, endch) = 最少代价

也就是 在区间[l,r]上 起始位置是计算startch,结束位置是计算endch

这样状态数最多3x3,根据a,b,c的顺序, 真实有效的只有6 个, 计算代价 常数就小很多

代码(前一种)

https://codeforces.com/contest/1609/submission/137409899

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
91
92
93
94
95
96
97
98
99
100
101
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
const int INF = 0x3f3f3f3f;  // 无限大操作
int n, q;
char s[100010];

int t[400010][40];

// bits
// 0 a
// 1 b
// 2 c
// 3 ab
// 4 bc
void mergeState(int o) {
  rep(i, 1, (1 << 5)) { t[o][i] = INF; }
  rep(i, 1, (1 << 5)) {  // 左state
    if (t[o << 1][i] == INF)
      continue;
    rep(j, 1, (1 << 5)) {  // 右state
      // abc = 'a' + 'bc' or 'ab' + 'c'
      if (((i & (1 << 0)) && (j & (1 << 4))) ||
          ((i & (1 << 3)) && (j & (1 << 2)))) {
        continue;
      }
      // new bit state
      int k = i | j;
      // ab = 'a'+'b'
      if ((i & (1 << 0)) && (j & (1 << 1))) {
        k |= (1 << 3);
      }
      // bc = 'b' + 'c'
      if ((i & (1 << 1)) && (j & (1 << 2))) {
        k |= (1 << 4);
      }
      t[o][k] = min(t[o][k], t[o << 1][i] + t[o << 1 | 1][j]);
    }
  }
}

void calc(int o, int pos) {
  rep(i, 1, (1 << 5)) {  // 状态
    t[o][i] = (i & (1 << (s[pos] - 'a'))) ? 0 : INF;
  }
  rep(ch, 'a', 'c' + 1) {
    if (ch == s[pos])
      continue;
    // 一次修改
    rep(i, 1, (1 << 5)) {
      if (i & (1 << (ch - 'a'))) {  // 包含该bit
        t[o][i] = min(t[o][i], 1);
      }
    }
  }
}

void update(int o, int l, int r, int pos, char ch) {
  if (l == r) {
    s[pos] = ch;
    calc(o, l);
    return;
  }
  int m = (l + r) / 2;
  if (pos <= m) {
    update(o << 1, l, m, pos, ch);
  } else {
    update(o << 1 | 1, m + 1, r, pos, ch);
  }
  mergeState(o);
}

void build(int o, int l, int r) {
  if (l == r) {
    calc(o, l);
  } else {
    int m = (l + r) / 2;
    build(o << 1, l, m);
    build(o << 1 | 1, m + 1, r);
    mergeState(o);
  }
}

int main() {
  scanf("%d %d", &n, &q);
  scanf("%s", s);
  build(1, 0, n - 1);
  rep(i, 0, q) {
    int pos;
    char ch;
    scanf("%d %c", &pos, &ch);
    update(1, 0, n - 1, pos - 1, ch);
    int ans = INF;
    rep(i, 1, (1 << 5)) { ans = min(ans, t[1][i]); }
    printf("%d\n", ans);
  }

  return 0;
}

可能包含改成恰好包含快了不少

https://codeforces.com/contest/1609/submission/137444815

1216 ms/3000 ms

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
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
const int INF = 0x3f3f3f3f;  // 无限大操作
int n, q;
char s[100010];

int t[400010][40];

// bits
// 0 a
// 1 b
// 2 c
// 3 ab
// 4 bc
void mergeState(int o) {
  rep(i, 1, (1 << 5)) { t[o][i] = INF; }
  rep(i, 1, (1 << 5)) {  // 左state
    if (t[o << 1][i] == INF)
      continue;
    rep(j, 1, (1 << 5)) {  // 右state
      // abc = 'a' + 'bc' or 'ab' + 'c'
      if (((i & (1 << 0)) && (j & (1 << 4))) ||
          ((i & (1 << 3)) && (j & (1 << 2)))) {
        continue;
      }
      // new bit state
      int k = i | j;
      // ab = 'a'+'b'
      if ((i & (1 << 0)) && (j & (1 << 1))) {
        k |= (1 << 3);
      }
      // bc = 'b' + 'c'
      if ((i & (1 << 1)) && (j & (1 << 2))) {
        k |= (1 << 4);
      }
      t[o][k] = min(t[o][k], t[o << 1][i] + t[o << 1 | 1][j]);
    }
  }
}

void calc(int o, int pos) {
  rep(i, 1, (1 << 5)) {  // 状态
    t[o][i] = INF;
  }
  rep(ch, 'a', 'c' + 1) {
    if (ch == s[pos]){
      t[o][1<<(ch-'a')] = 0;
    }else{
      t[o][1<<(ch-'a')] = 1;
    }
  }
}

void update(int o, int l, int r, int pos, char ch) {
  if (l == r) {
    s[pos] = ch;
    calc(o, l);
    return;
  }
  int m = (l + r) / 2;
  if (pos <= m) {
    update(o << 1, l, m, pos, ch);
  } else {
    update(o << 1 | 1, m + 1, r, pos, ch);
  }
  mergeState(o);
}

void build(int o, int l, int r) {
  if (l == r) {
    calc(o, l);
  } else {
    int m = (l + r) / 2;
    build(o << 1, l, m);
    build(o << 1 | 1, m + 1, r);
    mergeState(o);
  }
}

int main() {
  scanf("%d %d", &n, &q);
  scanf("%s", s);
  build(1, 0, n - 1);
  rep(i, 0, q) {
    int pos;
    char ch;
    scanf("%d %c", &pos, &ch);
    update(1, 0, n - 1, pos - 1, ch);
    int ans = INF;
    rep(i, 1, (1 << 5)) { ans = min(ans, t[1][i]); }
    printf("%d\n", ans);
  }

  return 0;
}