C - Coin

考虑令坐标为 00-indexed，那么 ii 位置的人会变成 i−⌈ik⌉i-\lceil\frac{i}{k}\rceil；类似的，后来是 ii 位置上的人上一轮是 i+⌊ik−1⌋+1i+\lfloor\frac{i}{k-1}\rfloor+1.

所以一个很自然的想法是，既然最终的位置是 00，那么我们直接用 i′←i+⌊ik−1⌋+1i'\gets i+\lfloor\frac{i}{k-1}\rfloor+1 一步步倒推. 时间和轮数成正比.

于是发现，当 kk 比较大的时候，轮数也会变大. 例如 k=nk=n 时，每次只会 eliminate 掉最开头的那个.

故考虑对 kk 进行分治.

  • 当 k≤nk\le \sqrt{n}，我们直接用式子倒推. 因为每次都会删去 nk\frac{n}{k}，所以差不多 O(n)O(\sqrt{n}) 轮.

  • 当 k>nk\gt \sqrt{n}，我们使用数论分块里的结论：⌈ik⌉\lceil\frac{i}{k}\rceil 和 ⌊ik−1⌋\lfloor\frac{i}{k-1}\rfloor 分别最多可以取 O(k)O(\sqrt{k}) 种不同的取值.
    我们可以计算出对于特定的 v=⌈ik⌉v=\lceil\frac{i}{k}\rceil 会减去多少次，故可以在 O(n)O(\sqrt{n}) 计算出总共经过多少轮.

    同理，我们可以计算出特定的 v=⌊ik−1⌋v=\lfloor\frac{i}{k-1}\rfloor 会加上多少次，故可以在 O(n)O(\sqrt{n}) 计算出准确的位置.

总体时间复杂度是 O(n)O(\sqrt{n}).

AC 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
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
#include <random>
using ll = long long;
constexpr ll V = 1e12;

ll n, k;
ll thres;
std::mt19937_64 rng(std::random_device{}());

ll ceil(ll x, ll y) { return (x - 1) / y + 1; }

ll f(ll n, ll k) {
    ll m, v = 0;
    while (true) {
        if (n < k) {
            m = n - 1;
            break;
        }
        n = n - ceil(n, k);
        v++;
    }
    while (v--) m = m + m / (k - 1) + 1;
    return m;
}

ll handle() {
    ll rounds = 0;
    [&] {
        ll e = n;
        auto find_l = [&] {
            ll f = (e + k - 1) / k;
            ll v = std::max(2ll, (f - 1) * k + 1);
            return v;
        };

        while (e > 1) {
            ll l = find_l();
            ll t = (e + k - 1) / k;
            ll x = (e - l) / t + 1;
            rounds += x;
            e -= t * x;
        }
    }();

    ll s = 0;
    auto find_max = [&] {
        ll f = s / (k - 1);
        return (f + 1) * (k - 1) - 1;
    };

    for (; rounds > 0;) {
        ll r = find_max();
        ll t = s / (k - 1) + 1;
        ll x = (r - s) / t + 1;
        x = std::min(x, rounds);
        s = s + x * t;
        rounds -= x;
    }

    return s;
}

void run() {
    std::cin >> n >> k;
    thres = std::sqrt(n);

    if (k == 1) std::cout << n << "\n";
    else if (k <= thres) {
        auto res = f(n, k);
        std::cout << res + 1 << "\n";
    } else std::cout << handle() + 1 << "\n";
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0), std::cout.tie(0);
    int t = 100;
    std::cin >> t;
    while (t--) run();
}

E - Extracting Weights

感觉其实不难想，一开始没有看到 nn 的数据范围. 不过代码也比较难写，可能赛时也不一定写得出来…

一次询问+回答相当于是一个 k+1k+1 元的方程. 所以，如果我们想解出 nn 个元，那么我们需要 nn 个线性无关的方程（其中包含一个 x1=0x_1=0 方程）.

所以算法思路就是，在树上处理出所有距离为 kk 的路径，把方程丢入线性基里，判断是否线性无关. 无关的话，那么加入查询列表. 最后得到每一个方程的值后，用高斯消元计算.

时间复杂度：O(n3)O(n^3)

AC 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
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
107
108
109
110
#include <bits/stdc++.h>
constexpr int N = 256;
using bs = std::bitset<N>;

int n, k;
std::vector<int> g[N];
bool vis[N];

namespace solver {
    bs B[N], val[N];
    std::pair<int, int> seg[N];
    int cnt;
    int res[N];

    void insert(bs b, int l, int r) {
        if (cnt == n) return;

        auto tmp = b;
        while (true) {
            int i = b._Find_first();
            if (i > n) break;
            if (!vis[i]) {
                vis[i] = true;
                B[i] = b, val[i] = tmp;
                seg[i] = {l, r};
                cnt++;
                return;
            } else b ^= B[i];
        }
    }

    bool check() { return cnt == n; }

    // <coef, RHS>
    void solve(std::vector<std::pair<bs, int>> &vec) {
        // reduce
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= i; j++) {
                if (vec[i].first.test(j)) {
                    vec[i].first ^= vec[j - 1].first;
                    vec[i].second ^= vec[j - 1].second;
                }
            }
        }

        for (int i = n - 2; i >= 0; i--) {
            for (int j = n; j > i + 1; j--) {
                if (vec[i].first.test(j)) {
                    vec[i].first ^= vec[j - 1].first;
                    vec[i].second ^= vec[j - 1].second;
                }
            }
        }

        std::cout << "! ";
        for (int i = 1; i < n; i++) std::cout << vec[i].second << ' ';
        std::cout << std::endl;
    }
}; // namespace solver

void dfs(int l, int u, int fa, bs &mask, int dep) {
    mask.set(u);
    if (dep == k) {
        if (l <= u) solver::insert(mask, l, u);
        mask.reset(u);
        return;
    }
    for (auto v : g[u]) {
        if (v == fa) continue;
        dfs(l, v, u, mask, dep + 1);
    }
    mask.reset(u);
}

int main() {
    std::cin >> n >> k;
    for (int i = 1, u, v; i < n; i++) {
        std::cin >> u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }

    [&] {
        bs tmp;
        tmp.set(1);
        vis[1] = true;
        solver::B[1] = tmp;
        solver::val[1] = tmp;
        solver::cnt++;
    }();

    for (int i = 1; i <= n; i++) {
        bs M;
        dfs(i, i, 0, M, 0);
    }

    if (solver::check()) {
        std::cout << "YES" << std::endl;
        std::cout << "? " << n - 1 << " ";
        for (int i = 2; i <= n; i++) std::cout << solver::seg[i].first << " " << solver::seg[i].second << " ";
        std::cout << std::endl;

        solver::res[1] = 0;
        for (int i = 2; i <= n; i++) std::cin >> solver::res[i];

        std::vector<std::pair<bs, int>> vec;
        for (int i = 1; i <= n; i++) vec.push_back({solver::val[i], solver::res[i]});

        solver::solve(vec);
    } else std::cout << "NO" << std::endl;
}

G - GCD

有点神奇……

赛时看到 aa 比较小，所以猜测暴力 BFS 搜索的时间复杂度是正确的. 但是不会证明… 当然也确实过了

AC 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
#include <bits/stdc++.h>
using ll = long long;

ll a, b;

void run() {
    std::cin >> a >> b;
    auto reduce = [&](ll &x, ll &y) {
        ll g = std::gcd(x, y);
        x /= g, y /= g;
    };
    ll g = std::gcd(a, b);
    a /= g, b /= g;

    std::queue<std::tuple<ll, ll, ll>> q;
    q.push({a, b, 0});
    ll ans = 0;
    while (!q.empty()) {
        auto [x, y, c] = q.front();
        q.pop();
        if (y % x == 0) {
            std::cout << 2 + c << "\n";
            return;
        }
        reduce(x, y);
        q.push({x - 1, y, c + 1}), q.push({x, y - 1, c + 1});
    }
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0), std::cout.tie(0);
    int t;
    std::cin >> t;
    while (t--) run();
}

H - Horizon Scanning

挺签到的，极角排序完后，算出连续 k+1k+1 个点的极角差，取 max⁡\max.

AC 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
#include <bits/stdc++.h>
using ll = long long;
constexpr int N = 2e5 + 10;
constexpr double pi = 3.14159265358979323846;

struct point {
    ll x, y;
    double ang;
    double scale() const { return std::sqrt(1.0 * (x * x + y * y)); }
};

point p[N * 2];
int n, k;

int sign(ll t) { return t > 0 ? 1 : (t == 0 ? 0 : -1); }

void run() {
    std::cout << std::setprecision(10) << std::fixed;
    std::cin >> n >> k;
    for (int i = 1, a, b; i <= n; i++) {
        std::cin >> a >> b;
        p[i] = {a, b};
        p[i].ang = std::atan2(b * 1.0, a * 1.0);
    }

    if (n == k) {
        std::cout << 2 * pi << "\n";
        return;
    }

    std::sort(p + 1, p + 1 + n, [&](point &a, point &b) { return a.ang < b.ang; });
    for (int i = 1; i <= n; i++) p[i + n] = p[i], p[i + n].ang += 2 * pi;

    double ans = 0;
    for (int i = k + 1; i <= 2 * n; i++) ans = std::max(ans, p[i].ang - p[i - k].ang);
    std::cout << ans << "\n";
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0), std::cout.tie(0);
    int t;
    std::cin >> t;
    while (t--) run();
}

J - Just another Sorting Problem

L - Last Chance: Threads of Despair

挺麻烦的一道题.

我们发现，先爆炸再攻击和先攻击再爆炸的最终效果是等价的. 所以，我们考虑维护爆炸伤害 BB（初始为 00）和剩余的主动攻击次数 cc.

  • 如果爆炸伤害已经超过了随从的血量，那么我们就不需要额外地去攻击，且由于随从死亡，爆炸伤害 +1+1.
  • 如果己方随从的血量 hi−1≤Bh_i-1\le B 说明我只需要让这个随从攻击一次就可以故意让他死亡，进而触发爆炸.
  • 如果敌方随从血量 h≥Bh\ge B
    • 如果己方随从可以在 cc 次攻击内把其血线打进爆炸伤害范围里，那么这个随从也可以被炸死.
    • 反之，这个随从就永远死不掉了. 无解

所以，我们只需要对随从血量进行排序，然后双指针即可.

AC 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
#include <bits/stdc++.h>
constexpr int N = 5e5 + 10;
using ll = long long;

ll n, m, a[N], b[N];

void run() {
    std::cin >> n >> m;
    int atk = 0;
    for (int i = 1; i <= n; i++) std::cin >> a[i], atk += a[i] != 1;
    for (int i = 1; i <= m; i++) std::cin >> b[i];
    atk += (atk != n);

    std::sort(a + 1, a + 1 + n);
    std::sort(b + 1, b + 1 + m);

    ll boom = 0;
    int p1 = 1, p2 = 1;
    while (true) {
        if (p1 <= n && a[p1] <= boom) {
            p1++, boom++;
            continue;
        }
        if (p2 <= m && b[p2] <= boom) {
            p2++, boom++;
            continue;
        }

        if (p1 <= n && a[p1] - 1 <= boom) {
            p1++, boom++;
            continue;
        }
        if (p2 <= m && b[p2] - atk <= boom) {
            int at = b[p2] - boom;
            atk -= at;
            p2++, boom++;
            continue;
        } else if (p2 <= m && b[p2] - atk > boom) {
            std::cout << "NO\n";
            return;
        }
        break;
    }

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

int main() {
    std::cin.tie(0)->sync_with_stdio(0), std::cout.tie(0);
    int t;
    std::cin >> t;
    while (t--) run();
}

M - Matrix Construction

对角线方向斜着填即可.

AC 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
#include <bits/stdc++.h>
#include <cstdio>
constexpr int N = 1005;

int n, m;
int g[N][N];

void run() {
    std::cin >> n >> m;
    int t = 1;
    for (int sum = 2; sum <= n + m; sum++) {
        for (int i = 1; i <= n; i++) {
            int j = sum - i;
            if (1 <= j && j <= m) g[i][j] = t++;
        }
    }

    std::cout << "YES\n";
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) std::cout << g[i][j] << " \n"[j == m];
    }
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0), std::cout.tie(0);
    int t;
    std::cin >> t;
    while (t--) run();
}
ICPC/Asia EC/2024 ICPC/NTU Training
License

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。