A. It’s Time to Duel

不合法的就两个条件，满足任何一个即不合法：

  1. 总和超过 n−1n-1，因为 n−1n-1 场比赛最多 n−1n-1 个胜者
  2. 连续两个 00。这是因为他们之间必有一场比赛，因此必有一个胜者
Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <headers/io/iov2.hpp>
#include <numeric>
#include <vector>
IO::IO io;

void run() {
    int n              = io.scan<int>();
    std::vector<int> s = io.scan<std::vector<int>>(n);

    if (std::accumulate(s.begin(), s.end(), 0) >= n) return io.println("YES");

    // consecutive 0s
    for (int i = 0; i < n - 1; i++)
        if (s[i] == 0 && s[i + 1] == 0) return io.println("YES");

    io.println("NO");
}

int main() {
    int T = io.scan<int>();
    while (T--) run();
}

B. Slice to Survival

如果换个先手，让 Fouad 先移动，那么他一定会移动到中心的位置，Mouf 每次切只能切掉一半。这时的总次数就是 ⌈log⁡2n⌉×⌈log⁡2m⌉\lceil \log_2 n\rceil \times \lceil \log_2 m\rceil.

但是现在是 Mouf 先手，所以我们考虑把第一次的先手提出来单独计算，于是剩下的就和上面一样了。总次数

1+min⁡{⌈log⁡2n⌉+⌈log⁡2min⁡(b,m−b+1)⌉,⌈log⁡2min⁡(a,n−a+1)⌉+⌈log⁡2m⌉} \gdef\clog#1{\lceil\log_2 #1\rceil} 1+\min\Bigg\{ \clog{n}+\clog{\min(b,m-b+1)}, \clog{\min(a,n-a+1)}+\clog{m} \Bigg\}
Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <algorithm>
#include <headers/io/iov2.hpp>
IO::IO io;
using i64 = long long;

void run() {
    i64 n, m, a, b;
    io.read(n, m, a, b);

    auto clog2 = [&](i64 x) { return x <= 1 ? 0 : 64 - __builtin_clzll(x - 1); };
    io.println(1 + std::min(clog2(n) + clog2(std::min(b, m - b + 1)), clog2(std::min(a, n - a + 1)) + clog2(m)));
}

int main() {
    int T = io.scan<int>();
    while (T--) {
        run();
#ifndef ONLINE_JUDGE
        io.println("==========");
#endif
    }
    return 0;
}

C1. Hacking Numbers (Easy)

想法是快速归约到一个确定的数字，然后花一步到达 target.

那么我们最多用 66 完成归约这一步骤。想到用 digit 归约：因为题目 unknown number 最大不超过 10910^9，因此数位和最大为 8181 (对应的数为 99 个 99)，再进行一次 digit 运算则数位和最大为 1616 (对应的数为 7979)。

然后就只剩四步归约到某个确定的数上。考虑二进制（直觉说 log⁡216=4\log_2 16=4），我们依次减去 20,21,22,232^0,2^1,2^2,2^3，于是无论如何，xx 都会被减成 11，这个数就确定了。这样对于每个数都可以通过这 77 完成。

Code
 
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
#include <iostream>
using i64 = long long;

int digit() {
    std::cout << "digit" << std::endl;
    int d;
    std::cin >> d;
    return d;
}
int add(i64 x) {
    std::cout << "add " << x << std::endl;
    int d;
    std::cin >> d;
    return d;
}
int mul(i64 x) {
    std::cout << "mul " << x << std::endl;
    int d;
    std::cin >> d;
    return d;
}
int div(i64 x) {
    std::cout << "div " << x << std::endl;
    int d;
    std::cin >> d;
    return d;
}
void finish() {
    std::cout << "!" << std::endl;
    int d;
    std::cin >> d;
}

void run() {
    i64 target;
    std::cin >> target;

    digit(), digit();
    for (int i = 3; i >= 0; i--) add(-(1 << i));
    add(target - 1);
    finish();
}

int main() {
    int T = 1;
    std::cin >> T;
    while (T--) run();
}

C2. Hacking Numbers (Medium)

想法依然是快速归约到一个数字。上一题我们用了两次 digit，这一次，我们考虑先 ×9\times 9，这样其数位和一定是 99 的倍数，而且最多 1010 位数，因此数位和还一定 ≤90\le 90，于是，再做一次数位和，我们就一定可以得到 99。然后再花一步得到结果即可。

D. D/D/D

想到了大致做法但是小细节想错了 orz

首先要考虑到一件事：如果我们可以用 SS 步到达点 ii，那么我们也可以用 S+2k,k∈NS+2k,k\in\N 步到达点 ii，方法是选一条边 (u,v)(u,v) 来回走 u→v→u…u\to v\to u \dots.

因此我们只需要维护两个东西，一个是“通过最少的奇数步到达点 ii” dp[i][1]dp[i][1]，另一个是“通过最少的偶数步到达点 ii” dp[i][0]dp[i][0]. 因为只关心最少，我们直接 BFS，同时注意转移

dp[u][0]=min⁡(u,v)∈E(dp[v][1]+1)dp[u][1]=min⁡(u,v)∈E(dp[v][0]+1) dp[u][0]=\min_{(u,v)\in E} (dp[v][1]+1)\\ dp[u][1]=\min_{(u,v)\in E} (dp[v][0]+1)
Code
 
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
#include <array>
#include <headers/io/iov2.hpp>
#include <queue>
#include <utility>
#include <vector>
IO::IO io;
using i64 = long long;

void run() {
    auto [n, m, l]     = io.scan<int, int, int>();
    std::vector<i64> a = io.scan<decltype(a)>(l);

    i64 max_even = 0, max_odd = 0, sum = 0;
    i64 min_even = 1e18, min_odd = 1e18;
    for (auto i : a) {
        sum += i;
        if (i % 2 == 0) min_even = std::min(min_even, i);
        else min_odd = std::min(min_odd, i);
    }
    max_even = (sum % 2 == 0 ? sum : sum - min_odd);
    max_odd  = (sum % 2 == 1 ? sum : sum - min_odd);

    std::vector<std::vector<int>> G(n);
    for (int i = 0; i < m; i++) {
        auto [u, v] = io.scan<int, int>();
        u--, v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    // BFS tree
    std::vector<std::array<i64, 2>> dp(n, {static_cast<int>(1e18), static_cast<int>(1e18)});

    std::queue<std::pair<int, i64>> q;
    q.push({0, 0});
    dp[0][0] = 0; // start with even

    while (!q.empty()) {
        auto [u, d] = q.front();
        q.pop();
        i64 parity = d % 2; // 0 for even, 1 for odd
        for (auto v : G[u]) {
            if (dp.at(v).at(!parity) > dp.at(u).at(parity) + 1) {
                dp.at(v).at(!parity) = dp.at(u).at(parity) + 1;
                q.push({v, d + 1});
            }
        }
    }

    io.set_delim("");
    for (int i = 0; i < n; i++) {
        if (max_even >= dp.at(i).at(0) || max_odd >= dp.at(i).at(1)) io.print("1");
        else io.print("0");
    }
    io.println();
}

int main() {
    int T = io.scan<int>();
    while (T--) {
        run();
#ifndef ONLINE_JUDGE
        io.println("==========");
#endif
    }
    return 0;
}