Codeforces Round 1091 (Div. 2) and CodeCraft 26

by JiuQiin Codeforces, 题解on Posted on
“If you cling to a certain thought with dynamic will power, it finally assumes a tangible outward form.”
— Paramahansa Yogananda

一些废话

这场总体来说打的很难受，本来本人的数学思维差的离谱，一遇上数学题，猜的对就过，猜不对是常态，得，开场 C 就来一道数学，直接卡一个多小时，猜了三个做法，都过不了样例，tmd，实在熬不动，去看 D ，这个 D 也很难绷，有一种能手推，但绝对用代码实现不了的绝望，真的很难绷，打个跟坨屎一样

Contents hide
1 一些废话
2 A. The Equalizer
2.1 题意
2.2 思路
2.3 代码
3 B. Flip the Bit (Easy Version)
3.1 题意
3.2 思路
3.3 代码
4 C. Grid Covering
4.1 题意
4.2 思路
4.3 代码
5 D. Flip the Bit (Hard Version)
5.1 题意
5.2 思路
5.3 反思
5.4 代码
6 E. Definitely Larger
6.1 题意
6.2 思路
6.3 代码

A. The Equalizer

题意

两人轮流下棋，每人可进行的操作是可选取任意的一个 aia_i 使其进行减一操作，最后一个进行操作的人获胜。先手可使用一次特殊技能：将 a 数组所有的值都替换成 k。问最后先手能否获胜

思路

如果数组和为奇数，则每人每轮轮流减一，先手一定获胜

如果数组和为偶数，则先手可选择使用技能，若使用完技能后，后手变为先手，即使用完技能后，数组和为偶数，原先手获胜

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    LL n, k;
    cin >> n >> k;
    LL sm = 0;
    for (LL i = 1; i <= n; ++i) {
        LL t;
        cin >> t;
        sm += t;
    }
    LL sm1 = k * n;
    if ((sm & 1) || (sm1 % 2 == 0)) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

B. Flip the Bit (Easy Version)

题意

给出一个二进制数组 a 和特殊索引 k ，每次可以选择任意的区间 [l, r] [l, \ r]，该区间必须包含特殊索引，将该区间中的数值翻转，即 0 -> 1, 1 -> 0，最后使得数组 a 中的所有值都等于原 aka_k（进行所有操作前），问最少的操作数

思路

每次尽可能干掉多的不符合要求的数值，所以尽可能左边扩到尽可能远，操作数为 lv，右边同理，操作数为 rv，多的操作数可以带上少的那部分，所以最后答案就是 max(lv,rv)max(lv, rv)

还有个细节，若 max 出来的答案是奇数，说明 aka_k 也被翻转了，还得再加上一次操作

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    LL n, k;
    cin >> n >> k;
    vector<LL> a(n + 1, 0);

    for (LL i = 1; i <=n; ++i) {
        cin >> a[i];
    }

    LL s;
    cin >> s;
    LL lv = 0, rv = 0;
    for (LL i = s + 1; i <= n; ++i) {
        if (a[i] != a[i - 1]) {
            rv++;
        }
    }
    for (LL i  =s - 1; i >= 1; --i) {
        if (a[i] != a[i + 1]) {
            lv++;
        }
    }
    LL ans = max(lv, rv);
    if (ans & 1) {
        ++ans;
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

C. Grid Covering

题意

给出一个 n×mn \times m 的网格A，从 A1,1A_{1, 1} 开始，每次可往下走 a 步，或者往右走 b 步，可选择任意一个动作开始，但每次必须两个动作轮流交替进行，问最后能否把每个格子都走到

思路

可以先把横纵分来来看，先考虑横向，若 gcd(n,a)≠1gcd(n, a) \neq 1，则中间一定有若干行永远无法走到，纵向同理，推出必须满足 gcd(n,a)=1 , gcd(m,b)=1gcd(n, a) = 1 \ , \ gcd(m, b) = 1

之后判断在一次轮回中，能否将所有格子走完？

设 p 为单横向走的步数，因为 p×a≡0 (mod n), p×b≡0 (mod m)p \times a \equiv 0\ (mod \ n),\ p \times b \equiv 0 \ ( mod \ m)，所以 pmin=lcm(n,m)p_{min} = lcm(n, m)（不懂，难道不考虑 a 和 b 的影响吗），横纵加起来，一次轮回中，所走的格子数最多为 2⋅lcm(n,m)2 \cdot lcm(n, m)

  • 若 gcd(n,m)>=3gcd(n, m) >= 3，n×m=gcd(n,m)×lcm(n,m)≥3×lcm(n,m)n \times m = gcd(n, m) \times lcm(n, m) \geq 3 \times lcm(n, m)，所以一次轮回一定覆盖不完
  • 若 gcd(n,m)==2gcd(n, m) == 2， n×m=gcd(n,m)×lcm(n,m)=2×lcm(n,m)n \times m = gcd(n, m) \times lcm(n, m) = 2 \times lcm(n, m)，刚好覆盖完
  • 若 gcd(n,m)==1gcd(n, m) == 1， n×m=gcd(n,m)×lcm(n,m)=lcm(n,m)n \times m = gcd(n, m) \times lcm(n, m) = lcm(n, m)，在走完一次后，下一次会从不同的方向再次覆盖相同格子，所以，会覆盖两次

唉，真的难绷，我是喜欢多想少些，但你这也 . . .好好好，玩儿阴的是吧

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    LL n, m, a, b ;
    cin >> n >> m >> a >> b;
    LL s = __gcd(n, a);
    LL t = __gcd(m, b);
    LL k = __gcd(n, m);
    if (s == 1 && t == 1 && k <= 2) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

D. Flip the Bit (Hard Version)

题意

这个是 B 的困难版本，两者的区别在于 D 不止一个特殊索引

思路

kk 个特殊索引将数组分成 k+1k + 1 组，每次进行操作，可同时将处于任意两组中的 ak‾\bar{a_k} -> aka_k，所以可以进行两两配对，但如果有一组过多，大于其余剩下之和，则答案就等于最大值，所以，最后答案等于 max(mx,sm2)max(mx, \frac{sm}{2})

反思

狭隘，太狭隘了，我当时只想到从两端开始讨论，相邻两个之间谁多一点，把另一边给包住，然后再往下延展，可以多包住几个，再在剩下部分的端点处找。呃，反正很混乱，没意识到每次操作的本质是消除任意两组中的 ak‾\bar{a_k}

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 5), mp(n + 5, 0);

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    int x;
    for (int i = 1; i <= k; ++i) {
        cin >> x;
        mp[x] = 1;
    }

    a[0] = a[x], a[n + 1] = a[x];

    int cnt = 0, sm = 0, mx = 0;

    for (int i = 1; i <= n + 1; ++i) {
        if (a[i] != a[i - 1]) {
            ++cnt;
        }
        if (mp[i] || i == n + 1) {
            sm += cnt;
            mx = max(mx, cnt);
            cnt = 0;
        }
    }

    cout << max(sm / 2, mx) << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

E. Definitely Larger

题意

对于排列 pp 和 qq，满足下列条件，称 jj 支配索引 ii：

  • j>ij > i
  • pj>pip_j > p_i
  • qj>qiq_j > q_i

给出 dd 数组，did_i 代表的含义是索引 ii 被多少个 jj 支配。

题目给出排列 pp 和数组 dd，问能否构造出排列 qq 满足 pp 和 qq 对应的数值

思路

不是很想说清楚这道题，其实也是因为我说不清楚，我一直想的思路都是错误的，很是挫败。我一直在想，这个比那个大，那个比这个小，这不就是拓扑排序吗，我就想（我先说明哈，以下思路都是错误的）每个 pip_i 后面都有 kk 个大于他的 pj p_j， k≥d[i]k \geq d[i]，一定是越往后面的越大越好（不知道当时咋就这么认为了，我好像还说服了一下我自己，因为如果去确定更靠前的数为更大，那么这个数后面还有比他大的数这是 did_i 确定的，那么就会让支配 pip_i 的个数自动增加），所以就从后往前找，对于 pj>pip_j > p_i ，同时 k≤dik \leq d_i ，就让 jj 指向 ii ，对于 pj>pip_j > p_i，但 k>dik > d_i ，就让 ii 指向 jj ，最后根据出度为零，从小到大赋值，走一遍拓扑排序

但不出所料，对拍出了反例

6
4 5 3 1 6 2 
1 0 0 1 0 0

每个点都有出度，但是可以构造出来 5 6 4 2 3 1，我后来反思了一下，对于后面具体是谁大于该数，谁小于该数，不应该无脑从后往前确定相对大小关系

OK，说正解的思路，在有很多变量的情况下，去找相对不变的量，对于多个 di=0d_i = 0 ，我们可以确定其中一个一定会被赋予当前未使用过的最大值，而且是从左往右赋值（等会儿说），当 qiq_i 被赋值后，它会影响什么？j<ij < i 且 pj<pip_j < p_i 的索引 jj，支配 jj 的 djd_j 个数少一，所以 dj−−d_j–，然后重复开始的操作，再去找最左边 di=0d_i = 0 的索引，把当前没用过的最大值赋值给 pip_i

为什么是从左往右赋值？

我说不清楚，但可以举个例子帮助理解

3
1  2 3
0 0 0

如果从右往左赋值，就会是 1 2 3，那么对应的 d 数组为 2 1 0，不符合

其实是因为对于每个 ii ，在 j>ij > i 中，pj>pi p_j > p_i 的 jj 有多个，可能会超过 did_i，如果先把大的值赋值给后面，当把更小的值赋值给前面的 pkp_k 后，很可能会使你以为已经确定的 did_i 增加，使最终构造出来的 di‘>did_i` > d_i，而如果大的值在前面，就断掉了 did_i 继续增加的可能，后面的 pkp_k 无论如何赋值，永远都小于 qiq_i

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    int n;
    cin >> n;
    vector<int> p(n + 1, 0), d(n + 1, 0), q(n + 1, 0);

    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> d[i];
    }

    for (int k = n; k >= 1; --k)
    {
        int f = 0;
        for (int i = 1; i <= n; ++i)
        {
            if (d[i] == 0 && !q[i])
            {
                q[i] = k;
                for (int j = 1; j < i; ++j)
                {
                    if (p[j] < p[i]) {
                        d[j] = max(0, d[j] - 1);
                    }
                }
                f = 1;
                break;
            }
        }
        if (!f) {
            cout << -1 << endl;
            return;
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        cout << q[i] << " ";
    }
    cout << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

Post authorWritten by

Leave a Comment

您的邮箱地址不会被公开。 必填项已用 * 标注