Practice.

A. Divide and Conquer

题意

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

思路

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

当然，本来就是奇数的话就直接输出 \(0\)。

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

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

题意

给定一个数组 \(b\)，定义操作为将任意元素加上不超过其本身的自然数，操作数量不限，输出一种操作方案，使得对于任意的 \(i, j\)，有 \(\min(b_i, b_j) | \max(b_i, b_j)\)。

思路

既然操作数量不限，那么我们不妨把所有数加到 \(2\) 的倍数。

更具体地说，我们只需加到每个元素最近的 \(2\) 的次幂即可。

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

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

题意

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

如果对于一个长度为奇数的数组，对于它的所有奇数下标 \(i\)，满足 \(b_i\) 是 \([1,i]\) 内出现次数至少占总数的一半的数，那么这个数组是好的。
若对于一个长度为 \(k\) 的数组 \(a\) 和一个长度为 \(2k-1\) 的数组 \(b\)，满足对于任意 \(i \in [1,k]\)，有 \(a_i = b_{2i-1}\)，那么称 \(b\) 是 \(a\) 的拓展数组。

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

思路

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

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

我们不妨记这个长度为 \(len\)，那么方案数即为 \(2^{len-1}\)。

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

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

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

算是想出来了一大半（