P12935 [NERC 2019] Balls of Buma

题目大意

规则大意

如果某个颜色相同的球段由于之前的操作变长，并且其长度达到至少

3

，那么该球段的所有球都会被消除。

目的

插入一个新球使该球段的所有球都被消除，求方案总数。

思路

先压缩字符串。

CPP

for(int i=0;i<s.size();i++){		//压缩字符串
	if((s[i]!=s[i-1]&&i)||!num){	//没有上一区块或与上一区块不同色 
    	num++;
    	if(!m[s[i]]){				//没有出现过此颜色 				
			m[s[i]]=++cnt;			//颜色总数++ 
			a[num][1]=cnt;
		}else a[num][1]=m[s[i]];	//否则对应 
		t[m[s[i]]]++;
	}
	a[num][0]++;					//区块长度++ 
}

由题易得，如果要使所有球都被消除，则有且仅有一个颜色出现过奇数次，且中心区块为这个颜色，此区块即为小球插入的位置。

因为球段必须由于之前的操作变长，所以左右两边颜色对称分布，故有且仅有一个颜色出现过奇数次。

详解见代码。

完整代码

CPP

#include<bits/stdc++.h>
using namespace std;
map<char,int> m;			//字符对应颜色 
string s;
int cnt=0;					//颜色总数 
int num=0;					//共有区块总数 
int a[300001][2]={};		//区块信息 
int t[300001]={};			//桶,各颜色区块数目 eg:AABAA  A:2,B:1 
bool se(int l,int r){								//是否能全部消除 
	while(l!=0&&r!=num+1){							//如果没有到边界 
		if(a[l][1]!=a[r][1]||a[l][0]+a[r][0]<=2){	//不同色(包含不变长),或小于3 
			return 0;
		}
		l--; 
		r++;
	}
	return 1; 
}
int main(){
	cin>>s;
	for(int i=0;i<s.size();i++){		//压缩字符串
		if((s[i]!=s[i-1]&&i)||!num){	//没有上一区块或与上一区块不同色 
			num++;
			if(!m[s[i]]){				//没有出现过此颜色 				
				m[s[i]]=++cnt;			//颜色总数++ 
				a[num][1]=cnt;
			}else a[num][1]=m[s[i]];	//否则对应 
			t[m[s[i]]]++;
		}
		a[num][0]++;					//区块长度++ 
	}
	int f=0;				//出现奇数次的颜色 
	for(int i=1;i<=cnt;i++){
		if(t[i]%2==1){
			if(f){			//如果有两种颜色 
				cout<<0;
				return 0;
			}	
			f=i;			//记录 
		}
	}
	int mid;
	if(num%2==0){
		cout<<0;
		return 0;
	}else mid=num/2+1;
	if(f&&a[mid][1]==f&&a[mid][0]>=2&&se(mid-1,mid+1)) cout<<a[mid][0]+1;	//颜色出现奇数次且能全消 
	else cout<<0;
	return 0;
}

题解：P12935 [NERC 2019] Balls of Buma

文章操作