Practice.

A. Destroyer

题意

定义每个机器人具有一个参数：它的前面有多少机器人。

机器人可以排成很多行，因而我们可以得到最后的参数序列。

现在，给定打乱后的参数序列，输出是否合法。

思路

很显然，我们只需统计每个参数的出现次数，按照参数升序排序后，如果出现次数不递减，那么就是合法的，否然不合法。

时间复杂度：\(O(n \log n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
    int n;
    cin >> n;
    vector<int> a(110);
    int mx = 0;
    for(int i=0;i<n;i++){
        int cur;
        cin >> cur;
        mx = max(mx, cur);
        a[cur] ++;
    }
    int pre = a[0];
    bool f = true;
    for(int i=1;i<=mx;i++){
        if(a[i] > pre){
            f = false;
            break;
        }
        pre = a[i];
    }
    cout << (f ? "YES\n" : "NO\n");
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

就是题目抽象了点

B. Astrophysicists

题意

给定 \(k\) 个金币，每个金币等价于 \(g\) 个银币。给定 \(n\) 个人，规定需要将所有银币分发给所有人。

对于任意一个人所分发的银币数量 \(x\)，我们定义 \(r = x\mod g\)，按照下面的规则得到盈利/亏损：

如果 \(r \geq \lceil \frac{g}{2} \rceil\)，那么亏损 \(g - r\)；
否则，盈利 \(r\)

输出最后能盈利最多多少钱，如果亏损，输出 \(0\)。

思路

我们不妨不考虑分配的总额，那么最后要让盈利尽可能多，每个人分发 \(\lfloor \frac{g-1}{2} \rfloor\) 即可。

那么，考虑上总额，如果总额不够，依然是盈利的，我们将答案和总额取最小值即可。

但如果总额过多，我们记多出 \(p\) 银币。

因为存在取模操作，因而我们可以把多出的银币全都给一个人。

此时，我们将会失去一个人的盈利，并亏损一部分银币，我们进行分讨即可。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
    int n, k, g;
    cin >> n >> k >> g;
    int ans = min((g - 1) / 2 * n, k * g), left = (k * g - ans) % g;
    if(left > 0){
        ans -= (g - 1) / 2;
        left = (left + (g - 1) / 2) % g;
        if(left < ceil((double) g / 2)) ans += left;
        else ans -= g - left;
    }
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

抽象的，通俗易懂的，巧妙的

C. k-th equality

题意

对于二元加法 \(A + B = C\)，给定 \(A, B, C\) 的位数以及一个整数 \(k\)，输出按字典序排序的满足位数的第 \(k\) 个式子。

思路

首先，第一反应绝对是推式子，但，这题的 \(A,B,C\) 范围小到...可以暴搜。

我们对 \(A\) 爆搜，并统计对于当前 \(A\) 的选择，有多少个对应的式子，以此遍历得到答案。

显然，令 \(x = \max(A, B)\)，我们只有两种情况：\(x = C, x + 1 = C\)，前后者的区别是是否进位，我们分讨即可。

那么，除了这两种情况，其他情况均为无解。

时间复杂度：\(O(n ^ 2)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;

const vector<int> p = {1, 10, 100, 1000, 10000, 100000, 1000000};

void solve() {
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    bool ok = false;
    for(int i = p[a - 1]; i < p[a]; i ++){ //对a爆搜
        int l = max(p[b - 1], p[c - 1] - i),
            r = min(p[b] - 1, p[c] - i - 1);
        if(l > r) continue;
        if(r - l + 1 < k) k -= (r - l + 1);
        else{
            cout << i << " + " << l + k - 1 << " = " << i + l + k - 1 << '\n';
            ok = true;
            break;
        }
    }
    if(!ok) cout << -1 << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

不能爆搜的话得对四种情况分讨，挺麻烦，但好像能做