AtCoder Beginner Contest 363-摩杜云开发者社区

上周去玩了（逃

A - Piling Up (abc363 A)

题目大意

给定分数，问晋级还差多少分。分别到\(100,200,300\)分能晋级。

解题思路

找到第一个大于当前分数的，其差即为答案。

神奇的代码

#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 a;
    cin >> a;
    vector<int> rk{100, 200, 300};
    auto it = upper_bound(rk.begin(), rk.end(), a);
    int ans = *it - a;
    cout << ans << '\n';

    return 0;
}

B - Japanese Cursed Doll (abc363 B)

题目大意

给定\(n\)个人的头发长度，每天会涨\(1\)厘米。问至少经过多少天，有至少\(P\)个人的头发长度至少是\(T\)。

解题思路

由于头发都是一起涨的，将头发长度从长到短排序，当第\(P\)个人的头发涨到\(T\)时，前\(P-1\)个也至少是\(T\)了。所以答案就是第\(P\)个人的头发涨到\(T\)的时间。

神奇的代码

#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, t, p;
    cin >> n >> t >> p;
    vector<int> a(n);
    for (auto& x : a) {
        cin >> x;
    }
    sort(a.begin(), a.end(), greater<int>());
    int ans = max(0, t - a[p - 1]);
    cout << ans << '\n';

    return 0;
}

C - Avoid K Palindrome 2 (abc363 C)

题目大意

给定一个字符串，将字母排序，问有多少种情况，其不存在一个长度为\(k\)的回文串。

解题思路

字符串长度\(n\)只有\(10\)，花\(O(10!)\)枚举所有的排列情况，然后花\(O(n)\)枚举子串，再花\(O(k)\)判断是否是回文串即可。时间复杂度是\(O(n!nk)\)

神奇的代码

#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, k;
    string s;
    cin >> n >> k >> s;
    int ans = 0;
    auto ispalindrome = [&](string&& s) -> bool {
        auto t = s;
        reverse(t.begin(), t.end());
        return t == s;
    };
    auto check = [&](string s) -> bool {
        for (int i = 0; i <= n - k; i++) {
            if (ispalindrome(s.substr(i, k))) {
                return false;
            }
        }
        return true;
    };
    sort(s.begin(), s.end());
    do {
        ans += check(s);
    } while (next_permutation(s.begin(), s.end()));
    cout << ans << '\n';

    return 0;
}

D - Palindromic Number (abc363 D)

题目大意

求第\(n\)小的回文数字。

解题思路

观察回文数字，按长度分奇数和偶数两种情况。

1 2 3 4 5 6 7 8 9
11 22 33 44 55 66 77 88 99
101 111 121 131 141 151 ... 191
202 212 222 232 242 252 ... 292
...
909 919 929 939 949 959 ... 999
1001 1111 1221 1331 1441 ... 1991
2002 2112 2222 2332 2442 ... 2992
...
9009 9119 9229 9339 9449 ... 9999

由于是前后是对称的，由于数的比较是从高位比较，我们可以把右半部分的低位忽略，这样就变成

1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 ... 19
20 21 22 23 24 25 ... 29
...
90 91 92 93 94 95 ... 99
10 11 12 13 14 15 ... 19
20 21 22 23 24 25 ... 29
...
90 91 92 93 94 95 ... 99

长度是奇偶循环的，去除右半部分，容易发现它就是

1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 ... 90 91 92 93 94 95 96 97 98 99
100 101 .......

每行(即一个长度)多出现一次。而依次每个长度的数量分别是\(9,99,999,9999......\)。

因此通过\(n\)，得知道第\(n\)个数的长度，以及是该长度的奇还是偶。如何知道长度，枚举即可，其长度不会超过\(O(\log n)\)。

知道该长度后，就知道该长度有多少个数字\(p\)，再通过\(n \geq p\)来判断是偶数情况还是奇数情况，\(n \% p\)就是对应的数了。这里的\(n\)是减去小的长度后的值，即从\(1000\)（如果长度是\(4\)）开始数的第几个数。

代码中 s=to_string(n % p + p / 9)，其中\(p/9\)是因为数是从\(1000\)开始的，而不是\(0000\)开始。

特判一下\(0\)。

神奇的代码

#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);
    LL n;
    cin >> n;
    if (n == 1) {
        cout << "0\n";
        return 0;
    }
    n -= 2;
    LL p = 9;
    while (n >= 2 * p) {
        n -= 2 * p;
        p *= 10;
    }
    auto s = to_string(n % p + p / 9);
    auto t = s;
    reverse(t.begin(), t.end());
    if (n < p)
        s.pop_back();
    auto ans = s + t;
    cout << ans << '\n';

    return 0;
}

E - Sinking Land (abc363 E)

题目大意

方格岛，四面环海。

给出岛的高度，每年海平面上升\(1\)。

问\(y\)年的每一年，没被淹的岛的数量。

解题思路

起初是四周的岛可能会被淹，称之为危险岛，我们需要比较危险岛的高度和海平面高度。

因为越矮的岛越容易被淹，我们优先比较危险岛的高度最低的，如果被淹了，则会新增一些危险岛，然后继续比较高度最低的，直到没被淹。

因此用优先队列维护这些危险岛的高度，当有新的危险岛被淹时，新增周围变成危险岛的高度，模拟即可。

时间复杂度为\(O(hw\log hw)\)

神奇的代码

#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 h, w, y;
    cin >> h >> w >> y;
    vector<vector<int>> a(h, vector<int>(w));
    for (auto& i : a)
        for (auto& j : i)
            cin >> j;
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>,
                   greater<tuple<int, int, int>>>
        pq;
    vector<vector<int>> vis(h, vector<int>(w, 0));
    auto push = [&](int x, int y) {
        if (x >= 0 && x < h && y >= 0 && y < w && !vis[x][y]) {
            vis[x][y] = 1;
            pq.push({a[x][y], x, y});
        }
    };
    for (int i = 0; i < h; i++) {
        push(i, 0);
        push(i, w - 1);
    }
    for (int i = 0; i < w; i++) {
        push(0, i);
        push(h - 1, i);
    }
    array<int, 4> dx = {0, 0, 1, -1};
    array<int, 4> dy = {1, -1, 0, 0};
    int ans = h * w;
    for (int i = 1; i <= y; i++) {
        while (!pq.empty()) {
            auto [v, x, y] = pq.top();
            if (v <= i) {
                pq.pop();
                ans--;
                for (int j = 0; j < 4; j++) {
                    int nx = x + dx[j];
                    int ny = y + dy[j];
                    push(nx, ny);
                }
            } else {
                break;
            }
        }
        cout << ans << '\n';
    }

    return 0;
}

F - Palindromic Expression (abc363 F)

题目大意

给定\(n\)，将\(n\)拆成若干个数相乘的表达式，其中这个表达式是个回文串，且不存在数字\(0\)。

解题思路

考虑朴素搜索，每个表达式的每个乘数必定是\(n\)的因子，因此我们事先预处理出\(n\)的所有因子，分析可知我们只需预处理\(< \sqrt{n}\)的因子即可，大于\(\sqrt{n}\)的因子要么其回文数\(< \sqrt{n}\)，要么两个数乘起来会\(> n\)了。

然后就枚举乘数是什么，即枚举\(n\)的因子\(x\)，然后求其回文数字\(y\)，判断\(x\)和\(xy\)是否都是\(n\)的因子。是的话，则就是\(n = x * \frac{n}{xy} * y\)，接下来就是判断\(\frac{n}{xy}\)能否表示成一个回文表达式，这就是一个子问题了，记忆化搜索一下即可。

考虑其复杂度，搜索状态的\(n\)的取值只有因数个，每次搜索枚举因数，因此总的时间复杂度是\(O(\sigma^2(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);
    LL n;
    cin >> n;
    vector<int> fac;
    for (LL i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            fac.push_back(i);
        }
    }
    map<LL, pair<LL, LL>> dp;
    auto rev = [](LL x) {
        string s = to_string(x);
        reverse(s.begin(), s.end());
        return stoll(s);
    };
    auto is_palindromic = [&](LL x) { return x == rev(x); };
    auto is_valid = [&](LL x) {
        return to_string(x).find('0') == string::npos;
    };
    auto dfs = [&](auto dfs, LL n) -> bool {
        if (is_valid(n) && is_palindromic(n))
            return true;
        if (dp.count(n))
            return true;
        for (auto& x : fac) {
            auto y = rev(x);
            if (n % x == 0 && n / x % y == 0 && is_valid(x) && is_valid(y) &&
                dfs(dfs, n / x / y)) {
                dp[n] = {x, y};
                return true;
            }
        }
        return false;
    };
    dfs(dfs, n);
    if (dp.empty() && (!is_valid(n) || !is_palindromic(n)))
        cout << -1 << '\n';
    else {
        string ansl, ansr;
        while (dp.count(n)) {
            auto [x, y] = dp[n];
            ansr = ansr + "*" + to_string(x);
            ansl = to_string(y) + "*" + ansl;
            n /= x;
            n /= y;
        }
        string ans = ansl + to_string(n) + ansr;
        cout << ans << '\n';
    }

    return 0;
}

G - Dynamic Scheduling (abc363 G)

题目大意

给定\(n\)个任务的截止完成时间\(d_i\)和奖励\(p_i\)，指如果该任务能在\(d_i\)之前完成，则能获得奖励\(p_i\)。

决定每天完成什么任务，使得奖励最大化。

维护\(q\)次操作，每次操作修改一个任务的\(d_i\)和\(p_i\)，修改后求上述答案，修改持久化。

解题思路

<++>

神奇的代码