CSES Adcanced Techniques

更新 ing（但是会优先补 vp ICPC 没做出来的题）

Meet in the Middle#

对半分，两半分别暴力所有情况。最后排序，遍历一边的，用二分或者双指针维护另一边的合法的组合的范围。

1
#include <iostream>
2
#include <algorithm>
3

4
using namespace std;
5
typedef long long LL;
6
const int N = 40;
7
int a[N], lb, lc;
8
LL b[1 << 20], c[1 << 20];
9

10
int main() {
11
    ios::sync_with_stdio(0);
12
    cin.tie(0), cout.tie(0);
13
    int n, x;
14
    cin >> n >> x;
15
    for (int i = 0; i < n; ++i) cin >> a[i];
16
    int mid = n >> 1;
17
    for (int i = 0; i < (1 << mid); ++i) {
18
        LL s = 0;
19
        for (int j = 0; j < mid; ++j) {
20
            if (i >> j & 1) s += a[j];
21
        }
22
        b[lb++] = s;
23
    }
24
    for (int i = 0; i < (1 << n - mid); ++i) {
25
        LL s = 0;
26
        for (int j = 0; j < n - mid; ++j) {
27
            if (i >> j & 1) s += a[j + mid];
28
        }
29
        c[lc++] = s;
30
    }
31
    sort(b, b + lb), sort(c, c + lc);
32
    LL res = 0;
33
    for (int i = 0; i < lb; ++i) {
34
        res += upper_bound(c, c + lc, x - b[i]) - lower_bound(c, c + lc, x - b[i]);
35
    }
36
    cout << res << endl;
37
    return 0;
38
}

Hamming Distance#

直接暴力就行了。

1
#include <iostream>
2
#include <bitset>
3

4
using namespace std;
5

6
const int N = 20010;
7
bitset<31> a[N];
8

9
int main() {
10
    ios::sync_with_stdio(0);
11
    cin.tie(0), cout.tie(0);
12
    int n, k;
13
    cin >> n >> k;
14
    int res = 40;
15
    for (int i = 1; i <= n; ++i) {
16
        string s;
17
        int t = 0;
18
        cin >> s;
19
        for (char c : s) t = (t << 1) + (c == '1');
20
        a[i] = t;
21
    }
22
    for (int i = 1; i <= n; ++i) {
23
        for (int j = i + 1; j <= n; ++j) {
24
            res = min(res, (int)(a[i] ^ a[j]).count());
25
        }
26
    }
27
    cout << res << endl;
28
    return 0;
29
}

Corner Subgrid Check#

卡不过去😭

Corner Subgrid Count#

思路应该很显然，开 bitset 存位置，暴力枚举所有行号组合两个二进制串与一下，设 1 的数量为 c，对答案贡献 $\binom{c}{2}$ .然后就是怎么卡常都过不去，最后看别人开了个 Ofast 优化过去了，然后我也开，993ms 极限跑过去了。

1
#pragma GCC optimize("Ofast")
2
#include <iostream>
3
#include <bitset>
4
#include <cstring>
5

6
using namespace std;
7

8
typedef long long LL;
9
const int N = 3010;
10
char a[N][N];
11
bitset<N> b[N];
12

13
int main() {
14
    ios::sync_with_stdio(0);
15
    cin.tie(0), cout.tie(0);
16
    int n;
17
    cin >> n;
18
    for (int i = 1; i <= n; ++i) {
19
        cin >> (a[i] + 1);
20
        for (int j = 1; j <= n; ++j) {
21
            b[i][j] = a[i][j] == '1';
22
        }
23
    }
24
    LL res = 0;
25
    for (int i = 1; i <= n; ++i) {
26
        for (int j = i + 1; j <= n; ++j) {
27
            LL c = (b[i] & b[j]).count();
28
            res += c * (c - 1) / 2;
29
        }
30
    }
31
    cout << res << endl;
32
    return 0;
33
}

Reachable Nodes#

用 bitset 记录能到的点，用记搜做反拓扑序 dp。

1
#include <iostream>
2
#include <bitset>
3

4
using namespace std;
5

6
const int N = 50010, M = 100010;
7
bitset<N> f[N];
8
bool v[N];
9
int ver[M], ne[M], head[N], tot;
10

11
void add(int x, int y) {
12
    ver[++tot] = y;
13
    ne[tot] = head[x];
14
    head[x] = tot;
15
}
16

17
void dfs(int x) {
18
    if (v[x]) return;
19
    v[x] = true;
20
    f[x][x] = true;
21
    for (int i = head[x]; i; i = ne[i]) {
22
        int y = ver[i];
23
        dfs(y);
24
        f[x] |= f[y];
25
    }
26
}
27

28
int main() {
29
    ios::sync_with_stdio(0);
30
    cin.tie(0), cout.tie(0);
31
    int n, m;
32
    cin >> n >> m;
33
    for (int i = 1; i <= m; ++i) {
34
        int x, y;
35
        cin >> x >> y;
36
        add(x, y);
37
    }
38
    for (int i = 1; i <= n; ++i) {
39
        if (!v[i]) dfs(i);
40
        cout << f[i].count() << ' ';
41
    }
42
    cout << endl;
43
    return 0;
44
}

Reachability Queries#

上一道的增强版。强联通分量缩点之后在反拓扑序 DP 即可。

1
#include <iostream>
2
#include <bitset>
3

4
using namespace std;
5

6
const int N = 50010, M = 200010;
7
int h1[N], h2[N], ver[M], ne[M], tot;
8
int st[N], tp;
9
int dfn[N], low[N], scc_id[N], scc_cnt, t;
10
bool ins[N];
11
bool vis[N];
12
bitset<N> f[N];
13

14
void add(int *head, int x, int y) {
15
    ver[++tot] = y;
16
    ne[tot] = head[x];
17
    head[x] = tot;
18
}
19

20
void tarjan(int x) {
21
    dfn[x] = low[x] = ++t;
22
    st[++tp] = x;
23
    ins[x] = true;
24
    for (int i = h1[x]; i; i = ne[i]) {
25
        int y = ver[i];
26
        if(!dfn[y]) {
27
            tarjan(y);
28
            low[x] = min(low[x], low[y]);
29
        }
30
        else if (ins[y]) low[x] = min(low[x], dfn[y]);
31
    }
32
    if (dfn[x] == low[x]) {
33
        int y;
34
        scc_cnt++;
35
        do {
36
            y = st[tp--];
37
            ins[y] = false;
38
            scc_id[y] = scc_cnt;
39
        } while (y != x);
40
    }
41
}
42

43

44
void dfs(int x) {
45
    if (vis[x]) return;
46
    vis[x] = true;
47
    f[x][x] = true;
48
    for (int i = h2[x]; i; i = ne[i]) {
49
        int y = ver[i];
50
        dfs(y);
51
        f[x] |= f[y];
52
    }
53
}
54

55
int main() {
56
    ios::sync_with_stdio(0);
57
    cin.tie(0), cout.tie(0);
58
    int n, m, q;
59
    cin >> n >> m >> q;
60
    for (int i = 1; i <= m; ++i) {
61
        int x, y;
62
        cin >> x >> y;
63
        add(h1, x, y);
64
    }
65
    for (int i = 1; i <= n; ++i) {
66
        if (!dfn[i]) tarjan(i);
67
    }
68
    for (int i = 1; i <= n; ++i) {
69
        for (int j = h1[i]; j; j = ne[j]) {
70
            int y = ver[j];
71
            if (scc_id[i] != scc_id[y]) {
72
                add(h2, scc_id[i], scc_id[y]);
73
            }
74
        }
75
    }
76
    while (q--) {
77
        int a, b;
78
        cin >> a >> b;
79
        a = scc_id[a], b = scc_id[b];
80
        dfs(a);
81
        cout << (f[a][b] ? "YES" : "NO") << endl;
82
    }
83
    return 0;
84
}

Cut and Paste#

可以用 FHQ-Treap（现学的）。这是一种基于分裂和合并的 Treap，感觉写起来反而还比一般的 Treap 好写。

1
#include <iostream>
2
#include <random>
3
#include <ctime>
4

5
using namespace std;
6

7
const int N = 200010;
8
mt19937 rnd(time(nullptr));
9

10
struct Node {
11
    int ls, rs;
12
    int cnt;
13
    char c;
14
    unsigned pri;
15
} tr[N];
16
int tot, rt;
17

18
void pushup(int u) {
19
    tr[u].cnt = tr[tr[u].ls].cnt + tr[tr[u].rs].cnt + 1;
20
}
21

22
void split(int u, int k, int &x, int &y) {
23
    if (!u) {
24
        x = y = 0;
25
        return;
26
    }
27
    int lsiz = tr[tr[u].ls].cnt + 1;
28
    if (lsiz <= k) x = u, split(tr[u].rs, k - lsiz, tr[u].rs, y);
29
    else y = u, split(tr[u].ls, k, x, tr[u].ls);
30
    pushup(u);
31
}
32

33
int merge(int u, int v) {
34
    if (!u || !v) return u | v;
35
    if (tr[u].pri < tr[v].pri) {
36
        tr[u].rs = merge(tr[u].rs, v);
37
        pushup(u);
38
        return u;
39
    }
40
    else {
41
        tr[v].ls = merge(u, tr[v].ls);
42
        pushup(v);
43
        return v;
44
    }
45
}
46

47
int newNode(char c) {
48
    tr[++tot] = {0, 0, 1, c, rnd()};
49
    return tot;
50
}
51

52
void print(int u) {
53
    if (!u) return;
54
    else {
55
        print(tr[u].ls);
56
        cout << tr[u].c;
57
        print(tr[u].rs);
58
    }
59
}
60

61
int main() {
62
    ios::sync_with_stdio(0);
63
    cin.tie(0), cout.tie(0);
64
    int n, q;
65
    string s;
66
    cin >> n >> q >> s;
67
    for (char c : s) rt = merge(rt, newNode(c));
68
    while (q--) {
69
        int l, r;
70
        cin >> l >> r;
71
        int lt, mt, rrt;
72
        split(rt, l - 1, lt, mt);
73
        split(mt, r - l + 1, mt, rrt);
74
        rt = merge(lt, rrt);
75
        rt = merge(rt, mt);
76
    }
77
    print(rt);
78
    cout << endl;
79
    return 0;
80
}

Substring Reversals#

仍然可以用 FHQ-Treap，这次的区间反转需要打懒标记。

1
#include <iostream>
2
#include <random>
3
#include <ctime>
4

5
using namespace std;
6

7
const int N = 200010;
8
mt19937 rnd(time(nullptr));
9

10
struct Node {
11
    int ls, rs;
12
    int cnt;
13
    char c;
14
    bool tag;
15
    unsigned pri;
16
} tr[N];
17
int tot, rt;
18

19
void pushup(int u) {
20
    tr[u].cnt = tr[tr[u].ls].cnt + tr[tr[u].rs].cnt + 1;
21
}
22

23
void pushdown(int u) {
24
    if (tr[u].tag) {
25
        if (tr[u].ls) swap(tr[tr[u].ls].ls, tr[tr[u].ls].rs), tr[tr[u].ls].tag ^= 1;
26
        if (tr[u].rs) swap(tr[tr[u].rs].ls, tr[tr[u].rs].rs), tr[tr[u].rs].tag ^= 1;
27
        tr[u].tag = 0;
28
    }
29
}
30

31
void split(int u, int k, int &x, int &y) {
32
    if (!u) {
33
        x = y = 0;
34
        return;
35
    }
36
    pushdown(u);
37
    int lsiz = tr[tr[u].ls].cnt + 1;
38
    if (lsiz <= k) x = u, split(tr[u].rs, k - lsiz, tr[u].rs, y);
39
    else y = u, split(tr[u].ls, k, x, tr[u].ls);
40
    pushup(u);
41
}
42

43
int merge(int u, int v) {
44
    if (!u || !v) return u | v;
45
    if (tr[u].pri < tr[v].pri) {
46
        pushdown(u);
47
        tr[u].rs = merge(tr[u].rs, v);
48
        pushup(u);
49
        return u;
50
    }
51
    else {
52
        pushdown(v);
53
        tr[v].ls = merge(u, tr[v].ls);
54
        pushup(v);
55
        return v;
56
    }
57
}
58

59
int newNode(char c) {
60
    tr[++tot] = {0, 0, 1, c, 0, rnd()};
61
    return tot;
62
}
63

64
void print(int u) {
65
    if (!u) return;
66
    else {
67
        pushdown(u);
68
        print(tr[u].ls);
69
        cout << tr[u].c;
70
        print(tr[u].rs);
71
    }
72
}
73

74
int main() {
75
    ios::sync_with_stdio(0);
76
    cin.tie(0), cout.tie(0);
77
    int n, q;
78
    string s;
79
    cin >> n >> q >> s;
80
    for (char c : s) rt = merge(rt, newNode(c));
81
    while (q--) {
82
        int l, r;
83
        cin >> l >> r;
84
        int lt, mt, rrt;
85
        split(rt, l - 1, lt, mt);
86
        split(mt, r - l + 1, mt, rrt);
87
        swap(tr[mt].ls, tr[mt].rs);
88
        tr[mt].tag ^= 1;
89
        rt = merge(lt, mt);
90
        rt = merge(rt, rrt);
91
    }
92
    print(rt);
93
    cout << endl;
94
    return 0;
95
}

Reversals and Sums#

同上，多维护一个 sum，pushup 的时候更新即可。

1
#include <iostream>
2
#include <random>
3
#include <ctime>
4

5
using namespace std;
6
typedef long long LL;
7
const int N = 200010;
8
mt19937 rnd(time(nullptr));
9

10
struct Node {
11
    int ls, rs;
12
    int cnt;
13
    LL val, s;
14
    bool tag;
15
    unsigned pri;
16
} tr[N];
17
int tot, rt;
18

19
void pushup(int u) {
20
    tr[u].cnt = tr[tr[u].ls].cnt + tr[tr[u].rs].cnt + 1;
21
    tr[u].s = tr[tr[u].ls].s + tr[tr[u].rs].s + tr[u].val;
22
}
23

24
void pushdown(int u) {
25
    if (tr[u].tag) {
26
        if (tr[u].ls) swap(tr[tr[u].ls].ls, tr[tr[u].ls].rs), tr[tr[u].ls].tag ^= 1;
27
        if (tr[u].rs) swap(tr[tr[u].rs].ls, tr[tr[u].rs].rs), tr[tr[u].rs].tag ^= 1;
28
        tr[u].tag = 0;
29
    }
30
}
31

32
void split(int u, int k, int &x, int &y) {
33
    if (!u) {
34
        x = y = 0;
35
        return;
36
    }
37
    pushdown(u);
38
    int lsiz = tr[tr[u].ls].cnt + 1;
39
    if (lsiz <= k) x = u, split(tr[u].rs, k - lsiz, tr[u].rs, y);
40
    else y = u, split(tr[u].ls, k, x, tr[u].ls);
41
    pushup(u);
42
}
43

44
int merge(int u, int v) {
45
    if (!u || !v) return u | v;
46
    if (tr[u].pri < tr[v].pri) {
47
        pushdown(u);
48
        tr[u].rs = merge(tr[u].rs, v);
49
        pushup(u);
50
        return u;
51
    }
52
    else {
53
        pushdown(v);
54
        tr[v].ls = merge(u, tr[v].ls);
55
        pushup(v);
56
        return v;
57
    }
58
}
59

60
int newNode(int t) {
61
    tr[++tot] = {0, 0, 1, t, t, 0, rnd()};
62
    return tot;
63
}
64

65
void print(int u) {
66
    if (!u) return;
67
    else {
68
        pushdown(u);
69
        print(tr[u].ls);
70
        cout << tr[u].val << ' ';
71
        print(tr[u].rs);
72
    }
73
}
74

75
int main() {
76
    ios::sync_with_stdio(0);
77
    cin.tie(0), cout.tie(0);
78
    int n, q;
79
    cin >> n >> q;
80
    for (int i = 1; i <= n; ++i) {
81
        int t;
82
        cin >> t;
83
        rt = merge(rt, newNode(t));
84
    }
85
    while (q--) {
86
        int op, a, b;
87
        cin >> op >> a >> b;
88
        int l, m, r;
89
        split(rt, a - 1, l, m);
90
        split(m, b - a + 1, m, r);
91
        if (op == 1) {
92
            swap(tr[m].ls, tr[m].rs);
93
            tr[m].tag ^= 1;
94
        }
95
        else cout << tr[m].s << endl;
96
        rt = merge(merge(l, m), r);
97
    }
98
    return 0;
99
}

Necessary Roads#

跑无向图 tarjan 找到桥即可。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 100010, M = 200010;
6

7
int head[N], ver[M * 2], ne[M * 2], tot = 1;
8
int dfn[N], low[N], t;
9
bool bridge[M * 2];
10
int cnt;
11

12
void add(int x, int y) {
13
    ver[++tot] = y;
14
    ne[tot] = head[x];
15
    head[x] = tot;
16
}
17

18
void tarjan(int x, int from) {
19
    dfn[x] = low[x] = ++t;
20
    for (int i = head[x]; i; i = ne[i]) {
21
        if (i == (from ^ 1)) continue;
22
        int y = ver[i];
23
        if (!dfn[y]) {
24
            tarjan(y, i);
25
            low[x] = min(low[x], low[y]);
26
            if (dfn[x] < low[y]) bridge[i] = bridge[i ^ 1] = true, cnt++;
27
        }
28
        else low[x] = min(low[x], dfn[y]);
29
    }
30
}
31

32
int main() {
33
    ios::sync_with_stdio(0);
34
    cin.tie(0), cout.tie(0);
35
    int n, m;
36
    cin >> n >> m;
37
    for (int i = 1; i <= m; ++i) {
38
        int x, y;
39
        cin >> x >> y;
40
        add(x, y), add(y, x);
41
    }
42
    tarjan(1, 0);
43
    cout << cnt << endl;
44
    for (int i = 2; i <= tot; i += 2) {
45
        if (bridge[i]) cout << ver[i ^ 1] << ' ' << ver[i] << endl;
46
    }
47
    return 0;
48
}

Necessary Cities#

跑无向图 tarjan 找到割点即可。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 100010, M = 200010;
6

7
int head[N], ver[M * 2], ne[M * 2], tot = 1;
8
int dfn[N], low[N], t;
9
bool cut[N];
10

11
void add(int x, int y) {
12
    ver[++tot] = y;
13
    ne[tot] = head[x];
14
    head[x] = tot;
15
}
16

17
void tarjan(int x, int from) {
18
    dfn[x] = low[x] = ++t;
19
    int f = 0;
20
    for (int i = head[x]; i; i = ne[i]) {
21
        if (i == (from ^ 1)) continue;
22
        int y = ver[i];
23
        if (!dfn[y]) {
24
            tarjan(y, i);
25
            low[x] = min(low[x], low[y]);
26
            if (x == 1) {
27
                if (++f == 2) cut[x] = true;
28
            }
29
            else if (dfn[x] <= low[y]) cut[x] = true;
30
        }
31
        else low[x] = min(low[x], dfn[y]);
32
    }
33
}
34

35
int main() {
36
    ios::sync_with_stdio(0);
37
    cin.tie(0), cout.tie(0);
38
    int n, m;
39
    cin >> n >> m;
40
    for (int i = 1; i <= m; ++i) {
41
        int x, y;
42
        cin >> x >> y;
43
        add(x, y), add(y, x);
44
    }
45
    tarjan(1, 0);
46
    int cnt = 0;
47
    for (int i = 1; i <= n; ++i) if (cut[i]) cnt++;
48
    cout << cnt << endl;
49
    for (int i = 1; i <= n; ++i) if (cut[i]) cout << i << ' ';
50
    cout << endl;
51
    return 0;
52
}

Star's Blog