Codeforces Round #832 (Div. 2)

Codeforces Round #832 (Div. 2) A~D

A. Two Groups

#include
#define int long long 
void solve()
{
    int n;
    std::cin >> n;
    int res1 = 0, res2 = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        std::cin >> x;
        if (x > 0) res1 += x;
        else res2 += x;
    }
    std::cout << std::abs(std::abs(res1) - std::abs(res2)) << "\n";
}

signed main()
{
    int T;
    std::cin >> T;
    while (T--) solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

B. BAN BAN

#include
#define int long long 
void solve()
{
    int n;
    std::cin >> n;
    std::cout << (n + 1) / 2 << "\n";
    for (int i = 1, j = 3 * n; i <= j; i += 3, j -= 3) {
        std::cout << i << ' ' << j << "\n";
    }
}

signed main()
{
    int T;
    std::cin >> T;
    while (T--) solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

C. Swap Game

#include
#define int long long 
void solve()
{
    int n, a;
    std::cin >> n >> a;
    int res = 0x3f3f3f3f;
    for (int i = 1; i < n; i++) {
        int x;
        std::cin >> x;
        res = std::min(x, res);
    }
    if (a <= res) std::cout << "Bob\n";
    else std::cout << "Alice\n";
}

signed main()
{
    int T;
    std::cin >> T;
    while (T--) solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

D. Yet Another Problem

题意： 给出数组和q次询问，每次询问输入一个区间范围，你可以选择这个范围中一段奇数长度的元素，替换他们为他们的异或和，问最少多少次可以把这个范围全部变成0，输出最小操作次数
思路： 首先可以确定的是，不考虑奇偶，要是可以变成全0，那么一定只需要一次或者不行，所以只需要直接看区间异或前缀和是不是0，现在考虑偶数区间长度，并且区间异或和是0
①这个区间两端有至少一个0，说明这个区间变成奇数区间长度，只需要一次
②这个区间全是0，说明0次
③这个区间有一段前缀奇数区间可以异或出来0，这样就可以变相把区间长度变成奇数，需要2次
④剩下就是-1的情况
对于第三点，我们开两个vector，一个记录对于奇数下标的异或值的下标，一个记录对于偶数的，那么我们只需要在相异的vector里找到左端点的异或值是否重新出现在右端点之前，能找到说明可以变相把长度变成奇数

#include
int cnt[200010], a[300010], sum[200010];
int main()
{
    std::ios::sync_with_stdio(0);
    std::cin.tie(0), std::cout.tie(0);
    int n, q;
    std::cin >> n >> q;
    std::map<int, std::vector<int> > vec[2];
    for (int i = 1; i <= n; i++) {
        int x;
        std::cin >> x;
        a[i] = x;
        cnt[i] = x;
        cnt[i] ^= cnt[i - 1];
        sum[i] = x;
        sum[i] += sum[i - 1];
        int p = i & 1;
        vec[p][cnt[i]].push_back(i);
    }
    while (q--) {
        int l, r;
        std::cin >> l >> r;
        if (cnt[l - 1] != cnt[r]) {std::cout << "-1\n"; continue;}
        if (sum[r] == sum[l - 1]) {std::cout << "0\n"; continue;}
        if ((r - l + 1) % 2 == 1) {
            std::cout << "1\n"; continue;
        }
        if (!a[l] || !a[r]) {std::cout << "1\n"; continue;}
        auto pa = std::lower_bound(vec[(l % 2)][cnt[l - 1]].begin(), vec[(l % 2)][cnt[l - 1]].end(), l - 1);
        if (pa != vec[(l % 2)][cnt[l - 1]].end() && *pa < r) {
            std::cout << "2\n"; continue;
        }std::cout << "-1\n";
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36