[CSP-S 2023] 消消乐

· · 个人记录

赛时

想到了一个规律，当一个字符串的头和首相等，并且中间的字符串同样可以被消除的话，那么这个大字串也就可以被消除。

虽然竭尽全力想到了这一点，不过还不知道如何实现，开始的想法是：

先使用 vector 来记录每一个字母所在的分别的下标，然后先从两个相邻字母的开始找（因为这样必定是可以消掉的），然后通过这个字串开始往两边遍历，一直找到找不下去为止。

然而，这样的想法是大错特错的，因为有 CBBAAC 这样的情况，按照我的思想是无法找到的，在考试中想到了 区间dp，同样的在考试中也想到了 栈 来找到一段回文字符串的方法，只是没有想到使用 栈 可以得到 50pts 的好成绩，思路还是很简单的：

每次枚举一个端点 l ，然后对这个 [l, n] 的字串进行括号匹配，这时候就可以累加可以匹配的字符串，就可以完成。

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define rint register int
#define For(i, j, k) for(rint i = j; i <= k; i++)
using namespace std;

inline int read(){
  int f = 1,x = 0;
  char ch = getchar();
  while(!isdigit(ch)){
    if(ch == '-')f = -1;
    ch = getchar();
  }
  while(isdigit(ch)){
    x = (x << 1) + (x << 3) + (ch ^ 48);
    ch = getchar();
  }
  return x * f;
}
inline void print(int x){
  if(x > 9)print(x / 10);
  putchar(x % 10 + '0');
}

string a;

ll ans = 0;
const int ull base = 1e7 + 7;
ull H[2000010];

signed main(){
    int n = read(); cin >> a;
    a = ' ' + a; H[0] = 1;
    For(i, 1, n){
        H[i] = H[i - 1] * base;
    }
    For(i, 1, n){
        stack<char> s; 
        ull cnt = 0;
        For(j, i, n){
            if(!s.empty() && s.top() == a[j])
                cnt -= s.top() * H[s.size()], s.pop();
            else s.push(a[j]), cnt += s.top() * H[s.size()]; 
            if(cnt == 0)
                ans++;
        }
    } 
    cout << ans; 
  return 0;
}

- Solve 1

果然正解其实就藏在骗分之中。

Hash + 栈

使用 Hash 处理现在枚举过的无法匹配的未匹配的字串的值，如 ABBA 假设我们处理到了 i = 3 那么剩下没有匹配的就会是 A ，这样我们就可以开始找到另一个 Hash 值表示 A 的字符串，因为 Hash 值是单调递增的（不考虑取模），所以如果之前有一个 Hash 值与现在的相等，那么说明，中间的这一段字符串一定就可以被消除。

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define rint register int
#define For(i, j, k) for(rint i = j; i <= k; i++)
using namespace std;

inline int read(){
  int f = 1,x = 0;
  char ch = getchar();
  while(!isdigit(ch)){
    if(ch == '-')f = -1;
    ch = getchar();
  }
  while(isdigit(ch)){
    x = (x << 1) + (x << 3) + (ch ^ 48);
    ch = getchar();
  }
  return x * f;
}
inline void print(int x){
  if(x > 9)print(x / 10);
  putchar(x % 10 + '0');
}

string a;
stack<char> s; 
ull cnt = 0;
const ull base = 1e9 + 7;
ull H[2000010];
ll ans = 0;
unordered_map<ull, ll> sum;

signed main(){
    int n = read(); cin >> a;
    a = ' ' + a;
    H[0] = 1;
    For(i, 1, n){
        H[i] = H[i - 1] * base;
    }
    sum[0] = 1;
    For(i, 1, n){
        if(!s.empty() && s.top() == a[i])
            cnt -= s.top() * H[s.size()], s.pop();
        else
            s.push(a[i]), cnt += a[i] * H[s.size()]; 
        ans += sum[cnt];
        sum[cnt]++;
    }
    cout << ans;
  return 0;
}

- Solve 2

这就与赛时想法比较像了。

运用结论，设 dp_i 表示以 i 为结尾的匹配字符串的个数。

那么肯定有以下的结论，令 last_i 表示与 a_i = a_{last_i} 的且 [last_i, i] 可以被消除的最近的下标， dp_i 的改变一定是 dp_{last_i - 1} + 1 ，如何去找到这个 last_i 呢？通过之前的思想，我们可以把大事化小，通过跳来解决 last_i \Leftarrow last_{last_i - 1} \dots 原理是什么呢，其实就是一直找回文字符串。

代码如下

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define rint register int
#define For(i, j, k) for(rint i = j; i <= k; i++)
#define down(i, j, k) for(rint i = k; i <= j; --i)
using namespace std;

inline int read(){
  int f = 1,x = 0;
  char ch = getchar();
  while(!isdigit(ch)){
    if(ch == '-')f = -1;
    ch = getchar();
  }
  while(isdigit(ch)){
    x = (x << 1) + (x << 3) + (ch ^ 48);
    ch = getchar();
  }
  return x * f;
}
inline void print(int x){
  if(x > 9)print(x / 10);
  putchar(x % 10 + '0');
}

ll to[2000010], dp[2000010], ans;

signed main(){
    int n = read();
    string a;
    cin >> a;
    a = ' ' + a;
    For(i, 1, n){
        for(int j = i - 1; j > 0; j = to[j] - 1){
            if(a[j] == a[i]){
                to[i] = j;break;
            }
        }
        if(to[i])dp[i] = dp[to[i] - 1] + 1, ans += dp[i];
    } 
    cout << ans;
  return 0;
}