第一周训练

1. ABC 267 D - Index × A(Not Continuous ver.)

题意

\(B\) 是 \(A\) 长度 \(M\) 的子集 求 \(\sum_1^M(i \times B_i)\) 最大值

做法

DP \[ dp[i][j] = max(dp[i][1 ... j - 1], dp[i - 1][j - 1] + i \times a[i]) \]

代码

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
/**
 * @author: XiaFan
 * @date: 09-05 19:28
 **/
#include <bits/stdc++.h>
using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    i64 n, m;
    std::cin >> n >> m;
    std::vector<i64> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }

    std::vector dp(m + 1, std::vector<i64>(n + 1, -1e16));
    for (int i = 0; i <= n; i++) {
        dp[0][i] = 0;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = std::max(dp[i][j], dp[i][j - 1]); 
            dp[i][j] = std::max(dp[i][j], dp[i - 1][j - 1] + i * a[j]); 
        }
    }

    std::cout << dp[m][n];

    return 0;
}

2. ABC 267 E - Erasing Vertices 2

题意

给你一张无向图，要删除所有节点
删除 \(i\) 节点的代价是与所有节点 \(j\)（节点 \(j\) 是与节点 \(i\) 直接连接的节点）的值 \(A[j]\) 的和 要求最小化删除所有节点的代价

做法

贪心
从代价最小的节点 \(i\) 开始删除，同时更新与节点 \(i\) 直接连接的节点删除代价

代码

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
/**
 * @author: XiaFan
 * @date: 09-07 18:58
 **/
#include <bits/stdc++.h>
using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    std::vector<i64> costs(n);
    std::vector<std::vector<int>> G(n);
    for (int i = 0; i < m; i++) {
        int x, y;
        std::cin >> x >> y;
        x--, y--;
        costs[x] += a[y];
        costs[y] += a[x];
        G[x].push_back(y);
        G[y].push_back(x);
    }
    
    std::set<std::pair<i64, int>> p;
    for (int i = 0; i < n; i++) {
        p.insert({costs[i], i});
    }

    i64 ans = 0;
    std::vector<bool> del(n, false);
    for (int i = 0; i < n; i++) {
        auto [cost, x] = *p.begin();
        ans = std::max(ans, cost);
        del[x] = true;
        p.erase(p.begin());
        for (auto y : G[x]) {
            if (del[y]) 
                continue;
            p.erase({costs[y], y});
            costs[y] -= a[x];
            p.insert({costs[y], y});
        }
    }

    std::cout << ans;
    
    return 0;
}

3. ABC 267 F - Exactly K Steps

题意

给一棵树，有一串询问
每个询问查询距离指定节点 \(U\) 距离 \(K\) 的一个节点，若不存在，输出 \(-1\)

做法

若存在这个点 \(Q\) ，必定在存在一个树的直径端点 \(P\) ，\(Q\) 在 \(UP\) 上

首先 \(BFS\) 两次算出树的直径两点，第一次 \(BFS\) 随机开始点，求出据随机点最远的点 \(D_1\) ，这就是直径的一个端点，第二次从这个点开始 \(BFS\) ，求出另一个直径端点 \(D_2\)

先预先读入所有询问
从直径的两端点开始 \(DFS\) ，将经过的点压入栈，若经过查询的点，就可以从栈中读取点
两次 \(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
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
/**
 * @author: XiaFan
 * @date: 09-07 19:26
 **/
#include <bits/stdc++.h>
using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;
    std::vector<std::vector<int>> adj(n);
    for (int i = 1; i < n; i++) {
        int x, y;
        std::cin >> x >> y;
        x--, y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    
    auto bfs = [&](int s) {
        std::vector<int> dis(n, -1);
        std::queue<int> q;
        q.push(s);
        dis[s] = 0;
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            for (auto y : adj[x]) {
                if (dis[y] == -1) {
                    dis[y] = dis[x] + 1;
                    q.push(y);
                }
            }
        }
        return std::max_element(dis.begin(), dis.end()) - dis.begin();
    };
    
    int v1 = bfs(0);
    int v2 = bfs(v1);
    // tree_d = distance(v1, v2)
    
    int q;
    std::cin >> q;
    std::vector<std::vector<std::pair<int, int>>> queries(n);
    for (int i = 0; i < q; i++) {
        int x, k;
        std::cin >> x >> k;
        x--;
        queries[x].push_back({k, i});
    }

    std::vector<int> v_stack;
    std::vector<int> ans(q, -1);
    std::function<void(int, int)> dfs = [&](int x, int parent) {
        for (auto [k, i] : queries[x]) {
            if (int(v_stack.size()) >= k) {
                ans[i] = v_stack[v_stack.size() - k] + 1;
            }
        }
        v_stack.push_back(x);
        for (auto y : adj[x]) {
            if (y != parent) {
                dfs(y, x);
            }
        }
        v_stack.pop_back();
    };
    
    dfs(v1, -1);
    dfs(v2, -1);
    
    for (int i = 0; i < q; i++) {
        std::cout << ans[i] << "\n";
    }
    
    return 0;
}

4. CF Round #819 D. Edge Split

题意

给一无向图，把边染成两种颜色
\(c_1\) 只考虑红色边，并计算图中连接组件的数量 \(c_2\) 只考虑蓝色边，并计算图中连接组件的数量 最小化 \(c_1 + c_2\)

做法

只要不染出单色环就可以 第一次并查集可以使得红色不成环，但不能保证蓝色，找出蓝色成环的一条边，强制红色，再进行一次并查集就可以了

代码

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
/**
 * @author: XiaFan
 * @date: 09-08 19:44
 **/
#include <bits/stdc++.h>
using i64 = long long;

struct DSU {
    int n;
    std::vector<int> f, siz;

    DSU(int n_) : n(n_), f(n_), siz(n_, 1) {
        std::iota(f.begin(), f.end(), 0);
    }

    int leader(int x) {
        while (x != f[x]) {
            f[x] = f[f[x]];
            x = f[x];
        }
        return x;
    }

    bool same(int x, int y) {
        return leader(x) == leader(y);
    }

    bool merge(int x, int y) {
        x = leader(x);
        y = leader(y);
        if (x == y) return false;
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }

    int size(int x) {
        return siz[leader(x)];
    }

    int num() {
        std::set<int> st;
        for (int i = 0; i < n; i++) {
            st.insert(leader(i));
        }
        return st.size();
    }
};

void solve() {
    int n, m;
    std::cin >> n >> m;
    DSU dsu1(n);
    std::string s;
    std::vector<std::pair<int, int>> edge(m);
    for (auto &[x, y] : edge) {
        std::cin >> x >> y;
        x--, y--;
        if (dsu1.merge(x, y)) {
            s.push_back('0');
        } else {
            s.push_back('1');
        }
    }

    DSU ans(n), dsu2(n);
    for (int i = 0; i < m; i++) {
        auto [x, y] = edge[i];
        if (s[i] == '1') {
            if (!dsu2.merge(x, y)) {
                ans.merge(x, y);
                s[i] = '2';
            }
        }
    }

    for (int i = 0; i < m; i++) {
        auto [x, y] = edge[i];
        if (s[i] == '2') {
            s[i] = '0';
        } else if (ans.merge(x, y)) {
            s[i] = '0';
        } else {
            s[i] = '1';
        }
    }

    std::cout << s << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int tt;
    std::cin >> tt;
    while (tt--) {
        solve();
    }

    return 0;
}

5. CF Round #817 G. Even-Odd XOR

题意

构建长度 n 的数组 奇偶下表的 \(XOR\) 相等

做法

前 \(n - 2\) 位随便取 \(a[n - 1]\) 选个大数，然后计算出 \(a[n]\) 即可

代码

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
/**
 * @author: XiaFan
 * @date: 09-05 20:07
 **/
#include <bits/stdc++.h>
using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
    
    std::vector<int> a(n);

    if (n == 3) {
        std::cout << "2 1 3\n";
        return;
    }

    std::iota(a.begin(), a.end(), 1);

    int m = n - 2;
    if (n % 2 == 1) {
        m--;
        a[n - 1] = 0;
    }

    int x = 0, y = 0;
    for (int i = 0; i < m; i++) {
        if (i % 2 == 0) {
            x ^= a[i];
        } else {
            y ^= a[i];
        }
    }
    a[m] = 114514 * 16;
    a[m + 1] = a[m] ^ x ^ y;

    for (int i = 0; i < n; i++) {
        std::cout << a[i] << " ";
    } 
    std::cout << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int tt;
    std::cin >> tt;
    while (tt--) {
        solve();
    }
    
    return 0;
}