CodeForces 950C Zebras【贪心】【思维】【构造】

发表于 | 更新于 | 分类于

题目大意：

给你一个01串，问其是否能拆成若干形如0101010的子串，若能，输出所有子串的0，1 的位置。

解题思路：

其实就是模拟这个选取的过程就行了，就看怎么选比较方便了。

在经过while(true)的暴力、分别存取0和1的下标来进行二分查找的不断尝(失)试(败)后，找到了一个神奇的写法。

具体操作：开上N个vector，用一个指向所有的待用存储空间的指针不断移动，遇到0就填到这个空间里然后指针向下走，遇到1了就返回到上个位置将1填进去，反复进行这个操作，$O(n)$时间内完美解决。

MyCode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int N = 200010;

char s[N];
vector<int> G[N];
int maxx, now, len;
int main()
{
    scanf("%s", s);
    len = strlen(s);

    for(int i = 0; i < len; ++i)
    {
        if(s[i] == '1')
        {
            if(now == 0)
                return puts("-1") & 0;
            G[--now].push_back(i);
        }
        else
            G[now++].push_back(i);
        maxx = max(maxx, now);
    }
    if(now != maxx) return puts("-1") & 0;

    printf("%d\n", maxx);
    for(int i = 0; i < maxx; ++i)
    {
        printf("%d", G[i].size());
        for(int j = 0; j < G[i].size(); ++j)
            printf(" %d", G[i][j] + 1);
        puts("");
    }
    return 0;
}
Donate comment here
0%