暑假集训 Nowcoder 多校 Round 1

第一次参加暑假集训的牛客多校，感觉还是挺难的。

比赛链接

D 「Chocolate」

签到题，只有 1 × 1 的时候 Walk Alone 会赢，其余情况均是 Kelin 赢。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>

void solve() {
    int n, m;
    std::cin >> n >> m;
    if (n == 1 && m == 1) {
        std::cout << "Walk Alone\n";
    }
    else {
        std::cout << "Kelin\n";
    }
}

int main() {

    solve();

    return 0;
}

J 「Roulette」

以 ”输-输-输-输-...-输-赢“ 为一个周期，Walk Alone 的钱只会增加 1 块，且接下来重新从 1 块开始下注。

假设有 x 块钱，且从 1 开始下注的胜率为 \(p_x\)，可得： \[ p_x = (1 - \frac{1}{2 ^ k}) p_{x + 1} \] 其中 \(k\) 满足：\(x \in [2 ^ r - 1, 2 ^ {r + 1} - 1)\)，接下来只要枚举区间然后使用快速幂即可。

时间复杂度：\(O(log^2n)\)

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

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
#include <iostream>
#include <algorithm>

using i64 = long long;
const i64 mod = 998244353ll;

i64 quickPow(i64 x, i64 n) {
    i64 res = 1;
    while (n) {
        if (n & 1) {
            res = res * x % mod;
        }
        x = x * x % mod;
        n >>= 1;
    }

    return res;
}

i64 inverse(i64 x) {

    return quickPow(x, mod - 2);
}

void solve() {
    i64 n, m;
    std::cin >> n >> m;
    int k = 1;
    while (n >= (1ll << (k + 1)) - 1ll) k++;
    i64 res = 1ll;
    i64 l = n, r = std::min((1ll << (k + 1)) - 1ll, n + m);
    i64 i2 = inverse(2);
    while (l < n + m) {
        i64 x = (1 - quickPow(i2, k) + mod) % mod;
        res = res * quickPow(x, r - l) % mod;
        l = r;
        r = std::min(((r + 1ll) << 1) - 1, n + m);
        k++;
    }

    std::cout << res << '\n';
}

int main() {

    solve();

    return 0;
}

K 「Subdivision」

先从从顶点 1 出发构造 BFS 树（只延伸 k 步），接下来新增顶点无非有以下两种类型：

  1. 加在非树边上的点：

    对于非树边而言，无论加多少点，都不会影响到最终结果，假设在非树边 \(<x, y>\) 上加入尽可能多的点，则新增到顶点 1 的距离不超过 k 的点有 \(2 \times k - dist[x] - dist[y]\) ，其中 \(dist[v]\) 表示 \(v\) 到顶点 1 的距离。

  2. 加在树边上的点： 假设存在末端节点 \(v\) 不与其他非树边相连，则可以延长末端节点，可新增 \(k - dist[v]\) 个点。

时间复杂度：\(O(n + m)\)

空间复杂度：\(O(n + m)\)

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
#include <iostream>
#include <queue>
#include <vector>

using i64 = long long;

void solve() {
    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<std::vector<int>> g(n);
    for (int i = 0, x, y; i < m; i++) {
        std::cin >> x >> y;
        x--;
        y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    std::vector<int> dist(n, -1);
    dist[0] = 0;
    std::queue<int> q;
    q.push(0);
    i64 cnt = 1ll; // 初始状态有多少距离不超过 k 的点数
    std::vector<int> tree(n, -1); // 构造 BFS 树
    tree[0] = 0;
    std::vector<int> endVertex; // BFS 树的末端节点
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        int d = dist[v] + 1;
        if (d > k) continue;
        bool tag = false;
        for (int x : g[v]) {
            if (dist[x] == -1) {
                // 未发现的点
                dist[x] = d;
                q.push(x);
                cnt++; // d <= k
                tree[x] = v;
                tag = true;
            }
        }
        if (!tag) endVertex.push_back(v); // 树的末端
    }

    // 加在非树边上的点
    for (int i = 0; i < n; i++) {
        for (int j : g[i]) {
            if (i < j && dist[i] != -1 && dist[j] != -1 && tree[i] != j && tree[j] != i) {
                cnt += 2ll * k - dist[i] - dist[j];
            }
        }
    }

    // 加在树边上的点（树的末端）
    for (int i : endVertex) {
        bool tag = false;
        for (int j : g[i]) {
            if (dist[i] != -1 && tree[i] != j) {
                tag = true;
                break;
            }
        }
        // 不存在非树边与末端连接
        if (!tag && i != 0) cnt += 1ll * k - dist[i];
    }

    std::cout << cnt << '\n';
}

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

    solve();

    return 0;
}

H 「Matches」

假设交换两个下标 \(i\) 和 \(j\) ，则 \(\sum_{k = 1} ^ n |a_k - b_k|\) 在原来的基础上减小 \(|a_i - b_i| + |a_j - b_j| - |a_i - b_j| - |a_j - b_i|\) ，换言之，我们只要能最大化 \(|a_i - b_i| + |a_j - b_j| - |a_i - b_j| - |a_j - b_i|\) 即可。

我们将每一对 \((a_i， b_i)\) 划分为两类区间：

  1. \([a_i, b_i]\)，\((a_i \leq b_i)\)
  2. \([b_i, a_i]\)，\((a_i > b_i)\)

问题就转化为我们要找到两个不同的区间，使得 \(f(i, j) = |a_i - b_i| + |a_j - b_j| - |a_i - b_j| - |a_j - b_i|\) 的值最大。

事实上，很容易证明当区间属于同一类的时候 \(f(i, j) \leq 0\) ，因此选取的两个区间只能来自不同的类，简单计算可得 \(f(i, j)\) 就等于两个区间相交部分的值。

所以我们只需要找到两类区间相交部分的最大值即可。

具体算法实现时可以考虑先枚举两类区间，存储到两个数组，然后分别按照区间左端点大小进行排序，同时使用两个新数组维护两类区间右端点前缀最大值，然后对任意一个区间 \(r = [x, y]\) ，在另一类区间数组中使用二分查找找到左区间不超过 \(x\) 的最大区间下标，根据前面定义的前缀数组，于是我们就得到了左区间端点不超过 \(x\) 的区间里右区间的最大值，通过此方式，我们可以枚举所有可能的最大区间交集。

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

空间复杂度：\(O(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
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
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using i64 = long long;

int binary_search(const std::vector<std::pair<int, int>>& r, int d) {
    // 找到区间 r[i] 左端点不超过 d 最大 i
    if (r.empty()) return -1;
    int left = 0, right = r.size() - 1;
    // r[left].first <= d < r[right].first
    if (r[left].first > d) return -1;
    if (r[right].second <= d) return right;

    while (right - left > 1) {
        int mid = (left + right) / 2;
        if (r[mid].first <= d) {
            left = mid;
        }
        else {
            right = mid;
        }
    }

    return left;
}

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    std::vector<int> 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<std::pair<int, int>> r1;
    std::vector<std::pair<int, int>> r2;
    for (int i = 0; i < n; i++) {
        if (a[i] <= b[i]) {
            r1.push_back(std::make_pair(a[i], b[i]));
        }
        else {
            r2.push_back(std::make_pair(b[i], a[i]));
        }
    }
    int n1 = r1.size(), n2 = r2.size();

    std::sort(r1.begin(), r1.end());
    std::sort(r2.begin(), r2.end());

    std::vector<int> maxrb_1(n1);
    if (n1 > 0) maxrb_1[0] = r1[0].second;
    for (int i = 1; i < n1; i++) {
        maxrb_1[i] = std::max(maxrb_1[i - 1], r1[i].second);
    }
    std::vector<int> maxrb_2(n2);
    if (n2 > 0) maxrb_2[0] = r2[0].second;
    for (int i = 1; i < n2; i++) {
        maxrb_2[i] = std::max(maxrb_2[i - 1], r2[i].second);
    }

    i64 res = 0;
    
    for (int i = 0; i < n1; i++) {
        int j = binary_search(r2, r1[i].first);
        if (j == -1) continue;

        int l = r1[i].first;
        int r = std::min(r1[i].second, maxrb_2[j]);
        if (r > l) res = std::max(res, (i64)r - l);
    }

    for (int i = 0; i < n2; i++) {
        int j = binary_search(r1, r2[i].first);
        if (j == -1) continue;

        int l = r2[i].first;
        int r = std::min(r2[i].second, maxrb_1[j]);
        if (r > l) res = std::max(res, (i64)r - l);
    }

    i64 sum = 0;
    for (int i = 0; i < n; i++) {
        sum += abs((i64)a[i] - b[i]);
    }

    std::cout << sum - 2 * res << '\n';
}

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

    solve();

    return 0;
}

M 「Water」

一个比较典型的问题，假设存在解（\(r\), \(s\)）使得 \(rA + sB = x\) 则可以实现 Walk Alone 的需求，使用 exgcd 判断即可。

若不定方程存在解 \((r, s)\)，则答案为：\(max\{2(r + s), 2|r - s| - 1\}\) 。只需要找到使得该式最小的整数解 \((r, s)\) 即可。

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

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

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
#include <iostream>
#include <climits>
#include <cmath>

using i64 = long long;

i64 exgcd(i64 a, i64 b, i64& x, i64& y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }

    i64 g = exgcd(b, a % b, y, x);
    y -= (a / b) * x;

    return g;
}

void solve() {
    i64 a, b, x;
    std::cin >> a >> b >> x;
    i64 r, s;
    i64 g = exgcd(a, b, r, s);
    if (x % g != 0) {
        std::cout << -1 << '\n';
        return;
    }
    i64 c = x / g;
    r *= c, s *= c;
    // ar + bs = x

    i64 k1 = b / g, k2 = - a / g;
    auto minOp = [r, s, k1, k2](i64 t) -> i64 {
        i64 r0 = r + k1 * t;
        i64 s0 = s + k2 * t;
        if (r0 >= 0 && s0 >= 0) {
            return 2 * (r0 + s0);
        }
        else {
            return 2 * std::abs(r0 - s0) - 1;
        }
    };

    i64 res = INT64_MAX;
    const int ran = 3;
    for (i64 t0 : {-r / k1, -s / k2}) {
        for (i64 t = t0 - ran; t <= t0 + ran; t++) {
            res = std::min(res, minOp(t));
        }
    }

    std::cout << res << '\n';
}

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

    int numTest;
    std::cin >> numTest;
    while (numTest--) solve();

    return 0;
}
ACM
#Nowcoder
暑假集训 Nowcoder 多校 Round 1
https://goer17.github.io/2023/07/17/暑假集训 Nowcoder 多校 Round 1/
作者
Captain_Lee
发布于
2023年7月17日
许可协议