CodeForces 949A Zebras

题目大意

将给定字符串分割成若干子序列（子序列：允许不相邻但按先后顺序选取若干字符构成的字符串），这些子序列要满足由01串构成且开始和结束字符必须为0。很显然每个字符只能出现在一个子序列中。 先输出你构造出的子序列的个数； 下面输出你构造的子序列，第一个数为子序列长度，后面跟着这个子序列每个字符对应于原字符串中的索引（从1开始），每行对应一个构造的子序列。 对输出的唯一限制是要求输出的字符索引为升序。

题解

思路1：大佬思路，对应代码1： 首先必然得存住答案才行，因此使用二维vector，ans[i]就代表第i个子序列。 遇到0我们就就将0加入到当前的ans[cnt]中，并且++cnt；遇到1就--cnt，将1加入到当前的ans[cnt]中。总而言之，遇到0向cnt增加的ans中插入，遇到1向cnt减小的ans中插入。 每次遇到1说明cnt要减小了，那我们就保存一下最大的cnt，表示构造的子序列的全部个数，但是如果最后遍历完字符串后的cnt与保存的最大值不一致就说明至少存在一个（ans中保存的）子序列的最后一元素为1，无法以0结尾。 至于为什么，你可以模拟一个过程试试，很容易理解的。 稍微举两种极端的情况：

1. 最后结尾的0超级多，那么cnt会一直自加，显然最后cnt就是cnt的最大值。此时必然都覆盖住了。
2. 最后没有0，即原字符串以1结尾，必然无法构造出答案，此时肯定存在至少一个（ans中保存的）子序列的结尾为1，也说明ans[cnt]上次为这个子序列是将末尾添加了个1，之后便没来过了，即’cnt < max(cnt)’，无解。

当然，我们不能忽略当cnt减到0的情况啊，1太多了cnt减到0也是无解。

思路2：我的思路，含思考过程，对应代码2： 先声明我看了上面大佬的题解。 第一个思考阶段： 首先我试着思考什么时候会输出-1。 原字符串第一个或最后一个字符为1是一定不行的； 片面思考过后就觉得，可以先将连续的0或1划分为一段，只要保证连续的0的个数大于等于其相邻的两段的连续的1的个数的最大值即可，00101100并非无解，但是按我的方法判断就是无解了。 保存的话，我就用普通数组保存的，因为我没看到要先输出总的子序列个数，所以构成一个子序列就直接输出了，最后才发现是错的。 构造方法也存在问题，在这就不细说错误思路了。

第二个思考过程： 上面判断无解的方式错了，但我觉得这个题应该是可以先特判出无解的情况的（有些题直接判无解是比较难的） 思考了一会理解构造的本质了，可以理解为遇到一个1就是对前面0的消耗，因此遇到1我们要判断一下是否还剩下未被消耗的0，只有有0才能让1构成子序列。同时也要从后向前进行判断。 二维vector无疑了，现在的思路是每次遇到1插入第一个末尾为0的子序列中（对应的ans索引小者为第一个，后同），遇到0插入到第一个末尾为1的子序列中。 但是如何保存和更新“第一个末尾为0的子序列”和“第一个末尾为1的子序列”对应的索引呢？保存好说，那假如要是找到了，需要将原索引更新成新的第一个索引，怎么更新？遍历？疯了吧。 失败告终，看了大佬的题解。

第三个思考过程： 大佬的“蛇形插入法”（我真是起名鬼才）完美的解决了这个问题！ （我觉得这是个很好的思路，值得学习！） 因此，特判无解就采用了我自己的方式，而保存和输出正解用了大佬的方式。

代码1

#include
#include
#include
#include
#include
using namespace std;
const int maxn = 200000 + 5;
char str[maxn];
vector G[maxn];
inline void fail(){ printf("-1");  exit(0); }
int main()
{
    scanf("%s", str);
    int n = strlen(str), cnt = 0, k = 0;
    for(int i = 0;i = cnt) fail();
    printf("%d\n", cnt);
    for(int i = 0;i str;
    int n = str.length();
    str = '.' + str;
    
    // -1:
    if(str[1] == '1' || str[n] == '1') { puts("-1"); return 0; }
    
    for(int i = 1;i