Codeforces Round 893 (Div. 2)

A - Buttons (CF1858 A)

题目大意

anna和katie轮流按按钮，anna只能按按钮A和C，katie只能按下按钮B和C。不能按下按钮的一方输。求最后谁赢

解题思路

根据峡谷经济学，有中立资源时先控中立资源。

神奇的代码

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    i64 a, b, c;
    std::cin >> a >> b >> c;

    i64 tmp = (c + 1) >> 1;
    a += tmp; b += c - tmp;

    if (a > b) {
        std::cout << "First" << std::endl;
    } else {
        std::cout << "Second" << std::endl;
    }
}

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

    int tt = 1;
    std::cin >> tt;
    while (tt --) solve();

    return 0;
}

B - The Walkway (CF1858 B)

题目大意

太长不写版

解题思路

BC难度反了。注意到每次删掉椅子，贡献最多减一，枚举减掉哪个就行。提前存储下吃饼干的点可以化简复杂度。

神奇的代码

#include <bits/stdc++.h>

using i64 = long long;
using PII = std::pair<int, int>;

void solve() {
    int n, m, d;
    std::cin >> n >> m >> d;

    std::vector<int> a(m + 2);
    a[0] = -d + 1;
    a[m + 1] = n + 1;
    for  (int i = 1;i <= m;i ++) {
        std::cin >> a[i];
    }

    int cnt = 0;
    for (int i = 1;i <= m + 1;i ++) {
        cnt += (a[i] - a[i - 1] - 1) / d;
    }

    int res = (1 << 30), ans = 0;
    for (int i = 1;i <= m;i ++) {
        int tmp = cnt;
        tmp -= (a[i] - a[i - 1] - 1) / d;
        tmp -= (a[i + 1] - a[i] - 1) / d;
        tmp += (a[i + 1] - a[i - 1] - 1) / d;
        tmp += m - 1;
        if (tmp < res) {
            res = tmp;
            ans = 1;
        } else if (res == tmp) {
            ans ++;
        }
    }

    std::cout << res << ' ' << ans << std::endl;
    
}

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

    int tt = 1;
    std::cin >> tt;
    while (tt --) solve();

    return 0;
}

C - Yet Another Permutation Problem (CF1858 C)

题目大意

找到一个排列，使得相邻两个数的gcd的不同个数最多

解题思路

按倍数构造，一眼题。

神奇的代码

#include <bits/stdc++.h>

using i64 = long long;
using PII = std::pair<int, int>;

void solve() {
    int n;
    std::cin >> n;

    std::cout << 1 << ' ';

    std::bitset<100010> vis;
    vis[1] = true;

    for (int i = 2;i <= n;i ++) {
        if (vis[i]) continue;
        for (int j = i;j <= n;j += j) {
            if (!vis[j]) vis[j] = true;
            std::cout << j << ' ';
        }
    }
    
    std::cout << std::endl;
}

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

    int tt = 1;
    std::cin >> tt;
    while (tt --) solve();

    return 0;
}