Codeforces Round 484 题解

2018/05/21

我(文化课)又菜了。

A. Row

读错题 WA 了五次,我怕不是石乐志。

直接判一下是否有并列的 1 ,是否由连续三个 0 。

 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
#include <bits/stdc++.h>
using namespace std;

int N;
char x[2001];

int main() {
    scanf("%d", &N);
    scanf("%s", x+1);

    int flag = false;
    for(int i=1;i<=N;i++) {
        if(x[i] == '1')
            if(x[i-1] == '1' || x[i+1] == '1') flag = true;
    }

    for(int i=1;i<=N;i++) {
        if(x[i] == '0')
            if(x[i-1] == '0' && x[i+1] == '0') flag = true;
    }

    if(x[1] == '0' && x[2] == '0') flag = true;
    if(x[N] == '0' && x[N-1] == '0') flag = true;
    if(x[1] == '0' && N == 1) flag = true;

    if(flag) puts("No");
    else puts("Yes");
}

B. Bus of Characters

小学生表示,读完题就会做!

题目指出动态维护类似于最值的东西,不难想到使用堆。

 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
#include <bits/stdc++.h>
using namespace std;

#define pqty priority_queue

int N;

map<int, int> LUT;
pqty<int, vector<int>, greater<int> > Q1;
pqty<int, vector<int>, less<int> > Q2;

int main() {
    scanf("%d", &N);
    int x;
    for(int i=0;i<N;i++) {
        scanf("%d", &x);
        Q1.push(x);
        LUT[x] = i+1;
    }

    N <<= 1; getchar();
    for(int i=0;i<N;i++) {
        x = getchar(); x = (x == '1');
        if(x == 0) {
            int w = Q1.top(); Q1.pop();
            int n = LUT[w]; printf("%d ", n);
            Q2.push(w);
        } else {
            int w = Q2.top(); Q2.pop();
            int n = LUT[w]; printf("%d ", n);
        }
    }

    puts("");
}

C. Cut ‘em all!

考虑贪心,dfs 每次把自己具有偶数点的儿子剥离。

 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
#include <bits/stdc++.h>
using namespace std;
const int SIZ = 2e6 + 1007;

int N;

struct tgno {
    int v;
    tgno* n;
} POOL[SIZ<<1]; int ppos;
tgno* Head[SIZ];

void _add(int u, int v) {
    POOL[ppos].v = v;
    POOL[ppos].n = Head[u];
    Head[u] = &POOL[ppos++];
}

void addEdge(int u, int v) {
    _add(u, v), _add(v, u);
}

int num[SIZ], cnt;
void dfs(int cur, int pre = 0) {
    num[cur] = 1;
    for(tgno* i=Head[cur];i;i=i->n) {
        if(i->v != pre) {
            dfs(i->v, cur);
            if(num[i->v] & 1)
                num[cur] += num[i->v];
            else {
                cnt++;
            }
        }
    }
}

int main() {
    scanf("%d", &N);

    if(N&1) { puts("-1"); return 0; }

    int u, v;
    for(int i=1;i<N;i++) {
        scanf("%d %d", &u, &v);
        addEdge(u, v);
    }

    dfs(1);

    printf("%d\n", cnt);
}

D. Shark

第一眼是两重二分(然而并不对,因为不单调)

不妨想一下答案会是什么东西:Ai + 1,此时所有小于这个值的格子被标记,对于其他可行值,显然不如这个小。

每次答案增加的时候,恰好有一个白格子被标记,考虑一种 O(logN) 时间内维护答案的数据结构:set 维护一堆区间。

 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
#include <bits/stdc++.h>
using namespace std;
const int SIZ = 2e5 + 1007;

struct seg {
    int l, r;  // [l, r)
    friend bool operator<(const seg &a, const seg &b) {
        if(a.l != b.l) return a.l < b.l;
        else return a.r < b.r;
    }
};

int N;
int A[SIZ], S[SIZ];
map<int, int> LUT;

int cnt = 0, ans = -1;
set<seg> cur;
int bucket[SIZ];
int check = 0;

int find_left(int pos) {
    typedef set<seg>::iterator It;
    seg q{pos, pos+1};
    It i = cur.lower_bound(q);
    if(i == cur.begin()) return pos;
    --i;
    seg pre = *i;
    if(pre.r == pos) {
        cur.erase(i);
        int sel = pre.r - pre.l;
        bucket[sel]--;
        if(bucket[sel] == 0)
            check--;
        return pre.l;
    } else return pos;
}

int find_right(int pos) {
    typedef set<seg>::iterator It;
    seg q{pos, pos+1};
    It i = cur.lower_bound(q);
    if(i == cur.end()) return pos+1;
    seg pre = *i;
    if(pre.l == pos+1) {
        cur.erase(i);
        int sel = pre.r - pre.l;
        bucket[sel]--;
        if(bucket[sel] == 0)
            check--;
        return pre.r;
    } else return pos+1;
}

void upd(int k) {
    int pos = LUT[k];
    int l = find_left(pos);
    int r = find_right(pos);
    cur.insert(seg{l, r}); bucket[r - l]++;
    if(bucket[r - l] == 1) check++;

    int ccnt = cur.size();
    if(check == 1 && cnt < ccnt) { cnt = ccnt, ans = k; }
}

int main() {
    scanf("%d", &N);

    for(int i=1;i<=N;i++) {
        scanf("%d", &A[i]);
        LUT[A[i]] = i;
        S[i] = A[i];
    }
    sort(S+1, S+N+1);

    for(int i=1;i<=N;i++) upd(S[i]);

    printf("%d\n", ans+1);
}