Codeforces Round 984 Div.3 题解

发表于 更新于 分类于 阅读次数： 本文字数： 8.8k
这场难度并不大，但是挺考验英语阅读的，向Div4靠拢了，FG需要一点异或的性质。

Codeforces Round 984 (Div. 3)

A

题意

给定一个数组，要求相邻数差的绝对值必须是5或7，判断是否成立。

题解

按题意模拟即可。

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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    bool ok = 1;
    for (int i = 1; i < n; i++) {
        if (abs(a[i] - a[i - 1]) == 5 || abs(a[i] - a[i - 1]) == 7) {
            continue;
        }
        ok = 0;
        break;
    }
    if (ok) {
        cout << "YES" << "\n";
    } else {
        cout << "NO" << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B

题意

给定\(n\)个货架，需要卖出\(k\)个瓶子，给定每个瓶子的标签\(b_i\)和价格\(c_i\)，要求每个货架只能放置相同类型的瓶子，求全部卖出后最多能卖多少钱。

题解

统计每种瓶子卖的总价后排序即可。

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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(k);
    for (int i = 0; i < k; i++) {
        int x, c;
        cin >> x >> c;
        x--;
        a[x] += c;
    }
    sort(a.begin(), a.end(), greater());
    int ans = 0;
    for (int i = 0; i < min(n, k); i++) {
        ans += a[i];
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C

题意

给定一个01字符串和\(q\)次操作，每次可以改变一个位置的字符，求每次操作后字符串中是否存在“1100”的子串。

题解

每次操作后实际只会改变操作位置周围的4个字符串，我们统计时去掉它们的影响后重新统计这4个字符串即可。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    int cnt = 0;
    for (int i = 0; i < n - 3; i++) {
        if (s.substr(i, 4) == "1100") {
            cnt++;
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int x;
        char y;
        cin >> x >> y;
        x--;
        if (s[x] == y) {
            if (cnt) {
                cout << "YES" << "\n";
            } else {
                cout << "NO" << "\n";
            }
            continue;
        }
        for (int j = max(0ll, x - 3); j <= min(n - 4, x); j++) {
            cnt -= s.substr(j, 4) == "1100";
        }
        s[x] = y;
        for (int j = max(0ll, x - 3); j <= min(n - 4, x); j++) {
            cnt += s.substr(j, 4) == "1100";
        }

        if (cnt) {
            cout << "YES" << "\n";
        } else {
            cout << "NO" << "\n";
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D

题意

给出一个\(n\times m\)的矩阵（两边长一定是偶数），里面的元素均为0-9的数字。现在从外向内遍历矩阵的每一圈，给出总共有多少个“1543”会出现在某一圈中。

题解

首先，我们需要一个遍历该矩阵的方式。不妨假定每一圈都是从左上角开始遍历的，那么圈数应该是\(\min(n,m)/2\)。从起点开始先向右，再向下，再向左，再向上的顺序，我们可以遍历每一圈，这可以通过四个循环来实现。

还有一个问题是要统计答案，由于起点的影响，由于每一层是循环的，前几个数作为结尾的子串是不会被统计进去的。我们可以考虑再遍历的过程中记录下这一圈的字符串，遍历完后破环成链（即将该字符串加倍），这样统计就没问题了，只需要统计以前一半长度作为开头的子串。

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
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int ans = 0;
    for (int d = 0; d < min(n, m) / 2; d++) {
        string s;
        for (int j = d; j < m - d - 1; j++) {
            s += a[d][j];
        }
        for (int i = d; i < n - d - 1; i++) {
            s += a[i][m - d - 1];
        }
        for (int j = m - d - 1; j > d; j--) {
            s += a[n - d - 1][j];
        }
        for (int i = n - d - 1; i > d; i--) {
            s += a[i][d];
        }
        s += s;
        for (int i = 0; i < s.size() / 2; i++) {
            if (s.substr(i, 4) == "1543") {
                ans++;
            }
        }
    }
    cout << ans << "\n";
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

E

题意

给定一个\(n\)行\(k\)列的矩阵\(a_{i,j}\)，之后按照\(i\)从1到\(n\)的顺序，令\(b_{i,j} = a_{i,j}|a_{i-1,j}\)，再给定\(q\)次询问，每次询问给定\(m\)个条件，每个条件是以\(r > c\)或\(r < c\)的形式给出，其中\(r\)代表\(b\)数组的第二维，我们需要给出一个尽可能小的数\(i\)，使得\(b_{i,r}\)满足给定的所有条件，若不存在输出-1。

题解

题意给的非常绕，但是注意到或运算具有单调不降的性质，因此对于每个询问我们都可以二分回答。为了便捷，我们可以自己手动交换数组的两个维度，这样可以直接使用lower_bound和upper_bound函数，否则需要手写。

在每个询问中，我们使用一组L，R代表可行的范围，对于每个要求，我们另开一组L，R进行二分并更新外部的L，R。所有要求二分结束后我们判断可行性：即\(L\le R\)时是满足条件的。

下面的代码中交换了两个维度，但是二分是手动实现的。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, k, q;
    cin >> n >> k >> q;
    vector<vector<int>> a(k, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) {
            cin >> a[j][i];
        }
    }

    for (int j = 0; j < k; j++) {
        for (int i = 1; i < n; i++) {
            a[j][i] |= a[j][i - 1];
        }
    }
    for (int i = 0; i < q; i++) {
        int m;
        cin >> m;
        int lo = 0, hi = n - 1;
        for (int j = 0; j < m; j++) {
            int r, c;
            char o;
            cin >> r >> o >> c;
            r--;
            if (o == '>') {
                int L = 0, R = n;
                while (L < R) {
                    int mid = L + (R - L) / 2;
                    if (a[r][mid] > c) {
                        R = mid;
                    } else {
                        L = mid + 1;
                    }
                }
                lo = max(lo, L);
            } else {
                int L = 0, R = n;
                while (L < R) {
                    int mid = L + (R - L) / 2;
                    if (a[r][mid] >= c) {
                        R = mid;
                    } else {
                        L = mid + 1;
                    }
                }
                hi = min(hi, L - 1);
            }
        }
        if (lo <= hi) {
            cout << lo + 1 << "\n";
        } else {
            cout << -1 << "\n";
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

F

题意

给定一组\(l,r,k,i\)，求\(l,r\)之间的所有满足下列条件的数\(x\)的异或值：\(x\not\equiv k(\mod 2^i)\)​。

\(1\le l\le r\le 10^{18}\)

题解

首先，异或具有这样的性质：\(0\oplus x = x, x \oplus x = 0\)，因此，求\([l,r]\)之间的答案，我们可以转化为求\([0,l-1]\)和\([0,r]\)之间的答案的异或值。现在我们只考虑求\([0,x]\)之间的答案即可，我们设为\(f(0,x)\)，答案即为\(f(l,r) = f(0,l-1) \oplus f(0,r)\)。

模意义下不等于\(k\)的数非常多，我们还可以利用异或的性质，求出\(x\equiv k(\mod 2^i)\)的数，异或上\([0,x]\)所有数的异或，接下来考虑分别求出\(0\oplus1\oplus ... \oplus x\)与满足\(x\equiv k(\mod 2^i)\)所有数的异或。

对于0开始的前缀异或，我们有如下的结论：从0开始每两个连续的数的异或值都是1，也就是说，每四个连续的数异或值必为0，我们按照模4的余数，将\(x\)分为四种情况考虑：如果\(x\)恰好为4的倍数，那么异或值一定是\(x\)，这是因为从0开始算的话，4的倍数实际上是第\(4k+1\)个数，而前\(4k\)个数的异或值为0，再异或一次应该就是\(x\)；同理，如果\(x \mod 4 \equiv 3\)，异或值应该为0；如果\(x\mod 4 \equiv 1\)，异或值为1，因为上一个数异或后为\(x\)，连续两个数恰好是从上一个数开始的，结果是1；如果\(x\mod 4 \equiv 2\)，结果应该是\(x+1\)，因为前一个数的异或值为1，而当前数是偶数，个位为0，异或后相当于加了1。

对于所有\(x\equiv k(\mod 2^i)\)，一个性质应该是：所有这些数转换为二进制后，低\(i\)位应该都相同，且都为\(k\)的二进制。这是因为\(2^i\)恰好对应第\(i+1\)位，也就是说从这一位开始的答案在模意义下没有影响，而只有低\(i\)位满足条件才能有\(x\equiv k(\mod 2^i)\)。我们考虑把这些数分解为低\(i\)位和从\(i+1\)位开始的数。既然知道每个数的低\(i\)位都是\(k\)，所以如果这些数一共有奇数个，低\(i\)位的异或值应该是\(k\)，否则应该是0。对于\(i+1\)位开始的数，其实就是0开始的前缀异或，我们只需要知道这些数最大满足条件的是多少即可，求法为减去\(k\)后对于\(2^i\)上取整。

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
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int l, r, i, k;
    cin >> l >> r >> i >> k;
    r++;
    auto get = [&](int x) {
        int a = x % 4;
        if (a == 0) {
            return 0ll;
        } else if (a == 1) {
            return x - 1;
        } else if (a == 2) {
            return 1ll;
        }
        return x;
    };
    int ans = 0;
    ans ^= get(r);
    ans ^= get(l);
    r = (r - k + (1ll << i) - 1) >> i;
    l = (l - k + (1ll << i) - 1) >> i;
    ans ^= get(r) << i;
    ans ^= get(l) << i;
    if ((r - l) & 1) {
        ans ^= k;
    }
    cout << ans << "\n";
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

G

题意

交互题，有\(n\)种物品，分别编号为1～n，每种物品有两个，现在有3个物品丢失了（不是同一种），给定150次询问，每次询问可以询问两种物品，回答这两种物品的编号范围之间所有物品的编号的异或结果，回答丢失的三个物品。

\(3\le n \le10^{18}\)

题解

\(n\)的范围非常大而询问次数比较少，想到肯定是近似\(O(\log n)\)的询问次数，进而想到二分。

由于每个物品只有两种，所以在未丢失的情况下，他们的异或和应该是0，因此一段物品的异或值不是0，说明这一段物品肯定有丢失的物品。

那么，是不是一段物品的异或值为0，这一段就没有丢失呢？这样并不对，考虑二进制下11，01，10三个数丢失，它们的异或和就是0，因此，麻烦的地方就是异或值为0无法确定一段物品是未丢失的。

但是，如果一次二分中发现左右两段的异或值都不是0，我们一定可以确定一个数。我们设丢失的三个数为\(a<b<c\)，那么要么\(a,b\)在一段，要么\(b,c\)在一段。如果\(b,c\)在一段，说明最高位的异或值一定是0，此时\(a\)就是可以确定的数，如果\(a,b\)在一段，那么最高位的异或值就是1，此时\(c\)就是可以确定的数。

我们考虑从10000...0000（二进制）开始二分，即枚举最高位，那么如果两段数都不为0时，就可以确定一个数了。然后我们继续在两个数的那一段二分，一旦每一次二分结果不为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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n;
    cin >> n;
    auto query = [&](int l, int r) {
        l = max(1ll, l);
        r = min(n, r - 1);
        if (l > r) {
            return 0ll;
        }
        cout << "xor " << l << " " << r << "\n";
        cout.flush();
        int x;
        cin >> x;
        return x;
    };
    int lo = 0, hi = (1ll << 60), d = 60;
    vector<int> ans;
    while (true) {
        int m = lo + (hi - lo) / 2;
        int a = query(lo, m);
        int b = query(m, hi);
        d--;
        if (b == 0) {
            hi = m;
        } else if (a == 0) {
            lo = m;
        } else if (b >> d & 1) {
            ans.push_back(b);
            hi = m;
            break;
        } else {
            ans.push_back(a);
            lo = m;
            break;
        }
    }
    while (true) {
        int m = lo + (hi - lo) / 2;
        int a = query(lo, m);
        int b = query(m, hi);
        d--;
        if (b == 0) {
            hi = m;
        } else if (a == 0) {
            lo = m;
        } else {
            ans.push_back(a);
            ans.push_back(b);
            hi = m;
            break;
        }
    }
    sort(ans.begin(), ans.end());
    cout << "ans";
    for (auto x : ans) {
        cout << " " << x;
    }
    cout << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}