Educational Codeforces Round 193 (Rated for Div. 2)

by JiuQiin Codeforces, 题解on Posted on
「那天，我听到了种子破土的声音，又细微又坚定。」
— 夏达 · 子不语
首页 » 题解 » Codeforces » Educational Codeforces Round 193 (Rated for Div. 2)
Contents hide
1 A. The Best Card
1.1 题意
1.2 思路
1.3 代码
2 B. Hypercarp and the Control Panel
2.1 题意
2.2 思路
2.3 代码
3 C. Sum of Distinct Values in a Matrix
3.1 题意
3.2 思路
3.3 代码
3.4 大佬的写法
3.5 对拍代码
4 D. Hypercarp and Interdimensional Jumps
4.1 题意
4.2 思路
4.3 代码

A. The Best Card

题意

给出 n 张上面分别写着 2, 3, 4, 5, 6, . . . n + 2 的牌，根据以下规则判断那张牌能赢：

  • 若 x 能被 y 整除，则 y 赢（y < x）
  • 若 x 不能被 y 整除，则 x 赢 (y < x)

判断是否存在必赢的牌

思路

若最大的那张牌无法被任何数整除，则最大的那张牌为必赢牌

反证法，若不是最大的那张牌，而是能整除其余牌的较小牌 x ，则对于它的倍数来说，它是必赢的，但是若 y = x + 1，y 一定与 x 互质，且 y > x，则 y 赢

如果你说不存在 x + 1，则 x 一定为最大值，反过来又证明了最开始的想法

代码

// 你爱它的清新又厌它的寡淡，喜恶同因，它只是水而已
#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 = 3e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;
const LL N = 3e6 + 10;

int vis[MAX];
vector<int> primes;

void isPrime() {
    for (int i = 2; i <= N; ++i) {
        if (!vis[i]) primes.push_back(i);
        for (int j : primes) {
            if (i * j > N)
                break;
            vis[i * j] = 1;
            if (i % j == 0)
                break;
        }
    }
}

void solve() {
    int n;
    cin >> n;
    if (!vis[n + 1]) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
}

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

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

B. Hypercarp and the Control Panel

题意

给出 n 个数，每个数的颜色为 aia_i，你可以先删除任意个数，之后最多进行一次交换，使得最后剩下的数相邻颜色不同，问，最后最多可剩多少个数字

思路

什么情况下交换才可以产生贡献呢？

对于在同一个模块中的数（连续数字的颜色相同）来说，交换是无意义的，只有在不同模块中的交换才有意义

若 1 2 交换，再看 1 的左边和 2 的右边：

若是 1 1 2 1，交换后为 1 2 1 1 ，则交换不产生新的贡献

若是 1 1 2 3，交换后为 1 2 1 3，则交换产生一个贡献

若是 1 1 2 2，交换后为 1 2 1 2，则交换产生两个贡献

代码

// 你爱它的清新又厌它的寡淡，喜恶同因，它只是水而已
#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;
    cin >>n;

    vector<LL> a(n+1), b;
    for (LL i = 1; i <= n; ++i) {
        cin >> a[i];
        if (!b.empty() && a[i] == b.back()) {
            continue;
        }
        b.push_back(a[i]);
    }

    LL ans = b.size();

    for (LL i = 1; i <= n - 1; ++i) {
        if (i == 2 && a[i] == a[i + 1] && a[i] != a[i - 1]) {
            ans++;
            break;
        }
        if (i >= 3 && a[i] == a[i + 1] && a[i] != a[i - 1] && a[i - 2] != a[i]) {
            ++ans;
            break;
        }
        if (i == n - 2 && a[i] == a[i + 1] && a[i + 1] != a[i + 2]) {
            ans++;
            break;
        }
        if (i <= n - 3 && a[i] == a[i + 1] && a[i + 1] != a[i  +2] && a[i + 3] != a[i]) {
            ++ans;
            break;
        }
    }

    for (LL i = 3; i <= n - 1; ++i) {
        if (a[i] != a[i - 1] && a[i] == a[i + 1] && a[i - 1] == a[i - 2]) {
            ans++;
            break;
        }
    }

    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. Sum of Distinct Values in a Matrix

题意

给你一个 n 行 m 列的矩阵，给出两个数组分别为 a，b，每次可从 a 数组中选取数字填入一整行中，或者从 b 数组中选取数字填入一整列中，问，最后最多有多少种不同的数字在矩阵中

思路

发现，最后的答案无非是四种情况：

  • 全都是在 a 数组中选取 n 个填入行中
  • 全都是在 b 数组中选取 m 个填入列中
  • 先填 n 行，然后填 m – 1 列
  • 先填 m 列，然后填 n – 1 行

第三，四种情况可以包含前两种情况，所以，总结下来，本质是从 a ，b 数组中最多选取 n + m – 1 个数字， a 数组最多选 n 个，b 数组最多选 m 个，问最后最多有多少个不同的数字

所以，本质是在求 a 数组与 b 数组的并集的前 n + m – 1 个数字

代码

// 你爱它的清新又厌它的寡淡，喜恶同因，它只是水而已
#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 = 2e5 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;
const LL N = 2e5  +10;

struct Node {
    LL x, id;
    bool operator<(const Node &t) const {
        return x > t.x;
    }
};

void solve() {
    LL n, m, x, y;
    cin >> n >> m >> x >> y;

    vector<LL> a(n + m + 1, 0), b(n + m + 1, 0);

    for (LL i = 1; i <= x; ++i)
        cin >> a[i];
    for (LL i = 1; i <= y; ++i)
        cin >> b[i];

    sort(a.begin() + 1, a.end(), greater<LL>());
    sort(b.begin() + 1, b.end(), greater<LL>());


    LL ans = 0;

    auto calc1 = [](LL k, vector<LL> &a)
    {
        LL sm = 0;
        LL len = a.size() - 1;
        for (LL i = 1; i <= min(k, len); ++i)
        {
            sm += a[i];
        }
        return sm;
    };

    auto calc2 = [](LL k1, LL k2, vector<LL> &a, vector<LL> &b, int x, int y) {
        LL sm = 0;    
        map<LL, LL> mp;
        LL cnt = 0;
        for (LL i = 1; i <= k1; ++i) {
            if (a[i] == 0)
                continue;
            mp[a[i]]++;
            sm += a[i];
        }
        for (LL i = 1; i <= k2; ++i) {
            if (b[i] == 0)
                continue;
            mp[b[i]]++;
            if (mp[b[i]] == 2) {
                ++cnt;
                continue;
            }
            sm += b[i];
        }

        LL l1 = k1 + 1;
        LL l2 = k2 + 1;
        LL r1 = k1 + cnt;
        LL r2 = k2 + cnt;

        // cout << cnt << endl;
        // cout << sm << " " << l1 << " " << r1 << " " << l2 << " " << r2 << endl;
        vector<LL> c;
        for (LL i = l1; i <= x; ++i) {
            c.push_back(a[i]);
        }
        for (LL i = l2; i <= y; ++i) {
            c.push_back(b[i]);
        }

        sort(c.begin(), c.end(), greater<LL>());

        LL tot = 0;
        for (LL v : c) {
            if (mp.count(v)) continue;
            if (tot == cnt)
                break;
            mp[v]++;
            sm += v;
            ++tot;
        }

        return sm;
    };

    ans = max(calc1(n, a), ans);
    // cout << calc1(n, a) << endl;
    ans = max(calc2(n, m - 1, a, b, x, y), ans);
    ans = max(calc1(m, b), ans);
    // cout << calc1(m, b) << endl;
    ans = max(calc2(m, n - 1, b, a, y, x), 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;
}

大佬的写法

大佬的写法很牛的一点是完美模拟了在 a 与 b 的并集中选取最多选取 n + m – 1 个的过程

x : 已选取的 a 数组中的个数

y：已选取的 b 数组中的个数

k：总的可选取的个数

若 aia_i > bjb_j ，则选取 aia_i , x++，若 bj>aib_j > a_i ，则选取 bjb_j , y++，这些都没问题，但是若 ai=bja_i = b_j 呢，选取谁呢？

我们不管选取谁，总的可选个数一定会减一，所以 k–，只要保证已选取的个数小于等于总的可选个数即可

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long

void solve() {
    int n, m, A, B;
    cin >> n >> m >> A >> B;
    vector<int> a(A + 1), b(B + 1);

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

    sort(a.begin() + 1, a.end(), greater<int>());
    sort(b.begin() + 1, b.end(), greater<int>());

    int i = 1, j = 1,ans = 0,k = n + m - 1, x =0 , y = 0;
    while (x < n && y < m && i <= A && j <= B && x + y < k) {
        if (a[i] > b[j]) {
            ans += a[i++];
            ++x;
        }
        else if (a[i] < b[j]) {
            ans += b[j++];
            ++y;
        }
        else {
            ans += a[i++];
            ++j;
            --k;
        }
    }

    while (x < n && i <= A && x  + y < k) {
        ans += a[i++];
        ++x;
    }

    while (y < m && j <= B && x + y < k) {
        ans += b[j++];
        ++y;
    }

    cout << ans << endl;
}

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

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

对拍代码

这不是我写的，是 chatGPT 写的，我只是觉得写得极好，可以学习一下

#include <bits/stdc++.h>
using namespace std;

using LL = long long;

LL n, m, x, y;
vector<LL> a, b;
LL ans;

void calc(vector<LL>& rv, vector<LL>& cv) {
    vector<int> id;

    for (int i = 0; i < n; ++i)
        if (rv[i] != 0)
            id.push_back(i);

    for (int i = 0; i < m; ++i)
        if (cv[i] != 0)
            id.push_back(n + i);

    sort(id.begin(), id.end());

    do {
        vector<int> tim(n + m, -1);

        for (int i = 0; i < (int)id.size(); ++i)
            tim[id[i]] = i;

        set<LL> s;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (rv[i] == 0 && cv[j] == 0) {
                    s.insert(0);
                }
                else if (rv[i] == 0) {
                    s.insert(cv[j]);
                }
                else if (cv[j] == 0) {
                    s.insert(rv[i]);
                }
                else {
                    if (tim[i] > tim[n + j])
                        s.insert(rv[i]);
                    else
                        s.insert(cv[j]);
                }
            }
        }

        LL cur = 0;
        for (LL v : s)
            cur += v;

        ans = max(ans, cur);

    } while (next_permutation(id.begin(), id.end()));
}

void dfsCol(int pos, vector<LL>& rv, vector<LL>& cv) {
    if (pos == m) {
        calc(rv, cv);
        return;
    }

    cv[pos] = 0;
    dfsCol(pos + 1, rv, cv);

    for (int i = 0; i < y; ++i) {
        cv[pos] = b[i];
        dfsCol(pos + 1, rv, cv);
    }
}

void dfsRow(int pos, vector<LL>& rv, vector<LL>& cv) {
    if (pos == n) {
        dfsCol(0, rv, cv);
        return;
    }

    rv[pos] = 0;
    dfsRow(pos + 1, rv, cv);

    for (int i = 0; i < x; ++i) {
        rv[pos] = a[i];
        dfsRow(pos + 1, rv, cv);
    }
}

void solve() {
    cin >> n >> m >> x >> y;

    a.resize(x);
    b.resize(y);

    for (auto& v : a)
        cin >> v;

    for (auto& v : b)
        cin >> v;

    ans = 0;

    vector<LL> rv(n), cv(m);

    dfsRow(0, rv, cv);

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int TestsNumT;
    cin >> TestsNumT;

    while (TestsNumT--)
        solve();

    return 0;
}

D. Hypercarp and Interdimensional Jumps

题意

最开始在 (0, 0)这一点，给出 (x, y)，每次横坐标加一（a++），或者纵坐标加一(b++)，然后，横向上跳 a 步，纵向上跳 b 步，问，在保证不跳出由 (0, 0) 和 (x, y) 构成的矩形中，最接近 (x, y) 点的跳法是什么

思路

贪心{\color{yellow}贪心}

假设最后一共跳了 kk 次，则倒数第 jj 次对答案的贡献是 jj，因为你当前加一，你后面每一次都会把这个一带着，所以，跳的总距离是 k(k+1)2\frac{k(k+1)}{2}，而在 xx 方向上，要保证跳的总距离 p≤xp \leq x，在 yy 方向上，保证跳的总距离 q≤yq \leq y，所以 p+q=k(k+1)2≤x+yp + q = \frac{k(k+1)}{2} \leq x +y，得 kk

再从 p+q≤k(k+1)2p + q \leq \frac{k(k+1)}{2} 中，根据 p≤x,q=k(k+1)2−p≤yp \leq x, q = \frac{k(k +1)}{2} – p \leq y 找到 pp 的上下限，然后遍历，找到最优的 pp 和 qq。这个遍历不会超时，因为根据之前 k(k+1)2≤x+y⇒k=O(x+y)\frac{k(k+1)}{2} \leq x+y \Rightarrow k= O(\sqrt{x+y})，枚举的次数也就 1e4 数量级

接下来我觉得是最有意思的部分，其思想类似于倍增，当你你构造一个二进制字符串来表示一个十进制数时，怎么做，从高位到地位去试探，看加上 (1<<i)(1 << i) 会不会超过 xx 。这个也是同样，用贪心的思想，看这一位放 ‘X’‘X’ , 会不会超过最终的 pp，若不会，则放置 ‘X’‘X’，若会，则放置 ‘Y’‘Y’

代码

// 你爱它的清新又厌它的寡淡，喜恶同因，它只是水而已
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int INF = 0x3f3f3f3f3f3f3f;

void solve() {
    int x, y;
    cin >> x >> y;

    int k = 0;
    while ((k + 1) * (k + 2) / 2 <= x + y) {
        ++k;
    }

    int mn = INF, sx = 0;

    for (int p = (k + 1) * k / 2 - y; p <= x; ++p) {
        int q = k * (k  +1)/ 2 - p;
        if ((x - p) * (x - p) + (y - q) * (y -q) < mn) {
            mn = (x - p) * (x - p) + (y - q) * (y - q);
            sx = p;
        }
    }

    string ans = "";
    int p = 0;

    for (int i = 1; i <= k; ++i)
    {
        int w = k - i + 1;

        if (p + w <= sx)
        {
            p += w;
            ans.push_back('X');
        }
        else
        {
            ans.push_back('Y');
        }
    }

    cout << ans << endl;
}

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

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

Leave a Comment

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