Codeforces Round 895 div3 | JorbanS

A - Two Vessels

int solve() {
    int a, b, c; cin >> a >> b >> c;
    return (abs(a - b) / 2 + (abs(a - b) & 1) + c - 1) / c;
}
1
2
3
4

B - The Corridor or There and Back Again

int solve() {
    int n; cin >> n;
    int res = 400;
    for (int i = 0; i < n; i ++) {
        int d, s; cin >> d >> s;
        res = min(res, d + (s - 1) / 2);
    }
    return res;
}
1
2
3
4
5
6
7
8
9

C - Non-coprime Split

void solve() {
    int l, r; cin >> l >> r;
    if (r >= 4) {
        if (l == r) {
            if ((l & 1) == 0) {
                cout << 2 << ' ' << r - 2 << endl;
                return;
            } else {
                for (int i = 2; i <= l / i; i ++) {
                    if (l % i == 0) {
                        cout << i << ' ' << l - i << endl;
                        return;
                    }
                }
            }
        } else {
            if (r & 1) cout << 2 << ' ' << r - 3 << endl;
            else cout << 2 << ' ' << r - 2 << endl;
            return;
        }
    }
    cout << -1 << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

D - Plus Minus Permutation

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

ll solve() {
    ll n, x, y; cin >> n >> x >> y;
    ll d = x * y / gcd(x, y);
    ll nx = n / x, ny = n / y;
    ll nxy = n / d;
    nx -= nxy, ny -= nxy;
    ll sumx = nx * (n * 2 - nx + 1) / 2;
    ll sumy = ny * (1 + ny) / 2;
    return sumx - sumy;
}
1
2
3
4
5
6
7
8
9
10
11
12

E - Data Structures Fan

Tag 前缀异或和

一开始无脑用 $bitset$，结果一直 $TLE$，换了 $string$ 就过了 😅😅😅

$bitset$ 一次输入复杂度 $O(N)$，而 $string$ 的均摊复杂度为 $O(n)$

const int N = 1e5 + 2;
int a[N], XOR[N];
string s;

void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i], XOR[i] = XOR[i - 1] ^ a[i];
    cin >> s;
    int res[2] = {0};
    for (int i = 0; i < n; i ++) res[s[i] - '0'] ^= a[i + 1];
    int m; cin >> m;
    while (m --) {
        int op; cin >> op;
        if (op == 1) {
            int l, r; cin >> l >> r;
            int t = XOR[r] ^ XOR[l - 1];
            res[0] ^= t;
            res[1] ^= t;
        } else {
            int g; cin >> g;
            cout << res[g] << ' ';
        }
    }
    cout << endl;
}
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