10/15
23:04
OI

CF264D Colorful Stones

CF264D Colorful Stones

神仙题。记录当前状态为(x,y),有一个显然的事实:固定y_i,可以到达的x是一个区间,记为[l_i,r_i],那么当y_i \rightarrow y_{i+1},区间向前单调移动。

不过区间中可能会有无法到达的状态。如果存在字符对(AB,BA),位置是(x_ax_{a+1},y_a,y_{a+1}),那么(a+1,b+1)是无法到达的。

于是可以预处理出某一个串中,这样字符的前缀和,双指针扫另一个串统计答案。

#include <bits/stdc++.h>

const int N = 1e6 + 233;

int n, m, A[N], B[N];
char sA[N], sB[N];
int sum[N][3][3];
long long ans;

int get_int(char c) {
  return c == 'R' ? 0 : c == 'G' ? 1 : 2;
}

int main() {
  scanf("%s %s", sA + 1, sB + 1);
  n = strlen(sA + 1);
  m = strlen(sB + 1);
  for (int i = 1; i <= n; ++i)
    A[i] = get_int(sA[i]);
  for (int i = 1; i <= m; ++i)
    B[i] = get_int(sB[i]);

  for (int i = 2; i <= n; ++i) {
    for (int j = 0; j < 3; ++j)
      for (int k = 0; k < 3; ++k)
        sum[i][j][k] = sum[i - 1][j][k];
    if (A[i] != A[i - 1])
      ++sum[i][A[i]][A[i - 1]];
  }

  for (int i = 1, l = 1, r = 1; i <= m; ++i) {
    if (i == 1) {
      while (r < n && A[r] != B[i])
        ++r;
      ans += r - l + 1;
    } else {
      if (r < n) {
        ++r;
        while (r < n && A[r] != B[i])
          ++r;
      }
      if (A[l] == B[i - 1])
        ++l;
      if (l > n)
        break;
      ans += r - l + 1;
      if (B[i] != B[i - 1])
        ans -= sum[r][B[i - 1]][B[i]] - sum[l][B[i - 1]][B[i]];
    }
  }

  std::cout << ans << std::endl;
  return 0;
}