题解：斑马,斑马(zebra)

问题描述

给定一个非空的01序列；

这个序列以 0 开始, 以 0 结束,中间 0 1 交替出现

你的任务是找到这样一个或多个子序列(可以在原序列中不连续),使得原序列中的每一个数都在你找到的子序列中出现且仅出现过一次,

并且这些子序列都是斑马(zebra)

输入格式

输入包含一个字符串s，长度不超过

输出格式

如果没有找到这样的子序列,请输出一行-1；

如果有,第一行输出一个整数n

之后n

你只需要输出你找到的一个解即可.

样例一

input

output

3
3 1 3 4
3 2 5 6
1 7


原题来源：Codeforces
翻译来源：LFYZOJ


分析： 由题可知，每个斑马串中0的数量比1的数量多1，那么字符串中1的数量减去0的差值就是子序列的数量。如果差值小于不为正数，肯定无解。那么，我们可以建立两个队列，分别用来存放下一个字符为0，即q0，下一个字符为1，即q1；再建立一个动态数组储存每个子序列及其组成数在原序列中的位置。注意，最后q0应该为空。
下面是代码：

 1 #include<iostream> 
 2 #include<cstdio>
 3 #include<queue>  
 4 #include<vector>  
 5 #include<cstring>  
 6 using namespace std;
 7 char s[200005];  
 8 int sum=0;  
 9 queue<int> q0, q1;  
10 vector<int> ans[200005];  
11 int main() {  
12     cin>>s;
13     int n=strlen(s);  
14     for(int i=0; i<n; i++){
15         s[i]-='0';  
16         if (s[i]==0) sum++;  
17         else sum--;  
18     }  
19     if(sum<=0){  
20         printf("-1");
21         return 0;  
22     }  
23     for(int i=0; i<sum; i++) 
24         q0.push(i);  
25     for(int i=0; i<n; i++){  
26         if(s[i]==0){  
27             if(q0.empty()){  
28                 printf("-1");  
29                 return 0;  
30             }  
31             int dep=q0.front(); 
32             q0.pop();  
33             q1.push(dep);  
34             ans[dep].push_back(i+1);  
35         }  
36         else{  
37             if(q1.empty()){  
38                 printf("-1");
39                 return 0;  
40             }  
41             int dep=q1.front(); 
42             q1.pop();  
43             q0.push(dep);  
44             ans[dep].push_back(i+1);  
45         }  
46     }  
47     if(!q0.empty()){  
48         printf("-1");
49         return 0;  
50     }  
51     printf("%d
",sum); 
52     for(int i=0; i<sum; i++){  
53         printf("%d ",ans[i].size()); 
54         for(int j=0; j<ans[i].size(); j++){
55             printf("%d ",ans[i][j]);
56         }
57         printf("
");
58      }  
59     return 0;  
60 }

"Hello World!"