Practice.

A. Two Groups

题意

给定一个数组 \(a\)，可以为负数，从数组 \(a\) 中取出某些数作为序列 \(s_1\)，剩余作为序列 \(s_2\)，输出 \(|sum(s_1)| - |sum(s2)|\) 的最大值。序列可以为空。

思路

考虑到 \(|sum(s_1)| - |sum(s2)| \leq |sum(s_1) + sum(s2)| = |sum(a_i)|\)，我们可以发现原数组的总和的绝对值即为最大值。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5+10;

signed main(){
    ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        int ans = 0;
        for(int i=1;i<=n;i++) {
            int cur;
            cin >> cur;
            ans += cur;
        }
        cout << abs(ans) << '\n';
    }
}

暴力枚举碰运气过了可还行

B. BAN BAN

题意

给定一个整数 \(n\)，对于由 \(n\) 个 \(BAN\) 组成的字符串，输出至少交换几次，使所有长度为 \(3\) 的可不连续子序列不包含 \(BAN\)。

思路

显然，我们希望 \(B\) 能移到后面，\(N\) 能移到前面，那么我们不妨将第 \(i\) 个 \(B\) 和第 \(n - i + 1\) 个 \(N\) 交换。

当然，若 \(n\) 为奇数，中间的那个字符串直接反转即可。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5+10;

signed main(){
    ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        cout << n / 2 + n % 2 << '\n';
        for(int i=0;i<n/2;i++) cout << 1 + i * 3 << ' ' << 3 * n - (i * 3) << '\n';
        if(n % 2 == 1) cout << 3 * (n / 2) + 1 << ' ' << 3 * (n / 2) + 3 << '\n';
    }
}

纯纯找规律（（

C. Swap Game

题意

给定一个序列，规定每个玩家可以选择一个数，将其与第一个数交换，并将第一个数扣去 \(1\)。定义最后将 \(0\) 交换到第一个位置上的玩家输，在 \(Alice\) 先手的条件下，输出最后的赢家。

思路

首先，若最小的数是第一个数，那么先手就会将最小的数放到后面，从而使后手具有必胜策略：我只需每次都挑大的数，那么对方就只能挑小的数，从而让对方最后只能取 \(0\)。反之同理。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5 + 10, inf = 0x3f3f3f3f;

signed main(){
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        int minn = inf, a0;
        cin >> a0;
        minn = min(minn, a0);
        for(int i=1;i<n;i++){
            int cur;
            cin >> cur;
            minn = min(minn, cur);
        }
        cout << (minn == a0 ? "Bob" : "Alice") << '\n';
    }
}

当然和总和的奇偶性没关系

D. Yet Another Problem

题意

给定一个序列 \(a\)，定义一次操作为选定任意长度为奇数的区间，将区间内的数全都改为整个区间的异或值。对于每个区间询问，输出最小操作数，使区间的数都变为 \(0\)。无解输出 \(-1\)。

思路

首先，若没有区间奇偶性的限制，我们直接预处理出前缀异或，然后用类似于前缀和的方式计算即可。

当然，也可以用一下前缀和，毕竟我们需要知道这个区间是否已经全为 \(0\)。

若查询的区间长度为偶数，那么我们只能挑选两个长度为奇数的区间。考虑到对一个子区间操作后，剩余的区间的异或值一定为 \(0\)，所以我们只需枚举所有长度为奇数的右端的子区间即可（左端也行）。

不过，我们不可以枚举，因为数据量实在太大了。所以，我们需要进行预处理。对于一个右端点，若它为偶数，那么以它为右端点的区间的左端点一定是奇数，从而我们可以进行递推，找到两个异或值相等且奇偶性不同的点即可。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5 + 10;

int a[N], xo[N], sum[N], pre[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<map<int, int>> mp(2);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        xo[i] = xo[i - 1] ^ a[i];
        sum[i] = sum[i - 1] + a[i];
        if(mp[1 - i % 2].count(xo[i])) pre[i] = mp[1 - i % 2][xo[i]];
        mp[i % 2][xo[i]] = i;
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        if ((xo[r] ^ xo[l - 1]) != 0) {
            cout << -1 << '\n';
            continue;
        }
        if (sum[r] - sum[l - 1] == 0) {
            cout << 0 << '\n';
        } else if ((r - l + 1) % 2 == 1) {
            cout << 1 << '\n';
        } else {
            if (a[r] == 0 || a[l] == 0) {
                cout << 1 << '\n';
                continue;
            }
            cout << (pre[r] >= l ? 2 : -1) << '\n';
        }
    }
}

二分半天不过...