Pinely Round 2 (Div. 1 + Div. 2)

发表于 2023-09-11 分类于 codeforces ， contest

Pinely Round 2 (Div. 1 + Div. 2)

Complete problemset

A. Channel

题意

有一个频道群组，共有n个订阅该频道的网民，现在发表了一篇帖子在这个频道内，初始在线人数是a，后续随着时间变化，会告知有用户上线或者下线。

假设上线的人一定会阅读，你需要确定是否所有人都会阅读这篇帖子。

思路

在最“好”的情况下，就是每次上线的是优先没有看过帖子的人。如果这种情况都不能大于等于n，则答案是否。

在最“坏”的情况下，就是每次上线的是优先看过帖子的人。如果这种情况能大于等于n，则答案是是。

否则就是有可能。

代码

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n, a, q;
    cin >> n >> a >> q;
    string s;
    cin >> s;
    if (a + count(s.begin(), s.end(), '+') < n) {
        cout << "NO\n";
        return;
    }
    int ok = a == n;
    for (char i : s) {
        if (i == '+') {
            a++;
        } else {
            a--;
        }
        if (a >= n)
            ok = 1;
    }
    cout << (ok ? "YES" : "MAYBE") << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

B. Split Sort

题意

给出一个长度为n的排列。

每次操作将创建一个新排列替代旧排列：选择一个数x，将所有小于x的数不改变原有顺序写下来，然后将大于等于x的数不改变原有顺序写下来。

求最少需要多少次操作，使得排列变为有序。

思路

记录每个数所在位置

从大到小考虑每一个数，对于一个数x，如果它左边没有比他小的数，那么就指定它进行一次操作。

代码

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n;
    cin >> n;
    vector<int> a(n), p(n + 1);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        p[a[i]] = i;
    }
    int ans = 0;
    for (int i = n; i > 1; i--) {
        ans += p[i - 1] > p[i];
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

C. MEX Repetition

题意

给出$a_1,a_2,\ldots, a_n$，n个不同的数，每个数的取值在0到n。

每次操作，从1到n逐个将$a_i$替换为$MEX(a_1, a_2, \ldots, a_n)$

请输出k次操作后的序列。

思路

我们找规律，先将0到n中没有出现的数x找出来，放在序列后。$a_1,a_2,\ldots, a_n, x$

一次操作后序列将变为$x, a_1,a_2,\ldots, a_n$

k次操作显而易见。

代码

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n), vis(n + 1);
    for (int& i : a) {
        cin >> i;
        vis[i] = 1;
    }
    for (int i = 0; i <= n; i++) {
        if (!vis[i]) {
            a.push_back(i);
            break;
        }
    }
    n++;
    for (int i = 0, b = n - k % n; i < n - 1; i++) {
        cout << a[(i + b) % n] << " ";
    }
    cout << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

D. Two-Colored Dominoes

题意

给出一个放置了多米诺骨牌的图。

现在要求给每一块多米诺骨牌涂色，一块牌将一半涂为黑色一半涂为白色。

问是否存在涂色后每一行每一列，黑白色数目相同。

如果有，则构造答案。

思路

对于每一行来说，横着摆放的牌可以忽略，因为给这一行的贡献是一黑一白。那么忽略横牌后，竖牌的个数必须是偶数，不然就没有答案。

对于每一列同理。

初步结论就是只要是行和列的骨牌所占格数是偶数才有答案。

但是如何构造答案。

拿行来说，对于一行里第一个出现的没有涂色的列骨牌，我们将其涂为白色，第二个涂为黑色，第三个…，这样黑白交替的涂色。由于竖着的骨牌也会覆盖其他行，但是这样的涂色方案并不会打破其他行黑白平衡。

代码

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

/*
优先用白色的错误
LRLR
.LR.
.LR.
LRLR

WBWB
.WB.
.WB.
BWWB
*/

void sol() {
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (auto& i : g)
        cin >> i;

    vector<string> ans(n, string(m, '.'));
    for (int i = 0; i < n; i++) {
        int cnt = 0;
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 'U') {
                cnt++;
                if (cnt % 2) {
                    ans[i][j] = 'W';
                    ans[i + 1][j] = 'B';
                } else {
                    ans[i][j] = 'B';
                    ans[i + 1][j] = 'W';
                }
            }
        }
        if (cnt % 2) {
            cout << "-1\n";
            return;
        }
    }
    for (int j = 0; j < m; j++) {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (g[i][j] == 'L') {
                cnt++;
                if (cnt % 2) {
                    ans[i][j] = 'W';
                    ans[i][j + 1] = 'B';
                } else {
                    ans[i][j] = 'B';
                    ans[i][j + 1] = 'W';
                }
            }
        }
        if (cnt % 2) {
            cout << "-1\n";
            return;
        }
    }
    for (auto& i : ans) {
        cout << i << "\n";
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

E. Speedrun

题意

现在有n个任务，第i个任务只能在一天的第$h_i$时刻完成，一天的时间为k小时。

现在给出m个依赖，有些任务在完成前依赖另一个任务先完成。

求完成任务的最少跨越时间（最后一个任务完成的时刻-第一个任务完成的时刻）

思路

我们拓扑排序，可能会得到多个个殊途同归的依赖树。并且知道这些依赖的开始时刻和结束时刻。

我们对入度为0的点进行时间延后一天，那么他会影响后续所有依赖它的点。受影响的点也会延后一天。

一个点可以有多个依赖，如果其中一个依赖延后了，导致了当前点延后了。这时其他的依赖延后，不会再次影响当前点了。也就是说每个点最多延后一次。

我们可以按照时间先后将所有入度为0的点进行排序，注意可能有多个点的时间一样。

将同一时间的点考虑延后，这样就让开始时刻延后。然后对依赖它的点进行更新，更新结束时刻。

维护最小的完成跨越时间。

代码

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    ll n, m, k;
    cin >> n >> m >> k;
    vector<ll> h(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }
    vector<int> g[n + 1];
    vector<ll> in(n + 1), cnt(n + 1), t(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        in[y]++;
    }
    ll mxt = 0;
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (in[i] == 0) {
            t[i] = h[i];
            q.push(i);
        }
    }
    while (q.size()) {
        int u = q.front();
        q.pop();
        mxt = max(mxt, t[u]);
        for (int v : g[u]) {
            if (h[v] >= t[u] % k) {
                t[v] = max(t[v], t[u] - t[u] % k + h[v]);
            } else {
                t[v] = max(t[v], t[u] + k - t[u] % k + h[v]);
            }

            if (in[v] == ++cnt[v]) {
                q.push(v);
            }
        }
    }
    map<ll, vector<int>> mp;
    for (int i = 1; i <= n; i++) {
        if (in[i] == 0) {
            mp[t[i]].push_back(i);
        }
    }
    auto udp = [&](int x) {
        queue<int> q;
        q.push(x);
        while (q.size()) {
            int u = q.front();
            q.pop();
            mxt = max(mxt, t[u]);
            for (int v : g[u]) {
                if (t[v] < t[u]) {
                    t[v] += k;
                    q.push(v);
                }
            }
        }
    };
    ll ans = 1e18;
    for (auto& [i, j] : mp) {
        ans = min(ans, mxt - i);
        for (int u : j) {
            t[u] += k;
            udp(u);
        }
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

F. Divide, XOR, and Conquer

题意

思路

代码

1
2

G. Swaps

题意

思路

代码

1
2

H. Goldberg Machine 3

题意

思路

代码

1
2

I. Redundant Routes

题意

思路

代码

1
2