Codeforces Round 942 (Div. 2)

A. Contest Proposal

大致题意

有两个数组 $a,b$，已经从小到大排序好了，现在往 $a$ 数组最前面再塞入几个值，同时从最后面删除相同数量的值，使得 $\mathrm{\forall }i\in [1,n],a_i\le b_i$

思路

简单题，由于数据量很小，甚至可以暴力

AC code

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (auto &i: a) cin >> i;
    for (auto &i: b) cin >> i;
    int l = 0, r = 0, ans = 0;
    while (l < n && r < n) {
        if (a[l] <= b[r]) {
            ++l;
            ++r;
        } else {
            ++ans;
            ++r;
        }
    }
    cout << ans << endl;
}
CPP

B. Coin Games

大致题意

有两个人做游戏，有几个英镑再桌面上，有些正面朝上有些背面朝上。

每次操作，允许移走一个正面朝上的，然后连续选择两个剩下的影片进行翻转

问谁会操作到最后一次

思路

翻转两个硬币等于没有翻转

AC code

void solve() {
    int n;
    cin >> n;
    string str;
    str.resize(n);
    cin >> str;
    int cnt = 0;
    for (const auto& c: str) cnt += c == 'U';
    cout << (cnt % 2 ? "YES" : "NO") << endl;
}
CPP

C. Permutation Counting

大致题意

有 $$ 种卡片，每种都有一定数量，现在允许额外再增加 $$ 张，使得这些卡片可以组成一个数组，数组种的存在的 $$ 的排列的子串尽可能多，问可以有多少个

思路

只需要 $$ 类似这样排列即可，通过二分找出每个数值都能到达的数量，然后排列起来

然后是剩下的那部分，比如多了一个 $$，那么按照上面的排列方式，将 $$ 放在最后面还能再多一次，即每有一个多出来的种类，就能增加一个子串

AC code

#define int long long

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> data(n);
    for (auto &i: data) cin >> i;
    auto check = [&](int x) {
        int use = 0;
        for (const auto &v: data) {
            if (v < x) use += x - v;
            if (use > k) break;
        }
        return use <= k;
    };

    int l = 0, r = 1e15;
    while (l + 1 < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) l = mid;
        else r = mid;
    }
    int ans = 0, use = k;
    for (const auto& v: data) {
        if (v > l) ++ans;
        else use -= l - v;
    }
    ans = min(n, use + ans);

    cout << ans + (l - 1) * n + 1 << endl;
}
CPP

D1. Reverse Card (Easy Version)

大致题意

给出 $$，求满足条件的 $$ 对

• $$
• $$

思路

假定 $$，且 $$
则可以得到

$$

容易得到，必然 $$ 是整数，而 $$，所以 $$，故 $$

所以很容易得到公式进行计算

AC code

#define int long long

void solve() {
    int n, m, ans = 0;
    cin >> n >> m;
    for (int i = 1; i <= n && i <= m; ++i) {
        int my = n / i;
        ans += (my + 1) / i;
    }
    cout << ans - 1 << endl;
}
CPP

D2. Reverse Card (Hard Version)

大致题意

给出 $$，求满足条件的 $$ 对

• $$
• $$

思路

假定 $$，且 $$
则可以得到

$$

容易得到，必然 $$ 是整数，而 $$，所以必然只能用 $$ 来承接除过来的 $$，即上述公式中的表达

所以可以根据公式得到，只需要找到合理的互质数 $$，即可找出有多少个 $$ 满足条件，因为 $$ 可以是任意值，即 $$ 是 $$ 的倍数

AC code

#define int long long

void solve() {
    int n, m, ans = 0;
    cin >> n >> m;
    if (n < 2 || m < 2) {
        cout << 0 << endl;
        return;
    }

    function<int(int, int)> gcd = [&](int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    };

    for (int i = 1; i * i <= n; ++i) {
        for (int j = 1; j * j <= m; ++j) {
            if (gcd(i, j) != 1) continue;

            ans += min(n / i, m / j) / (i + j);
        }
    }
    cout << ans << endl;
}
CPP