B. Balls of Buma

发布于 2020-10-11  320 次阅读




Balls of Buma

Balph is learning to play a game called Buma. In this game, he is given a row of colored balls. He has to choose the color of one new ball and the place to insert it (between two balls, or to the left of all the balls, or to the right of all the balls).

When the ball is inserted the following happens repeatedly: if some segment of balls of the same color became longer as a result of a previous action and its length became at least 3, then all the balls of this segment are eliminated.

Consider, for example, a row of balls ‘AAABBBWWBB’. Suppose Balph chooses a ball of color ‘W’ and the place to insert it after the sixth ball, i. e. to the left of the two 'W’s. After Balph inserts this ball, the balls of color ‘W’ are eliminated, since this segment was made longer and has length 3 now, so the row becomes ‘AAABBBBB’. The balls of color ‘B’ are eliminated now, because the segment of balls of color ‘B’ became longer and has length 5 now. Thus, the row becomes ‘AAA’. However, none of the balls are eliminated now, because there is no elongated segment.

Help Balph count the number of possible ways to choose a color of a new ball and a place to insert it that leads to the elimination of all the balls.

Input
The only line contains a non-empty string of uppercase English letters of length at most 3⋅105. Each letter represents a ball with the corresponding color.

Output
Output the number of ways to choose a color and a position of a new ball in order to eliminate all the balls.

Examples
input
BBWWBB

output
3

input
BWWB

output
0

input
BBWBB

output
0

input
OOOWWW

output
0

input
WWWOOOOOOWWW

output
7

题意:本题题意像祖玛球游戏一样,往中间一个字符插入一个相同的字符后,当相同字符大于三个,将合并并消除,同时两端的球往中间合并,当合并后相同球超过三个,又进行合并消除,直到把所有球合并消除完,求这个初始球插入的位置有多少种。
思路:其实只需要从左向右将不同种类的球以及其数量记录下来,然后,首位对比相加,若字符相等且其累加和相加大于3,则代表该球能够被合并且消除。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Node
{
	ll a;
	char c;
}D[3000005];
int main() {
	string s;
	cin >> s;
	ll ii=0,cnt=1;
	ll i;
	D[ii].c=s[0];
	for(i=1;i<=s.size();i++)
	{
		if(s[i]==D[ii].c)
			cnt++;
		else
		{
			D[ii].a=cnt;
			ii++;
			D[ii].c=s[i];
			cnt=1;
		}
	}
	int flag=0;
	ll x=0,y=ii-1;
	while(1)
	{
		if(x==y)
			break;
		if((y-x)==1)
			break;
		if(D[x].c!=D[y].c)
		{
			flag=1;
			break;
		}
		else 
		{
			if(D[x].a+D[y].a<3)
			{
				flag=1;
				break;
			}
		}
		x++;
		y--;
			
	}
//	cout<<x<<" "<<y<<endl;
	if(flag==1)
		cout<<0<<endl;
	else
	{
		if(x==y)
			if(D[x].a>=2)
				cout<<D[x].a+1<<endl;
			else
				cout<<0<<endl;
		else
		{
			cout<<0<<endl;
		}
	}

}