P9753 [CSP-S 2023] 消消乐

好题，该说不说想了半天manacher结果是假的

题目链接：P9753 [CSP-S 2023] 消消乐

回归正题对于这道题我们应该怎么做呢？

难点其实是在于我们如何在 O(1) 的时间内判断该字符是否符合

于是呢我们稍稍的思考一下就可以得到一个事实：

xAAx xx AxxA......

形如这样的字符串呢一定是合法的

那么对于此题我们考虑用hash和队列来做

首先我们根据以下依据记录hash值

记当前队列里总的hash值为now

那么当进来一个字符时，我们先将它与队尾字符进行比较

如果相等，那么我们就先将now-=hash(队尾元素),并将队尾元素弹出

否则我们就将当前元素加入队尾，并将now+=hash(当前队尾元素)

最后我们看看当前now在以往出现过几次，为什么呢？？？

很好理解，如果当前的now在之前出现过，就说明它与之前使总hash值变为now的字符相等，那么要想它们相等的话，它们之间的元素一定被消掉了否则根据我们的计算的话，它们会因为未消掉的元素而不相等

因此我们的ans+=cnt(now),并令cnt(now)++

代码如下

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define int long long
const int N=2e6+10,P=131,mod=8942221889969,Mod=1e9+7;

int n;
int ans;

map<int,int> cnt;

int p[N];
char s[N];

deque<int>q;

int _hash_(int x,int len)
{
	return x*p[len]%mod;//计算hash值 
}

int now_hash(int x,int opt)
{
	//计算当前的H 
	return (opt==1)?(x-_hash_(q.back(),q.size()))
					:(x+_hash_(q.back(),q.size()));
}

void solve()
{
	int H=0;
	cnt[0]=1;
	rep(i,1,n)
	{
		//cout<<1<<endl;
		if(q.size()!=0&&q.back()==s[i]-'a'+1)
		{
			H=now_hash(H,1);
			q.pop_back();
		}
		else {
			q.push_back(s[i]-'a'+1);
			H=now_hash(H,0);
		}
		ans+=cnt[H];
		cnt[H]++;
	}
	cout<<ans;
}

signed main()
{
	//freopen("P9753_19.in","r",stdin);
	
	cin>>n;
	rep(i,1,n)cin>>s[i];
	
	p[0]=1;
	rep(i,1,n)p[i]=p[i-1]*P%mod;
	
	solve();
}