Practice.

A. Yes-Yes?

题意

给定一个字符串，判断其是否是 \(YESYESYES...\) 的连续子串。

思路

判断多出的前缀是否满足条件，若满足条件，以 \(3\) 个字符为一组匹配 \(YES\)。剩余的后缀特判即可。

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

对应AC代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        int n;
        string s;
        cin >> s;
        n = (int) s.size();
        int i = 0;
        if(s[i] != 'Y'){
            if(s[i] == 'e' && (n == 1 || s[i + 1] == 's')) i = 2;
            else if(s[i] == 's') i = 1;
            else i = -1;
        }
        if(i != -1) for(;i<n;i+=3){
            if(s[i] == 'Y' && (i + 1 >= n || s[i + 1] == 'e') && (i  +2 >= n || s[i + 2] == 's')) continue;
            i = -1;
            break;
        }
        cout << (i == -1 ? "NO\n" : "YES\n");
    }
    return 0;
}

读题即可

B. Lost Permutation

题意

给定一个丢失了部分元素的排列，丢失的元素的总和为 \(s\)，输出是否能补全该排列。

思路

模拟即可。

我们遍历一遍，找出当前最大值之前的空位，去掉这些空位后，若 \(s\) 还有剩余，那么继续从最大值 \(+1\) 往下遍历，若能将 \(s\) 恰好减为 \(0\)，输出 \(YES\)。

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

对应AC代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1010;

bool a[N];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        int n, s;
        cin >> n >> s;
        memset(a, 0, sizeof a);
        int maxx = -1;
        for(int i=0;i<n;i++){
            int cur;
            cin >> cur;
            a[cur] = true;
            maxx = max(maxx, cur);
        }
        int tot = 0;
        for(int i=1;i<=maxx;i++)
            if(!a[i]) tot += i;
        if(tot > s) cout << "NO\n";
        else{
            int i = maxx + 1;
            while(tot < s){
                tot += i ++;
            }
            cout << (tot == s ? "YES\n" : "NO\n");
        }
    }
    return 0;
}

模拟就完事了

C. Thermostat

题意

给定一段区间 \([l, r]\)，区间内有两个点 \(a, b\)，定义一次操作为将当前位置加上或减去 \(p\)，\(p \geq x\)，操作后的数需要落在区间内。输出从 \(a\) 运动到 \(b\) 需要的最少操作数。

思路

显然，最多只需进行 \(3\) 次操作。

考虑到对称性，我们不妨来考虑 \(l \leq a \leq b \leq r\) 的情况，分类讨论一下：

无需操作，此时 \(a = b\)；
操作一次，此时应满足 \(b - a \geq x\)；
操作两次，此时我们可以向两端移动，只需任意一个满足即可。若向 \(l\) 移动，那么向下移动需要满足 \(a - l \geq x\)，考虑到步数只需大于等于 \(x\)，我们可以直接移动到 \(l\)，然后移动到 \(b\)。因为 \(l\) 到 \(b\) 的距离大于 \(l\) 到 \(a\) 的距离，那么我们无需多考虑。而向 \(r\) 移动时，在满足 \(r - a \geq x\) 的前提下，还需满足能运动到 \(b\)，即 \(r - a \geq x + \min(b - a, x)\)。
操作三次，相类似地，我们可以得到下面的式子：向 \(r\) 移动，\(r - a \geq x\) 、\(b - l \geq x\)；向 \(l\) 移动，\(a - l \geq x\)，\(r - b \geq x\)。

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

对应AC代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1010, inf = 0x3f3f3f3f;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        int a, b, l, r, x;
        cin >> l >> r >> x >> a >> b;
        if(a == b) cout << 0 << '\n';
        else if(abs(b - a) >= x) cout << 1 << '\n';
        else if(a < b){
            int ans1 = inf, ans2 = inf;
            if(a - l >= x || r - a >= x + min(b - a, x)) ans1 = 2;
            if((r - a >= x && b - l >= x) || (a - l >= x && r - b >= x)) ans2 = 3;
            cout << (min(ans1, ans2) == inf ? -1 : min(ans1, ans2)) << '\n';
        }else{
            int ans1 = inf, ans2 = inf;
            if(r - a >= x || a - l >= x + min(a - b, x)) ans1 = 2;
            if((a - l >= x && r - b >= x) || (r - a >= x && b - l >= x)) ans2 = 3;
            cout << (min(ans1, ans2) == inf ? -1 : min(ans1, ans2)) << '\n';
        }
    }
    return 0;
}

讨论死我了

D. Make It Round

题意

给定两个整数 \(n, m\)，找出 \(k \in [1, m]\)，使 \(n \times k\) 连续后缀 \(0\) 的个数最多。若有多解，输出最大的；若无解，输出 \(n \times m\)。

思路

考虑到 \(10\) 的质因子为 \(2, 5\)，我们不妨将 \(n\) 后面连续的 \(0\) 都去掉，然后统计 \(n\) 中因数 \(2, 5\) 的个数，并尽量在答案中用对应的 \(5, 2\) 与之配对，然后在答案最后尽可能拼上 \(0\)。最后得到的答案即为 \(0\) 个数最多的，因为存在多解，我们将答案乘上 \(m / ans\)。

时间复杂度：不会分析

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main(){
    ios::sync_with_stdio(false);
    int t, n, m;
    cin >> t;
    while(t --){
        cin >> n >> m;
        int ans = 1, p = n;
        while(p % 10 == 0) p /= 10;
        while(p % 2 == 0 && ans * 5 <= m){
            p /= 2;
            ans *= 5;
        }
        while(p % 5 == 0 && ans * 2 <= m){
            p /= 5;
            ans *= 2;
        }
        while(ans * 10 <= m) ans *= 10;
        cout << m / ans * n * ans << '\n';
    }
}

配对配对，贪一下嘛~

E. The Humanoid

题意

给定 \(n\) 个人，每个人有能力值 \(a_i\)。对于一个初始攻击力为 \(h\) 的怪物，它可以干掉所有 \(a_i < h\) 的人，并将自己的攻击力提高 \(\lceil \frac{a_i}{2} \rceil\)。怪物有两个道具，道具一总数为 \(2\)，可以将攻击力翻倍；道具二总数为 \(1\)，可以将攻击力变为原来的三倍。道具使用后消失。输出怪物可以干掉的最多人数。

思路

显然，若想让后续能倍乘的基数变得更大，我们就可以贪心地按能力值升序排序人，这样在需要道具的时候，就能获得尽可能多的攻击力。

然而，使用哪个道具是不确定的，虽然 \(3\) 翻的倍数最多，但放在前面还是后面是不确定的。

考虑到道具只有 \(3\) 个，我们不妨枚举道具使用的顺序，然后用递归解决即可。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5 + 10;

int a[N], n;

int cal(int b, int i, int use, int h){
    if(i == n) return 0;
    if(a[i] < h) return cal(b, i + 1, use, h + a[i] / 2) + 1;
    else{
        if(use == 3) return 0;
        return cal(b, i, use + 1, h * (b == use ? 3 : 2));
    }
}

signed main(){
    ios::sync_with_stdio(false);
    int t, h;
    cin >> t;
    while(t --){
        cin >> n >> h;
        for(int i=0;i<n;i++) cin >> a[i];
        sort(a, a + n);
        int ans = 0;
        for(int i=0;i<3;i++)
            ans = max(ans, cal(i, 0, 0, h));
        cout << ans << '\n';
    }
}

一开始错在道具的使用顺序上了，不可以贪心地使用当前能用的最小的翻倍数