A、Insert One

转成字符串考虑， 如果前面有负号， 增加使得结果最小， 否则，最大。暴力处理即可

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

void solve() {
    std::string s;
    std::cin >> s;
    if (s[0] == '-') {
        std::string str = s.substr(1);
        std::string t = "1" + s.substr(1);
        for (int i = 1; i < t.size(); i++) {
            std::string tmp = str.substr(0, i) + "1" + str.substr(i);
            t = std::min(t, tmp);
        }
        t = "-" + t;
        std::cout << t << '\n';
    } else {
        std::string str = s;
        std::string t = "1" + s;
        for (int i = 1; i < t.size(); i++) {
            std::string tmp = str.substr(0, i) + "1" + str.substr(i);
            t = std::max(t, tmp);
        }
        std::cout << t << '\n';
    }
}

signed main() {
    int t = 1;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C、Bernoulli’s Principle

简单推个公式 h = 1 / 2 * g * t ^ 2，代入可知 水平距离和 sqrt(h * (H - h)) 正相关

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

void solve() {
    int n, h;
    std::cin >> n >> h;
    std::vector<std::array<int, 2>> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i][0];
        a[i][0] = (h - a[i][0]) * a[i][0];
        a[i][1] = i + 1;
    }
    sort(a.begin(), a.end());
    for (auto& [x, idx] : a) {
        std::cout << idx << ' ';
    }
    std::cout << '\n';
}

signed main() {
    int t = 1;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B、Inversion Number Parity

按照题目要求对 生成的数一一求解即可， 注意有内存限制，不能用数组存起来。要边求随机数边计算结果。 还有一个交换不同位置的两个数为使逆序对的数量增减奇数个，所以求解时只需要关注是否有奇数个不同的位置交换。【l, r】循环移动d次，相当于(r - l) * d 个不同位置交换， 只需要判断 这个结果的奇偶性即可

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

void solve() {
    int n, a, b, c;
    std::cin >> n >> a >> b >> c;
    int f3, f2, f1;
    int u = (1 << 30) - 1;
    f3 = u & a, f2 = u & b, f1 = u & c;
    int g, h, f;
    int cnt = 0;
    for (int i = 0; i <= n; i++) {
        g = f3 ^ (((1 << 16) * f3) & u);
        h = g ^ (g / (1 << 5));
        f = h ^ ((2 * h) & u) ^ f2 ^ f1;
        if (i < n && (i + f % (n - i)) != i) {
            cnt++;
        }
        f3 = f2, f2 = f1, f1 = f;
    }
    std::string ans;
    if (cnt & 1) ans += '1';
    else ans += '0';

    for (int i = 1; i < n; i++) {
        g = f3 ^ (((1 << 16) * f3) & u);
        h = g ^ (g / (1 << 5));
        f = h ^ ((2 * h) & u) ^ f2 ^ f1;

        int l = std::min(f % n, f1 % n), r = std::max(f % n, f1 % n);
        f3 = f2, f2 = f1, f1 = f;
        g = f3 ^ (((1 << 16) * f3) & u);
        h = g ^ (g / (1 << 5));
        f = h ^ ((2 * h) & u) ^ f2 ^ f1;

        int d = f % n + 1;
        f3 = f2, f2 = f1, f1 = f;
        g = f3 ^ (((1 << 16) * f3) & u);
        h = g ^ (g / (1 << 5));
        f = h ^ ((2 * h) & u) ^ f2 ^ f1;

        f3 = f2, f2 = f1, f1 = f;
        if (((r - l) * d) & 1) {
            cnt++;
        }
        if (cnt & 1) {
            ans += '1';
        } else {
            ans += '0';
        }
    }
    std::cout << ans << '\n';
}

signed main() {
    int t = 1;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

G、Changing Minimum Spanning Tree

连通块数量大于2的时候误解， 输出0， 联通块个数为2时， 输出两个两个连通块大小的乘积 再成k

只需要处理联通块是1的情况， 首先对MST中边权进行排序，按照边权分段考虑，假设当前考虑了权 值最大值为w的MST子集，不在子集里的MST边权最小值是w1 (w1 - 1) * size1 * size2 加入答案。但是需要去掉重边的情况

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
#include <bits/stdc++.h>
#define int long long
const int MOD = 1e9 + 7;

struct DSU {
    std::vector<int> f, siz;
    DSU(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    } 
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    int size(int x) {
        return siz[find(x)];
    }
};
void solve() {
    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<std::array<int, 3>> e(m);

    for (int i = 0; i < m; i++) {
        int u, v, w;
        std::cin >> u >> v >> w;
        u--, v--;
        e[i] = {w, u, v};
    }
    std::sort(e.begin(), e.end());
    DSU dsu(n);
    int c = n;
    int ans = 0;
    
    std::vector<int> f(n), p(n, -1), dep(n);
    std::vector<int> ord;

    for (auto& [w, u, v] : e) {
        if (!dsu.same(u, v)) {
            u = dsu.find(u);
            v = dsu.find(v);
            ans = (ans + (int)dsu.size(u) * dsu.size(v) * (w - 1) % MOD) % MOD;
            if (dsu.size(u) < dsu.size(v)) {
                std::swap(u, v);
            }
            c--;
            f[v] = w;
            ord.push_back(v);
            p[v] = u;
            dsu.merge(u, v);
        }
    }
    if (c > 2) {
        ans = 0;
    } else if (c == 2){
        for (int i = 1; i < n; i++) {
            if (!dsu.same(i, 0)) {
                ans = (dsu.size(0) * dsu.size(i) % MOD) * k % MOD;
                break;
            }
        }
    } else {
        std::reverse(ord.begin(), ord.end());
        for (auto x : ord) {
            dep[x] = dep[p[x]] + 1;
        }
        for (auto [w, u, v] : e) {
            int t = 0;
            while (u != v) {
                if (dep[u] < dep[v]) {
                    std::swap(u, v);
                }
                t = std::max(t, f[u]);
                u = p[u];
            } 
            ans = (ans - (t - 1) + MOD) % MOD;
        }
    }
    std::cout << ans << '\n';
}

signed main() {
    int t = 1;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

F、Broken LED Lights

某个灯管选择方案 S 中两个不同的数字能被区分出来，当且仅当这个方案表示的这两个数字中至少有一个灯管显示状态不同。对所有数字的表示情况两两异或，那么问题就会转化为找到能与所有异或值均有交集的最小选择数 S。 据此，先将所有的异或值去重，然后把选择灯管的数量作为 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
#include <bits/stdc++.h>
#define int long long
constexpr int MASK[] = {0b1110111, 0b0010010, 0b1011101, 0b1011011, 0b0111010, 0b1101011, 0b1101111, 0b1010010, 0b1111111, 0b1111011};

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

void solve() {
    int n, m;
    std::cin >> n >> m;
    int res = INT_MAX;
    std::vector<int> a(n + 5), b;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            char x;
            std::cin >> x;
            a[i] |= MASK[x - '0'] << (j * 7);
        }
    
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
                b.push_back(a[i] ^ a[j]);
        }
    }
    
    sort(b.begin(), b.end());
    
    auto dfs = [&](auto &&self, int sum, int dep) -> void{
        if (dep >= res) return;
        int num = 0;
        for (auto x : b)
            if ((x & sum) == 0) {
                num = x;
                break;
            }
        
        if (num == 0) res = std::min(res, dep);
        else {
            for (int i = num; i; i -= lowbit(i)) {
                self(self, sum | lowbit(i), dep + 1);
            }
        }
    };
    
    dfs(dfs, 0, 0);
    std::cout << res << '\n';

}

signed main() {
    int t = 1;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}