0%

Codeforces - Round 834 Div 3

Practice.

A. Yes-Yes?

题意

给定一个字符串,判断其是否是 的连续子串。

思路

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

时间复杂度:

对应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

题意

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

思路

模拟即可。

我们遍历一遍,找出当前最大值之前的空位,去掉这些空位后,若 还有剩余,那么继续从最大值 往下遍历,若能将 恰好减为 ,输出

时间复杂度:

对应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

题意

给定一段区间 ,区间内有两个点 ,定义一次操作为将当前位置加上或减去 ,操作后的数需要落在区间内。输出从 运动到 需要的最少操作数。

思路

显然,最多只需进行 次操作。

考虑到对称性,我们不妨来考虑 的情况,分类讨论一下:

  1. 无需操作,此时

  2. 操作一次,此时应满足

  3. 操作两次,此时我们可以向两端移动,只需任意一个满足即可。若向 移动,那么向下移动需要满足 ,考虑到步数只需大于等于 ,我们可以直接移动到 ,然后移动到 。因为 的距离大于 的距离,那么我们无需多考虑。而向 移动时,在满足 的前提下,还需满足能运动到 ,即

  4. 操作三次,相类似地,我们可以得到下面的式子:向 移动,;向 移动,

时间复杂度:

对应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

题意

给定两个整数 ,找出 ,使 连续后缀 的个数最多。若有多解,输出最大的;若无解,输出

思路

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

时间复杂度:不会分析

对应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

题意

给定 个人,每个人有能力值 。对于一个初始攻击力为 的怪物,它可以干掉所有 的人,并将自己的攻击力提高 。怪物有两个道具,道具一总数为 ,可以将攻击力翻倍;道具二总数为 ,可以将攻击力变为原来的三倍。道具使用后消失。输出怪物可以干掉的最多人数。

思路

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

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

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

时间复杂度:

对应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';
    }
}

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