题目链接：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 <cstdio> 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 ",ans); } return 0; }
（写得丑勿喷