CF949A Zebras 瞎搞+set维护

题意

给你一个长度为$200000$的串,让你把这个串分为若干子序列,每个子序列必须为0,1交替出现,比如0,010,01010,等.且原串中每个字符一定属于且属于一个子序列.

比如0010100,我们可以把它分为3个子序列.

长度为3,分别为1,3,4号下标

长度为3,分别为2,5,6号下标

长度为1,分别为7号下标

否则,如果找不到就输出-1.

分析

首先答案一定是$cnt[0]-cnt[1]$个,因为那种子序列0的个数永远比1的个数多1,故多出了多少个0,就是最后答案.

我们从左往右交替找0,1就好啦,如果最后一个元素不为0,那么就无解.

那么我们怎么快速找到还没有利用的0或者1的下标呢?可以考虑用set维护下标,然后每次lower_bound求出下一个下标,这样一直做就可以了.

感觉维护那种只执行1次或者少量几次的下标的话,用set维护真的挺好的

比如以前做的补图最短路,补图强联通块计数,set维护还有哪些点没被访问过

再比如以前做的一个操作让一个数变为它的因子个数的数,用set维护哪些点还可以操作

代码

#include<cstdio>
#include<cstring>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN=2e5+7;
set<int>st0,st2;
char s[MAXN];
vector<int>G[MAXN];
int main(){
	scanf("%s",s);
	int len=strlen(s);
	int cnt[2]={0,0};
	for(int i=0;i<len;++i){
		if(s[i]=='0')st0.insert(i),cnt[0]++;
		else st2.insert(i),cnt[1]++;
	}
	if(cnt[0]-cnt[1]<=0){
		printf("-1\n");
		return 0;
	}
	int now=0;
	int q[MAXN],tot=0;
	bool hasAns=true;
	while(cnt[0]){
		int val=-1;
		tot=0;
		while(1){
			auto first=st0.lower_bound(val);
			if(first==st0.end()){
				hasAns=false;
				break;
			}
			val=*first;
	//		printf("val=%d\n",val);
			cnt[0]--;
			q[tot++]=val;

			auto second=st2.lower_bound(val);
			if(second==st2.end()){
				break;
			}
			val=*second;
			cnt[1]--;
			q[tot++]=val;
		}
		if(!hasAns)break;
		for(int i=0;i<tot;++i){
			if(i%2==0)st0.erase(q[i]);
			else st2.erase(q[i]);
			G[now].push_back(q[i]);
		}
		now++;
	}
	if(cnt[1]!=0)hasAns=false;
	if(!hasAns){
		printf("-1\n");
		return 0;
	}
	printf("%d\n",now);
	for(int i=0;i<now;++i){
		int len=G[i].size();
		printf("%d ",len);
		for(int j=0;j<len;++j){
			printf("%d ",G[i][j]+1);
		}
		printf("\n");
	}
	return 0;
}