Codeforces Round 1042 (Div. 3) • santisify Site

A Lever ↗#

题目描述#

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

选择一个下标 $i$ ,若 $A_{i}>B_{i}$ ，则 $A_{i}=A_{i}-1$ . 如果不存在这样的 $i$ ，则忽略此步骤.

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

解题思路#

可以发现两个操作都是操作 $A$ 数组， $B$ 数组没有变化过。既然这样，我们就可以只考虑 $A_{i}$ 和 $B_{i}$ 的大小关系. 不懂的，可以看样例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;  
}

cpp

B Alternating Series ↗#

题目描述#

构造一个数组 $A$ ,使得数组 $A(|A_{1}|,|A_{2}|,\cdots,|A_{n}|)$ 的字典序最下,并且长度大于等于 $2$ 的子数组的和为正数。

解题思路#

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

例如 $6$ 的构造： $\{-1,3,-1,3,-1，3\}$ ，当取第 $5$ ， $6$ 位的长度为 $2$ 的子数组 $\{-1,3\}$ 就会发现，最后一位可以为 $2$ ，依次可以推理出：当长度为偶数，那么最后一位应该为 $2$ 。

参考代码#

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 << ' ';  
       }    
    }
}

cpp

C Make it Equal ↗#

题目描述#

给出两个数组 $S$ , $T$ ，我们可以对 $S$ 进行任意次以下操作：将 $S_{i}$ 修改为 $S_{i}+k$ 或者 $|S_{i}-k|$ . 是否可以将 $S$ 变为 $T$ ?

解题思路#

由于变化的大小都是 $k$ ，则可以看作 $S_{i} + t * k = T_{j} (t \in Z)$ 那么我们可以将 $S$ 和 $T$ 都对 $k$ 取余,但是可能出现 $S_{i} = k - T_{i}$ ,我们可以将小于等于 $\frac{k}{2}$ 的数做一个变形,变为 $k-S_{i}$ 或者 $k-T_{i}$ ,最后再排序,检查是否相同.

参考代码#

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;  
}

cpp

D Arboris Contractio ↗#

题目描述#

选择一条简单路径 $s\to t$ ，然后将路径上除了 $s$ 以外的所有点都直接连接到 $s$ 上（即变成s的直连儿子）。即每次操作实际上是将一条路径“收缩”到起点 $s$ ，使得路径上的所有点都直接连到 $s$ 。这样，操作后从s到路径上任意一点的距离都变为 $1$ （除了 $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;  
}

cpp