Codeforces Round 1042 (Div. 3)

codeforces, 题解

A Lever

题目描述

给定两个长度为的数组 , .现在有以下两个操作：

选择一个下标 ,若，则. 如果不存在这样的，则忽略此步骤.

选择一个下标 ,若，则. 如果不存在这样的，则忽略此步骤.
当执行完第二步都会检查第一步是否执行，若未执行则直接结束。
问：迭代的次数是多少？

解题思路

可以发现两个操作都是操作数组，数组没有变化过。既然这样，我们就可以只考虑和的大小关系. 不懂的，可以看样例1.

参考代码

void solve() {
    int n;
    std::cin >> n;
    int ans = 1;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
       std::cin >> a[i];
    }
    for (int i = 0, x; i < n; i++) {
       std::cin >> x;
       if (a[i] > x) ans += a[i] - x;
    }
    std::cout << ans << std::endl;
}

B Alternating Series

题目描述

构造一个数组 ,使得数组的字典序最下,并且长度大于等于的子数组的和为正数。

解题思路

可以发现奇数位可以先填,这样可以保证字典序最小,依次考虑偶数位,由于前后都是,且要保证和大于等于,那么偶数位只能填.虽然这样填可以满足和为正数,但是会有个新的问题,不能保证字典序最小.

例如的构造： $，$ ，当取第，位的长度为的子数组就会发现，最后一位可以为，依次可以推理出：当长度为偶数，那么最后一位应该为。

参考代码

void solve() {
    int n;
    std::cin >> n;
    for (int i = 0; i < n; i++) {
       if (i % 2 == 0) {
          std::cout << -1 << ' ';
       } else if (i == n - 1) {
          std::cout << 2 << "\n";
       } else {
          std::cout << 3 << ' ';
       }
    }
}

C Make it Equal

题目描述

给出两个数组, ，我们可以对进行任意次以下操作：
将修改为或者.
是否可以将变为?

解题思路

由于变化的大小都是，则可以看作
那么我们可以将和都对取余,但是可能出现,我们可以将小于等于的数做一个变形,变为或者,最后再排序,检查是否相同.

参考代码

void solve() {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
       std::cin >> a[i];
       a[i] %= k;
       if (a[i] <= k / 2) {
          a[i] = k - a[i];
       }
    }
    for (int i = 0; i < n; i++) {
       std::cin >> b[i];
       b[i] %= k;
       if (b[i] <= k / 2) {
          b[i] = k - b[i];
       }
    }
    std::sort(a.begin(), a.end());
    std::sort(b.begin(), b.end());
    std::cout << (a == b ? "YES" : "NO") << std::endl;
}

D Arboris Contractio

题目描述

选择一条简单路径，然后将路径上除了以外的所有点都直接连接到上（即变成s的直连儿子）。即每次操作实际上是将一条路径“收缩”到起点，使得路径上的所有点都直接连到。这样，操作后从s到路径上任意一点的距离都变为（除了自己），而原来路径上的分支结构被改变。
最小化直径，并求达到最小直径所需的最少操作次数。

解题思路

最终树是双星结构（有两个中心相邻）。
我们需要选择一条边（u,v）作为中心边，使得u和v覆盖的叶子数最多（即u的叶子邻居数+v的叶子邻居数，注意如果u是叶子则包括自己，v同理）。
那么，最少操作次数就是总叶子数减去最大覆盖叶子数（即leaf - ans）。
因为已经覆盖的叶子不需要操作（它们已经直接连接到中心），而未覆盖的叶子每个都需要一次操作来提升（将它直接连接到某个中心）。

参考代码

void solve() {
    int n;
    std::cin >> n;
    std::vector g(n + 1, std::vector<int>());
    for (int i = 0, u, v; i < n - 1; i++) {
       std::cin >> u >> v;
       g[u].push_back(v);
       g[v].push_back(u);
    }
    int leaf = 0, ans = 0;
    for (int i = 1; i <= n; i++) {
       if (g[i].size() == 1) leaf++;
       int res = (g[i].size() == 1);
       for (auto v : g[i]) {
          res += (g[v].size() == 1);
       }
       ans = std::max(res, ans);
    }
    std::cout << leaf - ans << std::endl;
}