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\),修改后求上述答案,修改持久化。

解题思路

<++>

神奇的代码



热门相关:我在镇夜司打开地狱之门   寒门状元   嫂子是温泉爱好者   首辅娇娘   重生不嫁豪门