AtCoder Beginner Contest 321-526互联

A - 321-like Checker (abc321 A)

题目大意

给定一个数，问从高位到低位，数字是不是递减的。

解题思路

可以以字符串读入，然后依次判断即可。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin >> s;
    auto ok = [&]() {
        for (int i = 0; i < s.size() - 1; ++i) {
            if (s[i + 1] >= s[i])
                return false;
        }
        return true;
    };
    if (ok())
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';

    return 0;
}

B - Cutoff (abc321 B)

题目大意

给定\(n-1\)个数字，问最后一个数字最少是多少，使得你的分数不小于 \(x\)。

数字在 \([0,100]\)之间。分数是去掉最低最高后的和。

解题思路

因为范围不大，直接枚举最后一个数，找最大最小，然后求分数判断即可。时间复杂度是\(O(100^3)\)

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, x;
    cin >> n >> x;
    vector<int> a(n);
    for (int i = 0; i < n - 1; ++i)
        cin >> a[i];
    int ans = 0;
    auto ok = [&]() {
        auto tmp = a;
        sort(tmp.begin(), tmp.end());
        int sum =
            accumulate(tmp.begin(), tmp.end(), 0) - tmp.front() - tmp.back();
        return sum >= x;
    };
    for (; ans <= 100; ++ans) {
        a[n - 1] = ans;
        if (ok())
            break;
    }
    if (ans == 101)
        ans = -1;
    cout << ans << '\n';

    return 0;
}

C - 321-like Searcher (abc321 C)

题目大意

给定\(k\)，问\(321-like\)的第 \(k\)小的数是多少。

\(321-like\)就是第一题的定义，从高位到低位逐数字递减。

解题思路

最大的是\(9876543210\)，可以猜测数不多，直接搜索全部数出来，然后排序看第\(k\) 个是多少即可。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int k;
    cin >> k;
    LL s = 0;
    vector<LL> ans;
    function<void(int)> dfs = [&](int x) {
        s = s * 10 + x;
        ans.push_back(s);
        for (int i = x - 1; i >= 0; --i)
            dfs(i);
        s /= 10;
    };
    for (int i = 9; i >= 0; --i) {
        dfs(i);
    }
    sort(ans.begin(), ans.end());
    cout << ans[k] << '\n';

    return 0;
}

题目大意

给定两个数组\(a,b\)和一个数\(p\)，各从中取一个数\(x,y\)，得到贡献 \(\min(x+y, p)\) 。问所有取法的贡献和。

解题思路

对数组\(b\)排序，枚举数组 \(a\)，那么小于 \(p-a\)的 \(b\)的贡献是 \(a+b\)，其余的贡献是 \(p\)，因此二分找到这个界限，分别计算这两类的贡献和即可，前者是个关于\(b\)的前缀和，后者就是一个数组\(b\)中 \(\geq p-a\)的数量的统计。时间复杂度是 \(O(n\log m)\)。

也可以对\(a,b\)都排序，此时\(a\)枚举从大到小， \(b\)枚举从小到大，双指针也行。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    LL p;
    cin >> n >> m >> p;
    vector<LL> a(n), b(m);
    vector<LL> sumb(m);
    for (auto& i : a)
        cin >> i;
    for (auto& i : b)
        cin >> i;
    sort(b.begin(), b.end());
    partial_sum(b.begin(), b.end(), sumb.begin());
    LL ans = 0;
    for (auto& i : a) {
        LL r = p - i;
        auto cnt = lower_bound(b.begin(), b.end(), r) - b.begin();
        ans += 1ll * i * cnt + (cnt ? sumb[cnt - 1] : 0) + 1ll * p * (m - cnt);
    }
    cout << ans << '\n';

    return 0;
}

E - Complete Binary Tree (abc321 E)

题目大意

给定一棵完全二叉树，问与点\(x\)的距离为\(k\)的个数。

有 \(t\)组。

解题思路

示例图

考虑点\(5\)距离为 \(k\)的点都在哪。

首先在以该点的子树内，深度为 \(k\)的点有 \(2^k\)（起始为\(0\)），对应的标号都可以求出来，这样可以判断在\(n\)内的标号有多少个。

然后考虑该点的父亲的另一个节点（点\(4\)）的子树内，此时我们要求的深度是 \(2^{k-2}\)的点的个数。

然后考虑该点的父亲的父亲的另一个节点（点\(3\)）的子树内，此时我们要求的深度是\(2^{k-3}\)的点的个数。

不断往父亲考虑，因为每次往父亲走，点标号都会除以 \(2\)，最多 \(\log\)次就考虑完了。

总的复杂度是 \(O(t\log n)\)

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;

    auto solve = [&](LL x, LL k, LL n) {
        if (k < 0)
            return 0ll;
        if (k >= 64)
            return 0ll;
        __int128 num = (1ll << k), l = x;
        l = (l << k);
        __int128 r = l + num - 1;
        if (l > n)
            return 0ll;
        LL ret = min(r, (__int128)n) - l + 1;
        return ret;
    };
    while (t--) {
        LL n, x, k;
        cin >> n >> x >> k;
        LL ans = 0;
        if (k)
            ans += solve(x, k, n);
        while (x > 1 && k > 0) {
            --k;
            ans += solve((x ^ 1), k - 1, n);
            x /= 2;
        }
        if (x && k == 0)
            ans++;
        cout << ans << '\n';
    }

    return 0;
}

F - #(subset sum = K) with Add and Erase (abc321 F)

题目大意

箱子，放球，拿球，球上有数，各不相同。

每次操作后，问里面球数和为\(k\)的方案数。

解题思路

不考虑拿走球的操作，每次放球，求方案数，就是一个经典的\(0/1\)背包。

设 \(dp[i]\)表示和为 \(j\)的方案数，考虑选不选这个球（其数字为\(x\)），则有 \(dp[i] = dp[i] + dp[i - x]\)

现在拿走这个球，得从中剔除选了这个球的方案数。

设\(dp2[i]\)表示不选该球，和为 \(i\)的方案数。由于 \(dp[i]\)的方案包括两部分：选了该球和没选该球的。只要减去选了该球的方案数，那就是没选该球的方案数。而选了该球的方案数，其实就是 \(dp2[i-x]\)，即选了这个球后，剩下的 \(i-x\)就是由不选该球的方案数组成，这恰好是我们定义的 \(dp2[i-x]\)的定义。

于是 \(dp2[i] = dp[i] - dp2[i - x]\)转移式即可。

时间复杂度是 \(O(qn)\)。

这其实是最经典的退背包问题。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int mo = 998244353;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int q, k;
    cin >> q >> k;
    vector<int> dp(k + 1, 0);
    dp[0] = 1;
    while (q--) {
        string op;
        int x;
        cin >> op >> x;
        if (op[0] == '+') {
            for (int i = k; i >= x; --i) {
                dp[i] += dp[i - x];
                if (dp[i] >= mo)
                    dp[i] -= mo;
            }
        } else {
            vector<int> dp2(k + 1, 0);
            for (int i = 0; i <= k; ++i) {
                if (i < x) {
                    dp2[i] = dp[i];
                } else {
                    dp2[i] = dp[i] - dp2[i - x];
                    if (dp2[i] < 0)
                        dp2[i] += mo;
                }
            }
            dp.swap(dp2);
        }
        cout << dp[k] << '\n';
    }

    return 0;
}