CF1800D 题解

虽然不同的难以统计，但是统计相同的却很简单。

由于每次删除相邻两个字符，因此我们考虑连续 \(4\) 的情况。

s1s2s3s4 考虑删除 s1s2 和删除 s2s3 的区别。

删除后变成 s3s4 和 s1s4 因此，不同的情况当且仅当 \(s_{i} = s_{i+2}\)。

并且显然一共的方案只有 \(n - 1\) 种。

所以用 \(n - 1\) 减去统计的答案即可。

#include<bits/stdc++.h>
using namespace std;
int T;
void work(){
    string s;
    int n;
    cin>>n;
    cin>>s;
    int sum=0;
    for(int i=0;i+2<s.size();i++){
    	if(s[i]==s[i+2]) sum++;
	}
	cout<<s.size()-sum-1<<'\n';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    cin>>T;
    while(T--) work(); 
}