题
OvO http://codeforces.com/contest/909/problem/D
CF 455 div2 D
CF 909D
解
算出模拟的复杂度之后就是一个很水的模拟题
把字符串按照类似于行程编码的方式来表示，例如把 aaaabbccc 表示成 [4*a] [2*b] [3*c] 这样的形式（[4*a] 这个用一个结构体表示）
接下去就可以开心地敲模拟了，
例如对于 [5*a] [4*b] [2*c] [4*b] 这样一个表，
运行一次之后就变成了 [4*a] [2*b] [0*c] [3*b]
然后进行压缩 变成 [4*a] [5*b]
重点是复杂度的计算，每当你进行一次 O(1) 的操作（遍历数组，删除元素）时候，元素的总量（按 aabbc 是 个元素这样算）也会减1，所以总的复杂度是 O(n) 的，并不会超时
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm> using namespace std; const int M=1e6+44; struct Node
{
int val,num;
} q[M]; int lq;
char str[M]; void cps()
{
int k=lq;
lq=0;
for(int i=1;i<=k;i++)
if(q[i].num>0)
{
if(q[i].val==q[lq].val)
q[lq].num+=q[i].num;
else
q[++lq]=q[i];
}
} void solve()
{
int ans=0;
while(lq>1)
{
ans++;
for(int i=2;i<lq;i++)
q[i].num-=2;
q[1].num--,q[lq].num--;
cps();
}
printf("%d\n",ans);
} int main()
{
scanf("%s",str+1);
lq=strlen(str+1);
q[0].val=-1;
for(int i=1;i<=lq;i++)
q[i].val=str[i]-'a',q[i].num=1;
cps();
solve();
return 0;
}