【CodeForces - 950C】Zebras

Description

题目地址： Codeforces

题意：给你一串只含01的字符串，判断能否将字符串分为k个子序列，使得子序列满足以下条件：

1. 开头和结尾都是0
2. 相邻的2个数是01或者10

如0, 010, 01010 是合法的，1, 0110, 0101不合法

要求输出方案

（k可以为任意正整数，评测用SPJ）

Solution

我们发现，0可以单独为一组，那么只要匹配完所有的1剩下的0全单独算就行了

对于方案可以用vector储存，关键在于如何划分子序列

开一个指针变量p和一个方案数cnt，p指向一个序列，且保证当前p序列的最后面是0

现在依次考虑每个数字

如果当前数字是0并且p==cnt那么直接新开一个序列，否则把这个0放到p+1的序列中,且++p，这里因为p<cnt所以p+1的序列中必定结尾为1

如果数字是1就把这个1直接放在当前p的序列中，然后p--，这里保证当前序列结尾是0，且p-1的序列结尾是0

简单来说，保证结尾为1的序列全在p的后面，前面（包括p）的序列结尾都是0

方法挺巧妙的，时间复杂度为O(n)

Code

#include <cstdio>
#include <vector>
#include <ctype.h>
using namespace std;

vector<int> Ans[];
int p,cnt,n=;

int main(){
    for(char ch=getchar();isdigit(ch);ch=getchar(),n++)
        if(ch=='1'){
            if(!p){printf("-1\n");return ;}//1过多的情况
            Ans[p--].push_back(n);
        }else if(p==cnt) Ans[p=++cnt].push_back(n);
        else Ans[++p].push_back(n);
    if(p<cnt){printf("-1\n");return ;}//0过多的情况
    printf("%d\n",cnt);
    for(int i=;i<=cnt;++i){
        printf("%d ",Ans[i].size());
        for(int j=;j<Ans[i].size();++j)
            printf("%d ",Ans[i][j]);
        printf("\n");
    }
    return ;
}