题目链接: Colorful Points
题意:
给出一段字符串(长度最大为1e6),每次操作可以删除字符串中所有相邻字符与其不同的字符。例如:aabcaa 删除一次就变成了aa,就无法再删除了。题目要求所给出的字符串要操作几次后才无法操作。
题解:
可以把整个字符串化简为相邻字符都不同的串,把每个位置字符的个数记录下来,比如aaaabbbbccccdddd -> [4*a][4*b][4*c][4*d]。然后暴力求。@。@这题比我想象中的也暴力太多了,妈耶,刷新了我对D题的认知。
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6+;
const int MOD = 1e9+;
char vec[MAX_N];
int res[MAX_N];
char tran[MAX_N];
int main()
{
int N,M,T;
while(~scanf("%s",vec))
{
memset(res,,sizeof(res));
int len = strlen(vec);
int pos = ;
res[] = ;
char pre = vec[];
tran[pos] = pre;
for(int i=;i<len;i++)
{
if(vec[i] == pre) res[pos] ++;
else
{
res[++pos] = ;
pre = vec[i];
tran[pos] = pre;
}
} int num = pos + ;
int ans = ;
while(num > )
{
res[] -= ;
res[num-] -= ;
for(int i=;i<num-;i++)
{
res[i] -= ;
}
int t = ;
for(int i=;i<num;i++)
{
if(res[i]>)
{
if(t> && tran[t-] == tran[i])
{
res[t-] += res[i];
}
else
{
res[t] = res[i];
tran[t++] = tran[i];
}
}
}
num = t;
ans ++;
}
cout<<ans<<endl;
}
return ;
}