Problem Solving►CodeForces

CodeForces 949A - Zebras

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址

給你一串 0, 1 的序列，請將這個序列分成數個子序列，且子序列符合 0, 010, 01010, … ，前後都要為零。

子序列的組成不用連續，但 index 要遞增。

Solution

先解釋一下例子：

1
2
index: 1 2 3 4 5 6 7  
seq  : 0 0 1 0 1 0 0

可分成 3 個 sub-seq：(以 index 表示)

(length): indices …
3: 1 3 4 => 0 1 0
3: 2 5 6 => 0 1 0
1: 7 => 0

以一個陣列來記錄該 index 前面接的 index。(ans[a] = b => b a)
把序列掃一次，遇到 0 就去檢查前面有沒有 1，有的話就把這個 1 放到 0 前面。
也就是：
目前 index: cnt_idx
最靠近的 1 : one_idx
ans[cnt_idx] = one_idx

遇到 1 就是檢查前面有沒有 0 可以放在 1 前面。

因此我們需要邊操作 該子序列的結尾 0 和 剩餘未成子序列的 1，有點像 stack 的感覺。(vector<int> zero, one)
放進 ans 的數字，都是接在某數(idx)前，且每個子序列的結尾都會在 0。
所以我們只要去找 zero 內 0 的 idx，並去 ans 查詢其前面接的是甚麼，直到沒接東西，就完成一個子序列了。
只有自己一個的，其前面沒接東西，所以 ans[x] = 0。
e.g.

1
2
3
       0 0 1 0 1 0 0
index: 1 2 3 4 5 6 7
           2 3 4 5

zero : 1 6 7
one :

seq1: 1 (0)
seq2: 2 3 4 5 6 (01010)
seq3: 7 (0)

題外話：比賽時沒解出來，賽後看了別人的寫法覺得挺有趣的。不過也許是自己題解太少才會這麼覺得了…

Code

CF 949A
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <cstdio>
#include <vector>
#include <stack>
#define N 200005
using namespace std;

int main()
{
    char str[N];
    fgets(str + 1, N, stdin);
    vector<int> zero, one;
    int ans[N] = {}, ok = true;
    for (int i = 1; str[i] != '\n'; ++i)
    {
        if (str[i] == '0')
        {
            zero.push_back(i);
            if (!one.empty())
            {
                ans[i] = one.back();
                one.pop_back();
            }
        }
        else
        {
            if (zero.empty()) // can't find 0 before it(1)
            {
                ok = false;
                break;
            }
            else
            {
                one.push_back(i);
                ans[i] = zero.back();
                zero.pop_back();
            }
        }
    }

    if (ok && one.empty())
    {
        printf("%d\n", zero.size());
        for (int i : zero)
        {
            if (ans[i])
            {
                stack<int> s;
                s.push(i);
                while (i = ans[i])
                    s.push(i);

                printf("%d", s.size());
                while (!s.empty())
                {
                    printf(" %d", s.top());
                    s.pop();
                }
            }
            else
                printf("1 %d", i);
            putchar('\n');
        }
    }
    else
        puts("-1");

    return 0;
}