2021-08-26新高二一期暑假集训20

发表于

观察

难度:

思维难度: 两星

代码难度: 两星

算法:

倍增 + 树状数组

思路:

对于一个询问，从询问的点开始向上倍增，得到最近的有黑点的子树。因为修改是翻转一个棋子，所以只要单点加，区间求和就行.

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;
int n, m;
int fa[N][23];
int val[N];
int head[N], nxt[N], to[N], e_tot;
int col[N];

inline int read()
{
    int res = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        res = res * 10 + c - 48;
        c = getchar();
    }
    return res * f;
}
   

void add(int x, int y) {
    nxt[++e_tot] = head[x], head[x] = e_tot, to[e_tot] = y;
}

int lowbit(int x) {
    return x & (-x);
}

void change(int x, int v) {
    for (int i = x; i <= n; i += lowbit(i)) {
        val[i] += v;
    }
}

int query(int x, int y) {
    int res = 0;
    for (int i = y; i; i -= lowbit(i)) {
        res += val[i];
    }
    for (int i = x - 1; i; i -= lowbit(i)) {
        res -= val[i];
    }
    return res;
}

int dfn[N], tim, id[N], siz[N];

void dfs(int u) {
    dfn[u] = ++tim;
    id[tim] = u;
    siz[u] = 1;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        dfs(v);
        siz[u] += siz[v];
    }
}

int main() {
    n = read(), m = read();
    for (int i = 2; i <= n; ++i) {
        fa[i][0] = read();
        add(fa[i][0], i);
    }
    dfs(1);
    for (int k = 1; k <= 21; ++k) {
        for (int i = 1; i <= n; ++i) {
            fa[i][k] = fa[fa[i][k - 1]][k - 1];
        }
    }
    while (m--) {
        int x;
        x = read();
        if (x > 0) {
            if (!col[x]) {
                change(dfn[x], 1);
            }
            else change(dfn[x], -1);
            col[x] ^= 1;
        }
        else {
            x = -x;
            int u = x;
            if (!query(1, n)) {
                puts("0");
                continue;
            }
            else if (query(dfn[u], dfn[u] + siz[u] - 1)){
                printf("%d\n", u);
                continue;
            }
            else {
                for (int k = 21; ~k; --k) {
                    if (fa[u][k] && !query(dfn[fa[u][k]], dfn[fa[u][k]] + siz[fa[u][k]] - 1)) {
                        u = fa[u][k];
                    }
                }
                printf("%d\n", fa[u][0]);
            }
        }
    }
    return 0;
}

跳跃

难度:

思维难度 : 三星

代码难度 : 二星半

标签:

二维偏序 + 树状数组.

思路:

因为 n≤40n \leq 40 , 所以折半考虑， 分为前 n2\frac{n}{2} 栋楼和后 n2\frac{n}{2} 栋楼. 发现前后部分可以拼接起来当且仅当金币数量和 ≥K\geq K , 且前半部分最高的楼高度 ≤\leq 前半部分最高的楼高度 . 发现这是一个二维偏序问题。然后搞一下就行.

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long

using namespace std;

const int N = 50;
int n;
ll k;
int tot;
ll ans;
int h[N], g[N];
ll tmp[2100000];
int ttot;
int val[2100000];
int hei;
ll coin;

struct Pair{
    ll x;
    int y;
    bool op;
    bool operator < (const Pair A) const {
        if (x == A.x) {
            return op > A.op;
        }
        return x < A.x;
    }
}p[2100000];


bool check(int st, int _n) {
    hei = 0x3f3f3f3f, coin = 0;
    int last = 0;
    for (int i = 0; i < _n; ++i) {
        if (st >> i & 1) {
            if (h[i + 1] >= h[last]) {
                last = i + 1;
                hei = h[i + 1];
                coin += g[i + 1];
            }
            else return 0;
        }
    }
    return 1;
}

bool check2(int st, int _n) {
    hei = 0x3f3f3f3f, coin = 0;
    int last = 0;
    for (int i = 0; i < _n; ++i) {
        if (st >> i & 1) {
            if (h[i + 1 + n / 2] >= h[last]) {
                if (!last) hei = h[i + 1 + n / 2];
                coin += g[i + 1 + n / 2];
                last = i + 1 + n / 2;
            }
            else return 0;
        }
    }
    return 1;
}

int lowbit(int x) {
    return x & (-x);
}

void change(int x, int v) {
    for (int i = x; i <= tot; i += lowbit(i)) {
        val[i] += v;
    }
}

ll query(int x, int y) {
    ll res = 0;
    for (int i = y; i; i -= lowbit(i)) {
        res += val[i];
    }
    for (int i = x - 1; i; i -= lowbit(i)) {
        res -= val[i];
    }
    return res;
}

signed main() {
    scanf("%d%lld", &n, &k);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &h[i], &g[i]);
    }
    p[++tot].x = k;
    p[tot].y = 0;
    p[tot].op = 1;
    for (int st = 1; st < (1 << n / 2); ++st) {
        if (check(st, n / 2)) {
            ++tot;
            p[tot].x = k - coin;
            p[tot].y = hei;
            p[tot].op = 1;
        }
    }
    p[++tot].x = 0;
    p[tot].y = 0x3f3f3f3f;
    p[tot].op = 0;
    for (int st = 1; st < (1 << (n - n / 2)); ++st) {
        if (check2(st, n - n / 2)) {
            ++tot;
            p[tot].x = coin;
            p[tot].y = hei;
            p[tot].op = 0;
        }
    }
    for (int i = 1; i <= tot; ++i) {
        tmp[i] = p[i].x;
    }
    sort(tmp + 1, tmp + tot + 1);
    for (int i = 1; i <= tot; ++i) {
        p[i].x = lower_bound(tmp + 1, tmp + tot + 1, p[i].x) - tmp;
    }
    for (int i = 1; i <= tot; ++i) {
        tmp[i] = p[i].y;
    }
    sort(tmp + 1, tmp + tot + 1);
    for (int i = 1; i <= tot; ++i) {
        p[i].y = lower_bound(tmp + 1, tmp + tot + 1, p[i].y) - tmp;
    }
    sort(p + 1, p + tot + 1);
    for (int i = 1; i <= tot; ++i) {
        if (p[i].op == 1) {
            change(p[i].y, 1);
        }
        else {
            ans += query(1, p[i].y);
        }
    }
    cout << ans << endl;
    return 0;
}

总结

遇到 n≤40n\leq40 之类的题，考虑折半解决，然后拼起来.

树

难度:

思维难度 : 三星

代码难度 : 四星

标签:

并查集

思路:

显然问题是把 aia_i 到 bib_i 的边合并起来，最后输出 2并查集个数2^{并查集个数} .

合并可以用并查集, 然后跳边操作需要一些技巧，在合并并查集时按照两个根在树上的深度合并，把深度大的合并到深度小的上面，跳的时候直接跳到所在并查集的根所在的位置。这样每条边只会被合并 O(1)O(1) 次，

然后有可能无解，如果发现一条边既要向上又要向下就会无解。用类似 2−sat2-sat 的方法可以解决.

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;
int n, m;
int fa[N][23];
int val[N];
int head[N], nxt[N], to[N], e_tot;
int col[N];

inline int read()
{
    int res = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        res = res * 10 + c - 48;
        c = getchar();
    }
    return res * f;
}
   

void add(int x, int y) {
    nxt[++e_tot] = head[x], head[x] = e_tot, to[e_tot] = y;
}

int lowbit(int x) {
    return x & (-x);
}

void change(int x, int v) {
    for (int i = x; i <= n; i += lowbit(i)) {
        val[i] += v;
    }
}

int query(int x, int y) {
    int res = 0;
    for (int i = y; i; i -= lowbit(i)) {
        res += val[i];
    }
    for (int i = x - 1; i; i -= lowbit(i)) {
        res -= val[i];
    }
    return res;
}

int dfn[N], tim, id[N], siz[N];

void dfs(int u) {
    dfn[u] = ++tim;
    id[tim] = u;
    siz[u] = 1;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        dfs(v);
        siz[u] += siz[v];
    }
}

int main() {
    n = read(), m = read();
    for (int i = 2; i <= n; ++i) {
        fa[i][0] = read();
        add(fa[i][0], i);
    }
    dfs(1);
    for (int k = 1; k <= 21; ++k) {
        for (int i = 1; i <= n; ++i) {
            fa[i][k] = fa[fa[i][k - 1]][k - 1];
        }
    }
    while (m--) {
        int x;
        x = read();
        if (x > 0) {
            if (!col[x]) {
                change(dfn[x], 1);
            }
            else change(dfn[x], -1);
            col[x] ^= 1;
        }
        else {
            x = -x;
            int u = x;
            if (!query(1, n)) {
                puts("0");
                continue;
            }
            else if (query(dfn[u], dfn[u] + siz[u] - 1)){
                printf("%d\n", u);
                continue;
            }
            else {
                for (int k = 21; ~k; --k) {
                    if (fa[u][k] && !query(dfn[fa[u][k]], dfn[fa[u][k]] + siz[fa[u][k]] - 1)) {
                        u = fa[u][k];
                    }
                }
                printf("%d\n", fa[u][0]);
            }
        }
    }
    return 0;
}

总结

并查集的使用可以很灵活， 按深度合并可以直接跳过已经在并查集中的边。