0%

Codeforces - Round 838 Div 2

Practice.

A. Divide and Conquer

题意

给定一个数组 ,定义操作为选定一个元素并将其除 后向下取整,输出最少操作数,使整个数组的和为奇数。

思路

考虑到数据量比较小,我们不妨直接用“分治”的方法,考虑每个元素需要多少次才能改变奇偶性,然后找出操作数最少的元素,对应的操作数就是我们想要的答案。

当然,本来就是奇数的话就直接输出

时间复杂度:

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 60, inf = 0x3f3f3f3f;

int a[N];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t, n;
    cin >> t;
    while(t --){
        memset(a, 0, sizeof a);
        cin >> n;
        int sum = 0, mn = inf;
        for(int i=0;i<n;i++){
            int cnt = 0, x;
            cin >> x;
            a[i] = x;
            sum += a[i];
            while(x % 2 == a[i] % 2 && x > 0){
                cnt ++;
                x /= 2;
            }
            mn = min(mn, cnt);
        }
        if(sum % 2 == 0) cout << 0 << '\n';
        else cout << mn << '\n';
    }
    return 0;
}

真就“分治”呗

B. Make Array Good

题意

给定一个数组 ,定义操作为将任意元素加上不超过其本身的自然数,操作数量不限,输出一种操作方案,使得对于任意的 ,有

思路

既然操作数量不限,那么我们不妨把所有数加到 的倍数。

更具体地说,我们只需加到每个元素最近的 的次幂即可。

时间复杂度:

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 60, inf = 0x3f3f3f3f;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t, n;
    cin >> t;
    while(t --){
        cin >> n;
        cout << n << '\n';
        for(int i=1;i<=n;i++){
            int x;
            cin >> x;
            int to = 1;
            while(to < x) to *= 2;
            cout << i << ' ' << to - x << '\n';
        }
    }
    return 0;
}

限次数就难搞了

C. Binary Strings are Fun

题意

在二进制数组的条件下给出两个定义:

  1. 如果对于一个长度为奇数的数组,对于它的所有奇数下标 ,满足 内出现次数至少占总数的一半的数,那么这个数组是好的
  2. 若对于一个长度为 的数组 和一个长度为 的数组 ,满足对于任意 ,有 $ai = b{2i-1}ba$ 的拓展数组

现在,给定一个二进制数组 ,对于 的所有前缀,统计其 好的 拓展数组 的数量之和,并输出。

思路

首先,我们不难发现,若前两位是不相同的,那么我们可选的拓展值是唯一确定的,也就是说,想要让两个元素之间的拓展值有两种取法,那么这两个元素一定是相同的。

其次,若我们遇到了连续相同的一段,但后面被打断之后,那么我们就不得不在相同的这一段填上与之相反的值,否则无法满足后面的条件,所以我们应寻找后缀连续相同段的长度。

我们不妨记这个长度为 ,那么方案数即为

显然,我们可以直接从左向右遍历,此时我们对应地判断+更新 与答案即可。

时间复杂度:

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 60, inf = 0x3f3f3f3f, mod = 998244353;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t, n;
    cin >> t;
    while(t --){
        cin >> n;
        char pre = ' ';
        int ans = 1, tot = 0;
        for(int i=1;i<=n;i++){
            char now;
            cin >> now;
            if(now == pre) ans = (ans * 2) % mod;
            else ans = 1;
            pre = now;
            tot = (tot + ans) % mod;
        }
        cout << tot << '\n';
    }
    return 0;
}

算是想出来了一大半(