比赛链接：传送门

Summary

懒得吐槽学而思和CF的网络问题了，除了D题差一点点调出来之外，没有FST也没有掉分还是感到非常庆幸的 反正这场比赛是各种不顺，希望下一场能打的好一点

Problems

C. Zebras

Description

定义一个01串为斑马：以0开头，01交替出现并以0结尾 问能否将给定的01串分成若干个斑马，并输出方案

Solution

考虑贪心，开两个栈（或者队列也行），分别储存0和1。 如果当前元素为0，且1的栈不为空，则取出1栈栈顶元素； 如果当前元素为1，且0的栈不为空，则取出0栈的栈顶元素，如果0的栈为空，则无解。 最后再判一下1栈是否是空的即可

Code

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>

using namespace std;

const int Maxn = 200000 + 10;

char S[Maxn];

int Next[Maxn];
int N;

struct node
{
    int x, y;
};

stack <node> S1, S2;
int Vis[Maxn];

int main()
{
#ifdef hk_cnyali
    freopen("C.in", "r", stdin);
    freopen("C.out", "w", stdout);
#endif

    scanf("%s", S + 1);
    N = strlen(S + 1);
    for (int i = 1; i <= N; ++i)
    {
        int x = S[i] - '0';
        if (!x)
        {
            S1.push((node){x, i});
            if (S2.empty()) continue;
            int tmp = S2.top().y;
            S2.pop();
            Next[tmp] = i;
        }
        else 
        {
            if (S1.empty())
            {
                cout<<-1<<endl;
                return 0;
            }
            S2.push((node){x, i});
            int tmp = S1.top().y;
            S1.pop();
            Next[tmp] = i;
        }
    }

    if (!S2.empty())
    {
        cout<<-1<<endl;
        return 0;
    }

    int Ans = 0;
    for (int i = 1; i <= N; ++i)
    {
        if (Vis[i]) continue;
        ++Ans;
        int cnt = 0, tmp = i;
        while (tmp)
        {
            Vis[tmp] = 1;
            tmp = Next[tmp];
        }
    }
    cout<<Ans<<endl;

    memset (Vis, 0, sizeof (Vis));
    for (int i = 1; i <= N; ++i)
    {
        if (Vis[i]) continue;
        int cnt = 0, tmp = i;
        while (tmp)
            cnt ++, tmp = Next[tmp];
        cout<<cnt<<" ";
        tmp = i;
        while (tmp)
        {
            cout<<tmp<<" ";
            Vis[tmp] = 1;
            tmp = Next[tmp];
        }
        cout<<endl;
    }
    return 0;
}

D. A Leapfrog in the Array

Description

懒得说了

Solution

通过模拟打表找规律我们可以发现奇数位上的数都不会动， 偶数位上的数如果往前还原一步的话就能发现它们是连续的，并且依旧是保持着奇数为不动，偶数位继续向前还原的规律 然后就能通过不断递归求出答案

Code

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
#include <bits/stdc++.h>
#define int long long

using namespace std;

int N, M;

inline int Solve (int len, int x, int pos)
{
    if ((len + pos) == 2 * (N - 1)) return 2 * N - 1;
    if ((len + pos) & 1) return len + pos;
    //if (!(len & 1)) return Solve (len + x, x / 2, pos / 2);
    //return Solve (len + x, x / 2, pos / 2 + 1);
    if (!(len & 1))
        return Solve (len + x, x / 2, pos / 2);
    else 
    {
        if (!(x & 1))
            return Solve (len + x, x / 2, pos / 2 + 1);
        else return Solve (len + x, x / 2 + 1, pos / 2 + 1);
    }
}

main()
{
#ifdef hk_cnyali
    freopen("D.in", "r", stdin);
    freopen("D.out", "w", stdout);
#endif
    scanf("%lld%lld", &N, &M);
    for (int i = 1; i <= M; ++i)
    {
        int x;
        scanf("%lld", &x);
        printf("%lld\n", (Solve(0, N, x) + 1) / 2);
    }
    return 0;
}