CSP-S 2023 消消乐-题解

闲话

省流：long long 模拟pair

好抽象的题，可惜考场上没做出来。感觉其实是一个挺有趣的题的。

题目描述

小 L 现在在玩一个低配版本的消消乐，该版本的游戏是一维的，一次也只能消除两 个相邻的元素。 现在，他有一个长度为 \(n\) 且仅由小写字母构成的字符串。我们称一个字符串是可消 除的，当且仅当可以对这个字符串进行若干次操作，使之成为一个空字符串。 其中每次操作可以从字符串中删除两个相邻的相同字符，操作后剩余字符串会拼接 在一起。 小 L 想知道，这个字符串的所有非空连续子串中，有多少个是可消除的。

题目分析

首先有一个很显而易见的\(O(n^2)\)的暴力

（考场上只打了这个暴力）

我们只用枚举每一个区间判断它是否可以删除即可，我们可以简单分析得知，一个字符只要能被消除，它就应该消除，留给后面的字符来消除一定不会比能消除就消除更优秀。

所以我们直接枚举每一个点作为消除的起点，用一个栈来统计，如果当前点即将入栈的字符与栈顶元素相同，那么就直接弹栈，否则将当前字符入栈。

那么我们只需要每次判断栈是否为空就可以了，如果当前栈为空，那么答案就可以累加\(1\)，否则就进行下一次操作。

关键代码

void Subtask_1(){
	S.GTop=0;
	for(int i=1;i<=n;i++){
		while(!S.Empty()) S.Pop();
		for(int j=i;j<=n;j++){
			if(S.Top()==In[j]&&!S.Empty()) S.Pop();
			else S.Push(j);
			if(S.Empty()) Ans++;
		}
	}
	printf("%lld",Ans);
}

期望得分：\(50Pts\)

然后对这个出入栈的思想进行优化

首先我们想这个题的数据范围是\(2\times 10^6\)的，那么一定可以用\(O(n)\)的做法，所以我们尝试只以\(1\)为起点，来统计答案。

思考什么情况下一段区间可以视为可消除的。如果从\(1\)开始向栈中插入元素的话，那么一段区间是可消除的，当且仅当插入这段区间前后栈中元素的状态相同。

所以得到这个结论之后，我们可以用一个Hash值来记录栈中元素的状态，然后记录每个状态的出现次数\(Time_i\)，那么答案即为:\(\sum ^{Total}_{i=1}Time_i\times (Time_i-1)/2\)，因为对于每个状态都可以两两配对，随意组合即可。而对于这个式子，更快捷的方法是在每次出现一个状态时，就将答案累加这个状态之前出现的次数。

但是因为unordered_map不能套pair，所以我用的long long把两个Hash值合在一起。（这里用双Hash是为了防止撞Hash值）

Code

/*
 * @Author: Ehundategh
 * @Date: 2023-10-23 09:27:47
 * @FilePath: \Code\LuieGu\CF1223F.cpp
 * @Description: You Steal,I kill
 */
#include <unordered_map>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 2000100
const int p=20070903;
const int Inv1=674759451;
const int Mod1=999911659;
const int Inv2=489437524;
const int Mod2=1e9+7;
using namespace std;
inline int Calc1(int a,int b){return ((a+=b)>Mod1)?a-Mod1:a;}
inline int Del1(int a,int b){return ((a-=b)<0)?a+Mod1:a;}
inline int Mul1(int a,int b){return 1ll*a*b%Mod1;}
inline int Calc2(int a,int b){return ((a+=b)>Mod2)?a-Mod2:a;}
inline int Del2(int a,int b){return ((a-=b)<0)?a+Mod2:a;}
inline int Mul2(int a,int b){return 1ll*a*b%Mod2;}
char S[MAXN];
int n;
long long Ans=0;
class Stack{
private:
    int STop=0;
    int Pos[MAXN];
    int Hash1=0,Hash2=0;
public:
    void Push(int a){
        Hash1=Mul1(p,Hash1); Hash1=Calc1(Hash1,S[a]); 
        Hash2=Mul2(p,Hash2); Hash2=Calc2(Hash2,S[a]); 
        Pos[++STop]=a;
    }
    void Pop(){
        Hash1=Del1(Hash1,S[Pos[STop]]); Hash1=Mul1(Hash1,Inv1); 
        Hash2=Del2(Hash2,S[Pos[STop]]); Hash2=Mul2(Hash2,Inv2); 
        --STop;
    }
    char Top(){return S[Pos[STop]];}
    long long Get(){return ((long long)Hash1<<32ll)+(long long)Hash2;}
}St;
unordered_map<long long,int> Map;
int main(){
    scanf("%d",&n);
    Ans=0;
    Map[0]=1;
    for(int i=1;i<=n;i++){
        if(St.Top()==S[i]) St.Pop();
        else St.Push(i);
        Ans+=Map[St.Get()];
        Map[St.Get()]++;
    }
    printf("%lld\n",Ans);
}