Codeforces Round 922 (Div. 2)

发表于 更新于 分类于 阅读次数： 本文字数： 1k 阅读时长 ≈ 4 分钟
Opportunities don't happen; you create them.

A. Brick Wall

思路：

  • 水平的砖尽可能多，那么直接输出 \(n \times (m \div 2)\)​ 即可

时间复杂度：\(O(1)\)

1
2
3
4
5
6
void solve() {
    int n, m;
    std::cin >> n >> m;

    std::cout << 1LL * n * (m / 2) << "\n";
}

B. Minimize Inversions

思路：

  • 两个序列，那么只要其中一个是升序的，那么两者之和一定最少

时间复杂度：\(O(nlogn)\)

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
void solve() {
    int n;
    std::cin >> n;

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

    std::vector<int> p(n);
    std::iota(p.begin(), p.end(), 0);

    std::sort(p.begin(), p.end(), [&](int i, int j) {
        return a[i] < a[j];
    });

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

C. XOR-distance

思路：

  • 首先，解决本题要了解异或(xor)的性质，即：相同位为 0，不同位为 1
  • 那么要使得本题的 \(|(a \oplus x) - (b \oplus x)|\) 的最小值，那么我们要明确，一定是使得 \((a \oplus x)\) 和 \((b \oplus x)\) 的值尽可能的接近
  • 首先我们可以默认 \(a > b\) ，那么我们将 \(a\) 转换为二进制， \(b\) 转换为二进制，然后我们要缩小 \((a \oplus x)\) 和 \((b \oplus x)\) 的差距，那么就需要明确，如果 \(a\) 的二进制表示中的某一位和 \(b\) 的二进制表示的某一位出现了不同，且 \(bita_i > bitb_i\) 那么就需要将 \(a\) 的这一位与 \(b\) 的这一位交换(sum + 1 << i <= r的情况下)
  • 特别注意，如果从高位到低位枚举的第一个不同点出现，且这个位置的 \(bita_i > bitb_i\) ，那么就要略过这一位，因为这一位换了的贡献要大于其他后面低位的所有位的贡献，这是可以证明的

推荐看一下这一篇讲解

时间复杂度：\(O(logn)\)

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
void solve() {
    i64 a, b, r;
    std::cin >> a >> b >> r;
    if (a < b) {
        std::swap(a, b);
    }
    std::array<int, 64> bita {}, bitb {};
    for (int i = 0; i <= 63; i++) {
        if (a >> i & 1) {
            bita[63 - i] = 1;
        }
        if (b >> i & 1) {
            bitb[63 - i] = 1;
        }
    }

    bool ok = false;
    i64 sum = 0;
    for (int i = 0; i <= 63; i++) {
        if (bita[i] != bitb[i]) {
            if (!ok) {
                ok = true;
            } else {
                if (bita[i] > bitb[i]) {
                    i64 t = 1LL << (63 - i);
                    if (t + sum <= r) {
                        sum += t;
                    }
                }
            }
        }
    }
    std::cout << abs((a - sum) - (b + sum)) << "\n";
}

D. Blocking Elements

snow的代码

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

using ll = long long ;

void solve() {
    int n;
    cin >> n;
    
    vector<ll> a(n + 1);
    
    ll ub = 0, lb = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        lb = max(lb, a[i]);
        ub += a[i];
    }
    
    auto check = [&](ll x) {
        ll rest = 0;
        for (int i = 1; i <= n; i++) {
            int j = i;
            ll temp = a[i];
            while (j < n && temp + a[j + 1] <= x) temp += a[++j];
            i = j + 1;
            if (i <= n) rest += a[i];
        }
        if (rest <= x) return true;
        
        rest = a[1];
        for (int i = 2; i <= n; i++) {
            int j = i;
            ll temp = a[i];
            while (j < n && temp + a[j + 1] <= x) temp += a[++j];
            i = j + 1;
            if (i <= n) rest += a[i];
        }
        
        return rest <= x;
    };
    
    ll l = lb, r = ub, res = ub;
    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (check(mid)) r = (res = mid) - 1;
        else l = mid + 1;
    }
    
    cout << res << '\n';
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
    solve();
    return 0;
}

F. Caterpillar on a Tree

snow的代码

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

const int N = 2e5 + 10;

vector<int> G[N], tmp;
int dep[N], mx[N], f[N][20];

void dfs1(int u, int rt) {
    dep[u] = dep[rt] + 1;
    
    if (G[u].empty()) mx[u] = dep[u];
    
    f[u][0] = rt;
    for (int i = 1; i < 20; i++) {
        f[u][i] = f[f[u][i - 1]][i - 1];
    }
    
    for (int v : G[u]) {
        dfs1(v, u);
        mx[u] = max(mx[u], mx[v]);
    }
}

void dfs2(int u) {
    if (G[u].empty()) tmp.push_back(u);
    
    sort(G[u].begin(), G[u].end(), [&](int A, int B) {
        return mx[A] < mx[B];
    });
    
    for (int v : G[u]) {
        dfs2(v);
    }
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    
    for (int i = 19; i >= 0; i--) {
        if (dep[f[u][i]] >= dep[v]) u = f[u][i];
    }
    
    if (u == v) return u;
    
    for (int i = 19; i >= 0; i--) {
        if (f[u][i] != f[v][i]) {
            u = f[u][i], v = f[v][i];
        }
    }
    
    return f[u][0];
}

int get(int u, int v) {
    return dep[u] + dep[v] - dep[lca(u, v)] * 2;
}

void solve() {
    int n, k;
    cin >> n >> k;
    
    for (int i = 2; i <= n; i++) {
        int p; cin >> p;
        G[p].push_back(i);
    }
    
    dfs1(1, 0);
    dfs2(1);
    
    vector<int> vec;
    
    int ans = dep[tmp[0]] - 1;
    
    for (int i = 0; i + 1 < tmp.size(); i++) {
        
        int dis = get(tmp[i], tmp[i + 1]);
        ans += dis;
        
        if (dis > dep[tmp[i + 1]] - 1) {
            vec.push_back((dep[tmp[i + 1]] - 1) - dis);
        }
    }
    
    sort(vec.begin(), vec.end());
    
    for (int i = 0; i < k && i < vec.size(); i++) {
        ans += vec[i];
    }
    
    cout << ans;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}