CF1430D.StringDeletion（div2）

题目链接：http://codeforces.com/contest/1430/problem/D

题意：有一个长度为n(n<=2*10^5)的01字符串，每轮操作有两步：

　　　第一步是删去字符串中任意一个字符；

　　　第二步是删去字符串中的相同前缀串（例如：1100100 删去前两个1）；

　　　求最多可以进行几轮。

思路：首先我们可以很容易的知道删去前后有一个（或两个）与其相同的字符是最优的（且不为第一个字符），因为此时不会使第二步操作删掉的字符增加

　　　所以我们就想到了贪心，每轮操作都遍历一遍找到满足要求的字符（特殊的，若无满足要求的字符则删掉第一个字符），用双向指针维护前后的字符位置

　　　可是！！！此时复杂度为n^2，无了

　　　那我们考虑是否可以优化以上的方法-----

　　　很容易可以发现删去一个字符时，只会改变前一个和后一个字符的性质（改变他们是否满足要求），那么我们下一轮操作可以从前一个字符开始继续往下找

　　　需要注意的是一定要从没被操作2删去的字符开始找，查找操作1的复杂度为O(n)，操作二复杂度为O(n)，因此总复杂度为O(n)

代码：

#include
int n,T,pre[200100],nxt[200100];
char a[200100];
bool vis[200100];
void init()
{
for(int i=1;i<=n;i++) vis[i]=0;
for(int i=1;i<=n;i++)
{
pre[i]=i-1;
nxt[i]=i+1;
}
return;
}
int main()
{
int ans,x,cnt,be,k;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n); cnt=n;
scanf(" %s",a+1);
ans=0; init(); x=2; a[0]=a[n+1]='z'; be=1;
while(cnt)
{
ans++;
while((vis[x]||x==be)&&x<=n) x=nxt[x];
while(x<=n) {if (a[pre[x]]==a[x]||a[nxt[x]]==a[x]) break; x=nxt[x];}
if (x<=n)
{
vis[x]=1; cnt--; nxt[pre[x]]=nxt[x]; pre[nxt[x]]=pre[x];
if (pre[x]>be) x=pre[x];
else x=nxt[x];
}
else {vis[be]=1; cnt--; pre[nxt[be]]=0; be=nxt[be];}
if (!cnt) break;
k=a[be];
while(a[be]==k&&be<=n) {vis[be]=1; cnt--; pre[nxt[be]]=0; be=nxt[be];}
}
printf("%d\n",ans);
}
return 0;
}

（写得丑勿喷