Codeforces Round #656 (Div. 3)Codeforces Round #656 (Div. 3)

75 阅读 0 评论 50 点赞

我是靠谱客的博主忧郁大白，最近开发中收集的这篇文章主要介绍Codeforces Round #656 (Div. 3)Codeforces Round #656 (Div. 3)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

文章目录

Codeforces Round #656 (Div. 3)
- A. Three Pairwise Maximums
- B. Restore the Permutation by Merger
- C. Make It Good
- D. a-Good String
- E. Directing Edges
- F. Removing Leaves
- G. Columns Swaps

Codeforces Round #656 (Div. 3)

A. Three Pairwise Maximums

题意: 给定t个测试样例,每个测试样例给定x，y，z，需要找到a，b，c三个数，使得max(a, b)=x, max(a, c)=y, max(b, c)=z，输出a，b，c(顺序无所谓)，如果找不到输出NO。t~2e4, a、b、c~1e9
题解： max(a, b) = x, max(a, c) = y, 则max(a, b, c) = max(x, y)，同理max(a, b, c) = max(x, y) = max(y, z) = max(x, z)，则①x=y=z，②x < y = z。因此，只需要把x, y, z排序，最小的为x，中间的为y，最大的为z，判断y是否为z，不相等为NO，相等的话，输出x, x, y
代码:

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int a[3];
    int T ;
    cin >> T;
    while (T--) {
        for (int i = 0; i < 3; ++i) scanf("%d", &a[i]);
        sort(a, a + 3);
        if (a[1] != a[2]) {
            cout << "NOn";
            continue;
        }
        cout << "YESn";
        cout << a[0] << " " << a[0] << " " << a[1] << endl;
    }
    return 0;
}

B. Restore the Permutation by Merger

题意： t个测试样例，每个测试样例输入长度为2n的数组，该数组是由两个不改变相对位置的全排列数组merge而成的，每次要求输出原来的全排列数列。t ~ 400，n ~ 50
题解： 观察可以知道，同样的数字只需要取前一个出现的那个即可，因此，只需要扫一遍，如果这个数字没出现过，那么打印；如果没出现过，那么跳过
代码

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

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        unordered_map<int, int> mp;
        for (int i = 1, x; i <= n * 2; ++i) {
            cin >> x;
            if (mp.count(x)) continue;
            cout << x << " " ;
            mp[x] = 1;
        }
        cout << endl;
    }
    return 0;
}

C. Make It Good

题意: 定义一个good数列：每次从该数列的头或者尾拿出一个数字，拿出来的数字是单调不减的。现在给定t个测试样例，每个测试样例给定一个长度为n的数列，问需要将长度为n的数列的删除前k个数字，使之变为good数列，这个k最小取多少？ $sum_{} n~2e5$
题解: 对于任意两个数字x, y，如果这两个数字都是从前面拿出，那么需要x <= y；对于任意两个数字x和y，如果这两个数字都是从后面被拿出，那么需要x >= y，因此只需要倒着往前扫，找到类似小山坡的形状，即先增加后下降，一旦再次上升，即为到达边界。
代码:

#include <bits/stdc++.h>
 
using namespace std;
 
int const N = 2e5 + 10;
int a[N];
 
int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n ; ++i) {
            scanf("%d", &a[i]);
        }
        if (n == 1) {
            cout << 0 << endl;
            continue;
        }
        int i = n - 1;
        while (a[i] >= a[i + 1] && i >= 1) i--;
        while (a[i] <= a[i + 1] && i >= 1) i--;
        cout << i << endl;
    }
    return 0;
}

D. a-Good String

题意： 定义一个’a’-good字符串为:

字符串长度为1，且只有一个字符’a’
字符串长度大于1，前半部分全为’a’，后半部分为’b’-good字符串
字符串长度大于1，后半部分全为’a,’,前半部分为’b’-good字符串
现在有t个测试样例，每个测试样例给定一个长度为n的字符串，每次操作可以把任意位置的一个字符替换为任意一个小写字母，问最少需要多少次这样的操作后，才能使得当前字符串为’a’-good字符串?保证所有的字符串总长度为2e5

题解： 仔细分析可知，‘a’-good字符串是递归定义的，肯定为一半为a，另一半的前一半为b。另一半的后一半的前一半为c，。。。，即出现16-8-4-2-1这样的情况，因此每次只需要把当前字符串分为两半，分别统计两半内当前字符哪个出现的多，少的那个则为b字符串处理，不断dfs即可，由于这个规模不大，因此不会超时
代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
int const MAXN = 2e5 + 10;
int n, m, T;
string s;

int dfs(int st, int ed, char c) {
    if (st == ed) return (s[st] != c);
    int cnt1 = 0, cnt2 = 0;
    for (int i = st; i <= (st + ed) / 2; ++i) if (s[i] != c) cnt1++;
    for (int i = (st +ed) / 2 + 1; i <= ed; ++i) if (s[i] != c) cnt2 ++;
    return min(dfs(st, (st + ed) / 2, c + 1) + cnt2, dfs((st + ed) / 2 + 1, ed, c + 1) + cnt1);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> T;
    while(T--) {
        cin >> n >> s;
        cout << dfs(0, n - 1, 'a') << endl;
    }
    return 0;
}

E. Directing Edges

题意： 给定t个测试样例，每个测试样例给定n和m，n为图的点数，m为图的边数，给定m条边，每条边为op, a, b。如果op为1,表示有一条有向边a -> b;如果op为0，表示a和b之间有一条无向边。现在要求把无向边变成有向边(把a–b变成a->b或b->a)，使得最后这m条边没有环。【累加】n、m~2e5
题解： 题意可以转换为现在有一张有向图，要求向这张有向图内加入有向边，使得这张有向图没有环，求加边的方法。因此，可以先做一次拓扑排序，求出拓扑序，如果没有拓扑序，说明已经存在环；否则，只需要加入拓扑序小的指向拓扑序大的边即可。(因为想要形成环，必须有回路，则必须a->b，同时b->a,一旦出现拓扑序，说明存在a->b,不存在b->a,因此只要不加入b->a,则不可能出现环)
代码如下：

#include<bits/stdc++.h>

using namespace std;

int const N = 2e5 + 10;
int t, n, m;
set<int> point;
int e[N * 2], ne[N * 2], idx, h[N];
int d[N], sorted[N];
vector<pair<int, int> > undirect, direct;
vector<int> ans;
struct Edge{
    int op, u, v;
};
vector<Edge> E;

void top_sort() {
    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (!d[i]) {
            // cout << i << endl;
            q.push(i);
        }
    }
    while (q.size()) {
        auto t = q.front();
        q.pop();
        ans.push_back(t);

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            d[j]--;
            if (!d[j]) {
                q.push(j);
            }
        }
    }
    for (int i = 0; i < ans.size(); ++i) {
        sorted[ans[i]] = i + 1;
    }
    return ;
}

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
 
int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    cin >> t;
    while (t--) {
        memset(h, -1, sizeof h);
        memset(d, 0, sizeof d);
        idx = 0;
        E.clear();
        memset(sorted, 0, sizeof sorted);
        ans.clear();
        cin >> n >> m;
        for (int i = 0, op, a, b; i < m; ++i) {
            scanf("%d%d%d", &op, &a, &b);
            E.push_back({op, a, b});
            if (op == 1) {
                add(a, b);
                d[b]++;
            }
        }
        top_sort();
        // cout << ans.size() << endl;
        if (ans.size() != n) {
            cout << "NOn";
            continue;
        }
        cout << "YESn";
        for (int i = 0; i < E.size(); ++i) {
            if (E[i].op == 1) {
                cout << E[i].u << " " << E[i].v << endl;
            }
            else {
                if (sorted[E[i].u] < sorted[E[i].v]) cout << E[i].u << " " << E[i].v << endl;
                else cout << E[i].v << " " << E[i].u << endl;
            }
        }
    }
    return 0;
}

F. Removing Leaves

题意： t个测试样例，每个测试样例给定一棵有n个节点的无根树，每次选择一个有k个叶子的节点，删除这k个叶子，问最多能够做多少次这样的操作？第一行输入t，而后每个样例先输入n和k，再输入n-1条边。t ~ 2e4, $sum_{}n<=2e5$
题解： 可以从叶子的角度思考问题。当一个节点周围的叶子数目达到k的倍数的时候，答案才会加一。因此，我们可以维护一个队列，里面存放的时候当前的叶子。按照类似拓扑排序的方式进行更新，使用vis数组标记当前叶子是否存活。对于这种一圈一圈删除的问题，很多时候都是使用拓扑排序来处理。
代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
int const MAXN = 2e5 + 10, MAXM = MAXN * 2;
int n, m, T, k;
int vis[MAXN], e[MAXM], ne[MAXM], h[MAXN], idx, d[MAXN], cnt[MAXN];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> T;
    while(T--) {
        cin >> n >> k;
        for (int i = 1; i <= n; ++i) vis[i] = 0, h[i] = -1, d[i] = cnt[i] = 0;
        idx = 0;
        for (int i = 1, a, b; i < n; ++i ) {
            cin >> a >> b;
            add(a, b), add(b, a);
            d[a] ++, d[b] ++;
        }
        queue<int> q;
        for (int i = 1; i <= n; ++i) if (d[i] == 1) q.push(i);
        int res = 0;
        while(q.size()) {
            auto t = q.front();
            q.pop();
            vis[t] = 1;
            for (int i = h[t]; ~i; i = ne[i]) {
                int j = e[i];
                if (vis[j]) continue;
                d[j]--, cnt[j] ++;
                if (cnt[j] % k == 0) {
                    res++;
                    if (d[j] == 1) q.push(j);
                }
            }
        }
        cout << res << endl;
    }
    return 0;
}

G. Columns Swaps

大意：

给出一个2xn的矩阵，问能否通过交换某几列的第一行和第二行，使得第一行和第二行都是1到n的全排列

思路：

首先统计1到n出现的次数，必须都是两次否则输出-1

然后利用拓展域并查集，i代表这一列不换，i+n代表这一列需要变换

这样如果某个数出现在同一行，假设出现的位置分别为i和j，那么合并i和j+n，以及i+n和j

否则合并i和j i+n和j+n

这样最后会出现很多小联通块，这时候就选择i和i+n中数量较小的那一个即可

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;
typedef long long LL;
int t;
int a[N][2], n, cnt[N], pre[N], Size[2 * N], vis[2 * N], res[N], rescnt;
int f[2 * N];
int findf(int x) { return x == f[x] ? x : f[x] = findf(f[x]); }
void Union(int x, int y) {
    int fx = findf(x), fy = findf(y);
    if (fx != fy) {
        f[fx] = fy;
        Size[fy] += Size[fx];
    }
}
int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++) cnt[i] = 0, pre[i] = 0;
        for (int i = 1; i <= n; i++) cin >> a[i][0], cnt[a[i][0]]++;
        for (int i = 1; i <= n; i++) cin >> a[i][1], cnt[a[i][1]]++;
        int flag = 1;
        for (int i = 1; i <= n; i++)
            if (cnt[i] != 2) {
                flag = 0;
            }
        if (flag == 0) {
            printf("-1n");
            continue;
        }
        for (int i = 1; i <= n; i++) {
            f[i] = i, f[i + n] = i + n;
            Size[i] = 0, Size[i + n] = 1;
            vis[i] = vis[i + n] = 0;
        }
        for (int i = 0; i < 2; i++) {
            for (int j = 1; j <= n; j++) {
                int now = a[j][i];
                if (pre[now] == 0)
                    pre[now] = j;
                else {
                    if (pre[now] == j) continue;
                    int k = pre[now];
                    if (a[k][i] == now) {  //同一行
                        int fx = findf(k), fy = findf(j);
                        int fx2 = findf(k + n), fy2 = findf(j + n);
                        if (fx == fy)
                            flag = 0;
                        else
                            Union(fx, fy2), Union(fx2, fy);
                    } else {
                        int fx = findf(k), fy = findf(j);
                        int fx2 = findf(k + n), fy2 = findf(j + n);
                        if (fx == fy2)
                            flag = 0;
                        else
                            Union(fx, fy), Union(fx2, fy2);
                    }
                }
            }
        }
        for (int i = 1; i <= n; i++)
            if (findf(i + n) == findf(i)) {
                flag = 0;
                break;
            }
        if (flag == 0) {
            printf("-1n");
            continue;
        }
        for (int i = 1; i <= n; i++) {
            int x = findf(i), y = findf(i + n);
            // if (x == i && y == (i + n)) continue;
            if (!vis[x] && !vis[y]) {
                if (Size[x] > Size[y])
                    vis[y] = 1;
                else
                    vis[x] = 1;
            }
        }
        rescnt = 0;
        for (int i = 1; i <= n; i++) {
            if (vis[f[i + n]]) res[rescnt++] = i;
        }
        printf("%dn", rescnt);
        for (int i = 0; i < rescnt; i++) printf("%d ", res[i]);
        printf("n");
    }
    return 0;
}