Codeforces Round 896 (Div. 2)

A. Make It Zero

大致题意

有一个数组，允许你每次选择一个区间，然后将这个区间内的所有值变成他们异或和的结果，问给出一种最多只进行 8 次的操作的可能方法使得整个数组变成 0

思路

不要求最小，只要能就行，简单了很多很多

首先，偶数个相同的值进行异或和，结果为 0，如果整个数组长度为偶数，那么直接异或和两次即可

如果为奇数，那么先把前 $n - 1$ 个异或和一下，最后再异或和两次最后两个值即可

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, tmp;
        cin >> n;
        for (int i = 0; i < n; ++i) cin >> tmp;
        if (n % 2) {
            cout << 4 << endl;
            cout << 1 << ' ' << n << endl;
            cout << 1 << ' ' << n - 1 << endl;
            cout << n - 1 << ' ' << n << endl;
            cout << n - 1 << ' ' << n << endl;
        } else {
            cout << 2 << endl;
            cout << 1 << ' ' << n << endl;
            cout << 1 << ' ' << n << endl;
        }
    }
}

B. 2D Traveling

大致题意

有一个棋盘，开始在 $a$ 点，要前往 $b$ 点，只能中途停留在固定的 $n$ 个节点中任意一个

任意两个节点之间的成本是他们的棋盘距离，但是有 $k$ 个节点，他们之间相互的成本是 $0$

问最少成本是多少

思路

棋盘距离就意味着，其实中间停留是毫无意义的，直接到终点就行了，没必要停留

但是有一些特殊节点，所以只需要找到距离 $a$ 最近的特殊节点，并计算成本，和距离 $b$ 的特殊节点，并计算成本，然后将两个成本相加和直接前往的成本差异，求较小值就行

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define int long long

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, k, a, b;
        cin >> n >> k >> a >> b;
        vector<pair<int, int>> data(n);
        for (auto &item: data) cin >> item.first >> item.second;
        auto dist = [&](int l, int r) {
            return abs(data[l].first - data[r].first) + abs(data[l].second - data[r].second);
        };
        int ans = dist(a - 1, b - 1);
        int ak = INT_MAX * 2LL, bk = INT_MAX * 2LL;
        for (int i = 0; i < k; ++i) {
            ak = min(ak, dist(i, a - 1));
            bk = min(bk, dist(i, b - 1));
        }
        cout << min(ans, ak + bk) << endl;
    }
}

C. Fill in the Matrix

大致题意

有一个 $n \times m$ 的矩阵，将其每一行填充为 $m$ 的一个排列，求出每一列的 MEX，然后将每一列的 MEX 再求一次 MEX，问最终结果最大是多少，并给出矩阵

思路

构造题，比较简单，如果想看我的构造方案就运行一下打印出来看看吧

需要注意的是，因为矩阵比较大，不能存下来，所以需要提前算出答案输出了，不能等构造完成了再去算

AC code

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
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, m;
        cin >> n >> m;
        if (m == 1) {
            cout << 0 << endl;
        } else if (n >= m - 1) {
            cout << m << endl;
        } else {
            cout << n + 1 << endl;
        }
        for (int i = 0; i < min(n, m - 1); ++i) {
            for (int j = 0; j < m; ++j) {
                cout << (j - i - 1 + m) % m << ' ';
            }
            cout << endl;
        }
        for (int i = min(n, m - 1); i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                cout << (j + 1) % m << ' ';
            }
            cout << endl;
        }
    }
}

D1. Candy Party (Easy Version)

大致题意

有 $n$ 个人，每个人手上都有一些糖果，现在每个人都必需要给另外一个人 $2^x$ 个糖果，$x$ 可以是任意自然数，且每个人必须从另外一个人那里拿到他给出的糖果，问是否存在一种可能，经过这样一次操作后，所有人糖果数量相同

思路

首先，糖果没有新增或者丢弃，那么必然总糖果数量不变，所以很容易计算出最终每个人应该是多少糖果。那么就可以算出差值（应该最终增加/减少多少）

其次思考一个问题，由于给出/收到的糖果数量满足 $2^x$ 的形式，那么必然差值定是两个 $2^x$ 之差。例如 $3 = 4 - 1$，$7 = 8 - 1$，$4 = 8 - 4$ 等等就是合法的值，而例如 $5$ 就是一个非法的值。所以这样就可以先排除掉一部分了

很显然，每个值都只有一种可能的拆法，又因为每个人只能从一个人那里拿到糖果，那么必然所有的给出和拿到的可能性只有这些，他们必然完全相等

AC code

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
#define int long long

void solve() {
    vector<int> mi(40);
    for (int i = 0; i < 40; ++i) mi[i] = 1LL << i;
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        vector<int> data(n);
        for (auto &item: data) cin >> item;
        int sum = 0;
        for (auto &item: data) sum += item;
        if (sum % n != 0) {
            cout << "No" << endl;
            continue;
        }
        sum /= n;

        auto lowBit = [](int x) { return x & -x; };
        vector<int> p[2];
        p[0].reserve(n);
        p[1].reserve(n);
        bool flag = true;
        for (int i = 0; i < n; ++i) {
            int diff = data[i] - sum;
            if (diff == 0) continue;
            int l = diff > 0 ? 0 : 1, r = 1 ^ l;
            diff = abs(diff);
            int b = *upper_bound(mi.begin(), mi.end(), diff);
            int s = b - diff;
            if (*lower_bound(mi.begin(), mi.end(), s) != s) {
                flag = false;
                break;
            }
            p[l].push_back(b);
            p[r].push_back(s);
        }
        sort(p[0].begin(), p[0].end());
        sort(p[1].begin(), p[1].end());
        cout << (flag && p[0] == p[1] ? "YES" : "NO") << endl;
    }
}

D2. Candy Party (Hard Version)

大致题意

和上一题类似，只不过从必须给一个人改成了至多给一个人，从一个人那拿到变成了至多从一个那里拿到。即可以不再一定要给出/收到了

思路

那么唯一的区别就在于那些差值本来就符合 $2^x$ 的人，因为他们既可以选择同时有给出收到，也可以选择只给出/收到。而那些不满足的则必定有给出和收到阶段

而那些本来就符合 $2^x$ 的值，如果它又同时选择有给出收到，那么称其为拆开后的，而拆开后必然得到一个更大的值。

那么可以按照下面的步骤进行模拟

  1. 将所有值分成两类：已经拆过了的，没有拆过的
  2. 对于每个差值，如果它满足 $2^x$，那么放入到没有拆过的组里，而不满足的，则将拆开后的两个 $2^x$ 值放入已经拆过的组里
  3. 判断一下，已经拆过的里面 $abs$ 最大的值和没有拆过的里面 $abs$ 最大的值，哪个大，如果后者大，那么就把那些大的值放入已经拆过的队列（因为他们再拆开就会创造更大的值，没有必要再拆了）
  4. 每次取出 $abs$ 最大的拆过的值，然后尝试在已经拆过里面为它找配对上的，即 $abs$ 相同，但是正负号相反的值，并将其消除
  5. 如果找不到，那么就再去没有拆过里面找相同的条件的，并消除
  6. 如果还找不到，那么再去没有拆过里面找符号相同但是值恰好为 $abs$ 的一半的，将其拆开，将 $abs$ 较大的删除，较小的放入已经拆开的队列中
  7. 回到 3 步，除非两个队列都空了

AC code

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#define int long long

void solve() {
    vector<int> mi(40);
    for (int i = 0; i < 40; ++i) mi[i] = 1LL << i;
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        vector<int> data(n);
        for (auto &item: data) cin >> item;
        int sum = 0;
        for (auto &item: data) sum += item;
        if (sum % n != 0) {
            cout << "No" << endl;
            continue;
        }
        sum /= n;

        struct cmp {
            bool operator()(const int &lhs, const int &rhs) const {
                return abs(lhs) < abs(rhs);
            }
        };

        priority_queue<int, vector<int>, cmp> depart;
        map<int, int, greater<>> pos, neg;
        bool flag = true;
        for (int i = 0; i < n; ++i) {
            int dif = data[i] - sum;
            if (dif == 0) continue;
            if (abs(dif) == *lower_bound(mi.begin(), mi.end(), abs(dif))) {
                // good gay
                (dif > 0 ? pos : neg)[abs(dif)]++;
            } else {
                // bad gay
                int b = *upper_bound(mi.begin(), mi.end(), abs(dif));
                b *= dif > 0 ? 1 : -1;
                int s = dif - b;
                if (abs(s) != *lower_bound(mi.begin(), mi.end(), abs(s))) {
                    flag = false;
                    break;
                }
                depart.push(b);
                depart.push(s);
            }
        }

        if (!flag) {
            cout << "NO" << endl;
            continue;
        }

        while (!depart.empty() || !pos.empty() || !neg.empty()) {
            if (depart.empty()) {
                auto posIter = pos.begin(), negIter = neg.begin();
                if (posIter->first == negIter->first) {
                    int tmp = min(posIter->second, negIter->second);
                    posIter->second -= tmp;
                    negIter->second -= tmp;
                    if (posIter->second == 0) pos.erase(posIter);
                    if (negIter->second == 0) neg.erase(negIter);
                    continue;
                }

                auto &iter = posIter->first > negIter->first ? posIter : negIter;
                auto mx = posIter->first > negIter->first ? 1 : -1;
                auto &u = posIter->first > negIter->first ? pos : neg;
                auto &v = posIter->first > negIter->first ? neg : pos;
                auto tIter = v.find(iter->first / 2);
                if (tIter == v.end()) {
                    flag = false;
                    break;
                }
                int tmp = min(iter->second, tIter->second);
                for (int i = 0; i < tmp; ++i) depart.push(mx * iter->first / 2);
                iter->second -= tmp;
                tIter->second -= tmp;
                if (iter->second == 0) u.erase(iter);
                if (tIter->second == 0) v.erase(tIter);
            }

            while (!pos.empty() || !neg.empty()) {
                auto posIter = pos.begin();
                auto negIter = neg.begin();

                bool posWin = negIter == neg.end() || (posIter != pos.end() && posIter->first > negIter->first);
                auto &maxIter = posWin ? posIter : negIter;
                auto &maxLink = posWin ? pos : neg;
                auto mx = posWin ? 1 : -1;
                if (maxIter->first > abs(depart.top())) {
                    for (int i = 0; i < maxIter->second; ++i) depart.push(mx * maxIter->first);
                    maxLink.erase(maxIter);
                } else {
                    break;
                }
            }

            int cnt[2] = {depart.top() < 0, depart.top() > 0};
            int cur = abs(depart.top());
            depart.pop();

            while (!depart.empty() && abs(depart.top()) == cur) {
                cnt[0] += depart.top() < 0;
                cnt[1] += depart.top() > 0;
                depart.pop();
            }

            // receives from not good gay
            int tmp = min(cnt[0], cnt[1]);
            cnt[0] -= tmp;
            cnt[1] -= tmp;
            if (cnt[0] == 0 && cnt[1] == 0) continue;

            int left = cnt[0] > 0 ? 0 : 1;
            auto &link = cnt[0] > 0 ? pos : neg;
            int mx = cnt[0] > 0 ? -1 : 1;

            // find in pos which is equals to this gay
            auto iter = link.find(cur);
            if (iter != link.end()) {
                tmp = min(cnt[left], iter->second);
                iter->second -= tmp;
                cnt[left] -= tmp;
                if (iter->second == 0) link.erase(iter);
            }
            if (cnt[left] == 0) continue;

            // not enough, find in pos which is half of this gay
            iter = link.find(cur / 2);
            if (iter != link.end()) {
                tmp = min(cnt[left], iter->second);
                for (int i = 0; i < tmp; ++i) depart.push(mx * cur / 2);
                iter->second -= tmp;
                cnt[left] -= tmp;
                if (iter->second == 0) link.erase(iter);
            }

            if (cnt[left] != 0) {
                flag = false;
                break;
            }
        }

        cout << (flag ? "YES" : "NO") << endl;
    }
}
ACM&算法
#ACM #Codeforces
Codeforces Round 896 (Div. 2)
https://blog.mauve.icu/2023/09/16/acm/codeforces/CodeforcesRound896/
作者
Shiroha
发布于
2023年9月16日
许可协议