ABC363

V_Melville's memory / 2024-07-21 / 原文

A. Piling Up

模拟

代码实现

r = int(input())
ans = 100-r%100
print(ans)

B. Japanese Cursed Doll

模拟

代码实现

#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

int main() {
    int n, t, p;
    cin >> n >> t >> p;
    
    vector<int> l(n);
    rep(i, n) cin >> l[i];
    
    int day = 0;
    while (true) {
        int cnt = 0;
        rep(i, n) {
            if (l[i] >= t) cnt++;
        }
        if (cnt >= p) {
            cout << day << '\n';
            return 0;
        }
        
        rep(i, n) l[i]++;
        day++;
    }
    
    return 0;
}

C. Avoid K Palindrome 2

暴搜

先对 $S$ 做排序得到字典序最小的排列，然后利用C++ std::next_permutation 这个内置函数，这个函数有一个自动去重的功能比较方便，相对地，Python的 itertools.permutations 函数就不具备这个去重功能

代码实现

#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

int main() {
    int n, k;
    string s;
    cin >> n >> k >> s;
    
    ranges::sort(s);
    
    int ans = 0;
    do {
        bool ok = true;
        rep(i, n-k+1) {
            string t = s.substr(i, k);
            string rt = t;
            ranges::reverse(rt);
            if (t == rt) ok = false;
        }
        if (ok) ans++;
    } while (next_permutation(s.begin(), s.end()));
    
    cout << ans << '\n';
    
    return 0;
}

D. Palindromic Number

原题：poj2402

不妨设 $0$ 是 $0$ 位数
$0$ 位数中有 $1$ 个回文数
$1$ 位数中有 $9$ 个回文数
$2$ 位数中有 $9$ 个回文数
$3$ 位数中有 $90$ 个回文数
$4$ 位数中有 $90$ 个回文数
$5$ 位数中有 $900$ 个回文数
$6$ 位数中有 $900$ 个回文数
$\ \ \vdots$

通过 $n$ 我们可以推出答案的位数

由于题目中要求不能有前导0，所以第一个数有 $9$ 种取法
然后对位数的奇偶性进行讨论：
当位数为偶数时，前一半数位上的数和后一半数位上的数对应相等
当位数为奇数时，中间的数左半数位上的数和它右半数位上的数对应相等

代码实现

#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

int main() {
    ll n;
    cin >> n;
    
    if (n == 1) {
        puts("0");
        return 0;
    }
    n--;
    
    for (int keta = 1;;++keta) {
        int l = (keta+1)/2;
        ll num = 9;
        rep(i, l-1) num *= 10;
        if (n > num) {
            n -= num;
            continue;
        }
        
        // 1 : num/9
        n += num/9-1;
        string s = to_string(n);
        string rs = s;
        ranges::reverse(rs);
        if (keta%2 == 1) s.pop_back();
        s += rs;
        cout << s << '\n';
        return 0;
    }
    
    return 0;
}