A. Divide and Conquer

题意：

给定n个数，每次操作可以使得:$$ \lfloor\frac{ai}{2}\rfloor $$，求最少的操作次数使得n个数的总和为偶数。

分析：

• 和为偶数，res = 0
• 和为奇数，暴力模拟

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define mst(x, y) memset(x, y, sizeof x)
#define endl '\n'
#define INF LONG_LONG_MAX
#define x first
#define y second
#define int long long
#define Lson u << 1, l, mid
#define Rson u << 1 | 1, mid + 1, r
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 200010, MOD = 1e9 + 7;
const double EPS = 1e-6;
typedef pair<int, int> PII;
typedef unordered_map<int, int> Ump;
int T;
int n;
int a[N];
int res;
int sum;
void solve()
{
    sum = 0;
    res = INF;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], sum += a[i];

    if (sum & 1)
    {
        for (int i = 1; i <= n; i++)
        {
            int idx = 0, tmp = sum, num = a[i];
            while (tmp & 1 && a[i])
            {
                a[i] /= 2;
                tmp -= (num - a[i]);
                idx++;
            }
            if (tmp % 2 == 0)
                res = min(res, idx);
            // cout << "a[i] : " << a[i] << " idx : " << idx << endl;
        }
        cout << res << endl;
    }
    else
        cout << "0" << endl;
}
signed main()
{
    FAST;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

B. Make Array Good

题意：

对每一个 ai 操作，可以加上一个数 k（0 ≤ k ≤ ai），操作之后使任意两个数，较大的数能被较小的数整除，操作数 ≤ n

分析：

可以选择最小的数作为底数，每个数扩展成底数的倍数（倍数满足的底数的2的整次幂）；
为什么可行：
对于此时的x，$$ d\times2^{n}\leqslant x\leqslant d\times2^{n + 1} $$
试计算最大差值：$$ d\times2^{n + 1} -x$$
又$$ x\geq d\times2^{n}$$
所以最大差值一定＜x，即最大操作次数为n

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define mst(x, y) memset(x, y, sizeof x)
#define endl '\n'
#define INF LONG_LONG_MAX
#define x first
#define y second
#define int long long
#define Lson u << 1, l, mid
#define Rson u << 1 | 1, mid + 1, r
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 200010, MOD = 1e9 + 7;
const double EPS = 1e-6;
typedef pair<int, int> PII;
typedef unordered_map<int, int> Ump;
int T;
int res;
int n;
int a[N];
int minv;
void solve()
{
    minv = INF;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        minv = min(minv, a[i]);
    }

    cout << n << endl;
    for (int i = 1; i <= n; i++)
    {
        int num = a[i];
        for (int j = 1;; j *= 2)
        {
            if (num <= minv * j)
            {
                cout << i << " " << minv * j - num << endl;
                break;
            }
        }
    }
}
signed main()
{
    FAST;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

C. Binary Strings are Fun

题意（没看懂在说什么，样例也看不懂）复制了：

• 定义一个好的 01 串为：对于每一个奇数位上的数一定是前缀串中的中位数。
  也就是说：如果 si = 1 ，那么对于前i个位置中，1 出现的次数必须多于 0 出现的次数 。
• 定义一个字符串的拓展字符串：对于一个长度为k的字符串，插空添加 0 或 1

对于给定的字符串s，对于他的每一个前缀，求好的字符串的总数。

分析：

要想奇数位上的 1 或 0 有贡献，每一个插入的数都要考虑：
对于给定的 s ：

• s[i] != s[i - 1]，只需要添加与s[i]相同的数即可实现数量上的反超
• s[i] == s[i - 1]，此时不管添加 0 还是 1 ，都不会对数量的反超有影响，所以此时有 2 种情况

类推下去每种情况进行累加

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define mst(x, y) memset(x, y, sizeof x)
#define endl '\n'
#define INF LONG_LONG_MAX
#define x first
#define y second
#define int long long
#define Lson u << 1, l, mid
#define Rson u << 1 | 1, mid + 1, r
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 200010, MOD = 998244353;
const double EPS = 1e-6;
typedef pair<int, int> PII;
typedef unordered_map<int, int> Ump;
int T;
int n;
string s;
int res;
void solve()
{
    res = 0;
    cin >> n >> s;
    s = " " + s;
    int idx = 1;
    for (int i = 1; i <= n; i++)
    {
        if (s[i] != s[i - 1])
            idx = 1;
        else
            idx = idx * 2 % MOD;
        res = (res + idx) % MOD;
    }
    cout << res % MOD << endl;
}
signed main()
{
    FAST;
    cin >> T;
    while (T--)
        solve();
    return 0;
}