A. 使数组 A 等于数组 B

给定两个长度为 n 的二进制数组，可通过翻转元素或重新排列来使 A 与 B 完全一致。目标是求最小操作次数。

关键观察：差异位置数与两数组中 1 的数量差的绝对值加一中的较小值即为答案。

#include <bits/stdc++.h>
using namespace std;

int t, n, cnt;
int a[105], b[105];
int sum_a[105], sum_b[105];

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        cnt = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
            sum_a[i] = sum_a[i-1] + a[i];
        }
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &b[i]);
            if (a[i] ^ b[i]) ++cnt;
            sum_b[i] = sum_b[i-1] + b[i];
        }
        printf("%d\n", min(cnt, abs(sum_a[n] - sum_b[n]) + 1));
    }
    return 0;
}

B. GCD 构造序列

给定数组 a，需构造数组 b 满足 a[i] = gcd(b[i], b[i+1])。若存在则输出 "YES"，否则 "NO"。

构造策略：设 b[i] = lcm(a[i-1], a[i])，边界补 1。验证是否满足条件即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int t, n;
ll a[100050];
ll res[100050];
bool valid;

ll gcd(ll x, ll y) {
    return y == 0 ? x : gcd(y, x % y);
}

ll lcm(ll x, ll y) {
    return x / gcd(x, y) * y;
}

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        valid = true;
        for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
        a[0] = a[n+1] = 1;
        for (int i = 1; i <= n+1; ++i)
            res[i] = lcm(a[i-1], a[i]);
        for (int i = 1; i <= n; ++i)
            if (gcd(res[i], res[i+1]) != a[i])
                valid = false;
        puts(valid ? "YES" : "NO");
    }
    return 0;
}

C1. 优质子数组（简单版）

统计所有子区间 [l,r]，使得子数组 arr[l..r] 中第 i 个元素不小于 i。

使用动态规划：定义 dp[i] 表示以 i 结尾的有效子数组最大长度，则 dp[i] = min(dp[i-1] + 1, arr[i])。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int t, n;
ll arr[200050];
ll dp[200050];
ll ans;

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%lld", &arr[i]);
        dp[0] = 0;
        ans = 0;
        for (int i = 1; i <= n; ++i) {
            dp[i] = min(dp[i-1] + 1, arr[i]);
            ans += dp[i];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

C2. 优质子数组（加强版）

支持单点修改，每次修改后输出新数组中所有有效子区间的贡献总和。

核心思想：预处理前缀和、后缀贡献数组 track[i]，利用线段树加速查找"断点"位置 q，通过等差数列求和快速计算中间部分。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll inf = 0x3f3f3f3f;
ll n, m, p, x, q;
ll arr[200050];
ll d[200050], dp[200050], sum[200050];
ll track[200050], ne[200050];
ll ans, dd;
struct Node {
    ll l, r, mi;
} tree[800050];

void pushup(int p) {
    tree[p].mi = min(tree[p<<1].mi, tree[p<<1|1].mi);
}

void build(int p, ll l, ll r) {
    tree[p].l = l; tree[p].r = r;
    if (l == r) {
        tree[p].mi = d[l];
        return;
    }
    ll mid = (l + r) >> 1;
    build(p<<1, l, mid);
    build(p<<1|1, mid+1, r);
    pushup(p);
}

ll query(int p, ll l, ll r) {
    if (l <= tree[p].l && tree[p].r <= r) return tree[p].mi;
    ll res = inf, mid = (tree[p].l + tree[p].r) >> 1;
    if (l <= mid) res = min(res, query(p<<1, l, r));
    if (mid < r) res = min(res, query(p<<1|1, l, r));
    return res;
}

ll binary_find(ll ql, ll qr, ll val) {
    if (query(1, ql, qr) > val) return n + 1;
    ll l = ql, r = qr, mid, res;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (query(1, ql, mid) <= val) {
            res = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    return res;
}

int main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++i) scanf("%lld", &arr[i]);

    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
        dp[i] = min(dp[i-1] + 1, arr[i]);
        d[i] = arr[i] - i;
        sum[i] = sum[i-1] + dp[i];
    }

    build(1, 1, n);
    track[n] = arr[n];
    ne[n] = n + 1;
    for (int i = n-1; i > 0; --i) {
        ne[i] = binary_find(i+1, n, d[i]);
        if (ne[i] == n+1)
            track[i] = (arr[i] + arr[i] + n - i) * (n - i + 1) / 2;
        else {
            track[i] = track[ne[i]];
            track[i] += (arr[i] + arr[i] + ne[i] - 1 - i) * (ne[i] - i) / 2;
        }
    }

    scanf("%d", &m);
    while (m--) {
        scanf("%lld%lld", &p, &x);
        ll new_dp = min(dp[p-1] + 1, x);
        q = binary_find(p+1, n, new_dp - p);
        ans = sum[p-1];
        if (q == n+1)
            ans += (new_dp + new_dp + n - p) * (n - p + 1) / 2;
        else {
            ans += (new_dp + new_dp + q - p - 1) * (q - p) / 2;
            ans += track[q];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

D. 相等的二进制子序列

给定长度为 2n 的 01 字符串，可进行循环移位操作，将字符串分为两个完全相同的子串。

前提：0 和 1 的数量必须为偶数。将字符串按每两个字符分组，不同组数为偶数时，交替选择各组中一个字符作为移动目标。

#include <bits/stdc++.h>
using namespace std;

int t, n;
string s;
vector<int> diff;
int pos[100050];

int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        cin >> s;
        s = " " + s;
        int ones = 0;
        for (char c : s) if (c == '1') ++ones;
        if (ones % 2) {
            cout << -1 << '\n';
            continue;
        }

        diff.clear();
        for (int i = 1; i <= 2*n; i += 2)
            if (s[i] != s[i+1])
                diff.push_back(i);

        for (int i = 0; i < diff.size(); ++i) {
            if (i % 2 == 0) {
                if (s[diff[i]] == '0') pos[i] = diff[i];
                else pos[i] = diff[i] + 1;
            } else {
                if (s[diff[i]] == '1') pos[i] = diff[i];
                else pos[i] = diff[i] + 1;
            }
        }

        cout << diff.size() << '\n';
        for (int i = 0; i < diff.size(); ++i)
            cout << pos[i] << ' ';
        if (!diff.empty()) cout << '\n';

        for (int i = 1; i <= 2*n; i += 2)
            cout << i << ' ';
        cout << '\n';
    }
    return 0;
}