外观
Skip to content 查看源代码：
查看源代码：
CF2131.md
---
title: CF2131
createTime: 2025/8/18
categories:
- IT
tags:
- OI
---
## [CF2131A. Lever](https://codeforces.com/contest/2131/problem/A)
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn=20;
int a[maxn];
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t--) {
int n, ans=1;
cin >> n;
for (int i=1; i<=n; i++) {
cin >> a[i];
}
for (int i=1; i<=n; i++) {
int b;
cin >> b;
ans += max(a[i]-b, 0);
}
cout << ans << '\n';
}
return 0;
}
```
## [CF2131B. Alternating Series](https://codeforces.com/contest/2131/problem/B)
安排字典序最小就是奔着目光短浅去的。
于是负值贪心地取 $-1$，但是正值由于抽子序列的最坏情况是 $-1 \ a \ -1$，所以非尾部的 $a$ 必须为 $3$。
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i=1; i<=n; i++) {
cout << ((i&1)? -1: 3-(i==n)) << ' ';
}
cout << '\n';
}
return 0;
}
```
## [CF2131C. Make it Equal](https://codeforces.com/contest/2131/problem/C)
一次操作改变的数的空间是有限的，
且这个数可以到达所在空间中的所有点。
于是考虑把空间内的所有数视为等价，
然后比较两个多重集即可。
最后，这个空间是什么？
是 $(\pm x) \bmod k$。
因此，一个数所在的空间序号可以表示成
$\operatorname{space}(x) = \min(x \bmod k, (-x) \bmod k)$
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, k;
map<int, int> S, T;
inline int space(int a) {
// printf("space(%d) = %d\n", a, min(a%k, k-a%k));
return min(a%k, k-a%k);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t--) {
S.clear();
T.clear();
// 多测不清空，赛后两行泪
cin >> n >> k;
for (int i=1; i<=n; i++) {
int x;
cin >> x;
S[space(x)]++;
}
bool ans = true;
for (int i=1; i<=n; i++) {
int x;
cin >> x;
int sx = space(x);
T[sx]++;
if (T[sx] > S[sx]) {
ans = false;
// 要输入完，不能 break
}
}
cout << (ans? "YES\n" : "NO\n");
}
return 0;
}
```
## [CF2131D. Arboris Contractio](https://codeforces.com/contest/2131/problem/D)
一棵树直径最小的形态是菊花图。
设它的花蕊为 $r$，
设原树的非花叶节点数 $c$ 为不与花蕊直接相连且不为花蕊的叶节点数。
:::note 引理
将一张图收缩为花蕊为 $r$ 的菊花图至少需要 $c$ 次操作。
---
**证明** 对于一次操作，非花叶节点的个数最多减少 $1$。
- 对于仅经过一个非花叶节点的路径
显然。
- 对于经过两个非花叶节点的路径
一个非花叶节点会连到另一个非花叶节点上，仍为非花叶节点。
:::
:::note 引理
将一张图收缩为花蕊为 $r$ 的菊花图只需 $c$ 次操作。
---
**证明** 对于每一个非花叶节点，做一次 r 到这个节点的操作即可。
由于每个节点至少是一个叶节点自身或祖先，它总能被做一次操作，然后直接连到 $r$ 上。
:::
因此，$\mathrm{ans} = \#\mathrm{leaf} - \displaystyle\max_r\bigl( \#\{(\mathrm{leaf}, r) \in E\} + [r \in \mathrm{leaf}] \bigr)$。
如何统计？每个叶节点向自己以及它所连的节点打一个标记。
时间复杂度 $O(n)$。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+100;
vector<int> G[maxn];
int leaves;
int sub[maxn];
inline void add_edge(int u, int v) {
G[u].push_back(v);
G[v].push_back(u);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
leaves = 0;
for (int i=1; i<=n; i++) {
sub[i] = 0;
G[i].clear();
}
for (int i=1; i<=n-1; i++) {
int u, v;
cin >> u >> v;
add_edge(u, v);
}
for (int i=1; i<=n; i++) {
if (G[i].size() == 1) {
leaves++;
sub[G[i][0]]++;
sub[i]++;
}
}
int msub=0;
for (int i=1; i<=n; i++) {
msub = max(msub, sub[i]);
}
cout << leaves - msub << '\n';
}
return 0;
}
```
## [CF2131E. Adjacent XOR](https://codeforces.com/contest/2131/problem/E)
由于每个数最多操作一次，可以知道：
若能够变换，每个数异或的不是 $a_{i+1}$（下一个数操作前）就是 $b_{i+1}$（下一个数操作后，或者下一个数不操作）
（也可以不异或）
直接模拟即可。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+100;
int a[maxn], b[maxn];
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
a[n+1] = b[n+1] = 0; // 多测___，_____
for (int i=1; i<=n; i++) {
cin >> a[i];
}
for (int i=1; i<=n; i++) {
cin >> b[i];
}
bool ans = true;
for (int i=1; i<=n; i++) {
ans &= a[i] == b[i]
|| ((a[i]^a[i+1])==b[i])
|| ((a[i]^b[i+1])==b[i]);
}
cout << (ans? "YES\n" : "NO\n");
}
return 0;
}
```
## [CF2131F. Unjust Binary Life](https://codeforces.com/contest/2131/problem/F)
注意到
$$
\begin{matrix}
A=x \oplus y & B=x \oplus w \\
C=z \oplus y & D=z \oplus w
\end{matrix}
$$
满足 $A \oplus B \oplus C \oplus D = 0$，如果其中三个为 $0$，那么剩下一个也一定为 $0$。
因此如果存在一条全 $0$ 的路径，它的最小矩形包围盒一定全为 $0$。
因此 $f(x, y)$ 即为将任意的 $i \le x, j \le y$ 的 $a_i \oplus b_j$ 变为 $0$ 的最小操作数。
等价地，此时 $a_1, \dots, a_x, b_1, \dots, b_y$ 都相同。此时最少的操作次数为其中 $0/1$ 最少的一个的个数。
根据 $\min \longleftrightarrow |\cdot|$ 互化公式
$$
\min\{x,y\} = \dfrac{x+y}{2} - \left| \dfrac{x-y}{2} \right|
$$
有
$$
\begin{aligned}
& \sum_{x=1}^{n} \sum_{y=1}^{n} f(x, y)\\
=&\sum_{x=1}^{n} \sum_{y=1}^{n} \min\left\{ \left(\sum_{i=1}^{x} a_i\right) + \left(\sum_{i=1}^{y} b_i\right), x+y - \left( \left(\sum_{i=1}^{x} a_i\right) + \left(\sum_{i=1}^{y} b_i\right) \right) \right\} \\
\xlongequal[\text{前缀和}]{\text{预处理}}& \sum_{x=1}^{n} \sum_{y=1}^{n} \min\left\{ A_x+B_y, x+y-A_x-B_y \right\} \\
\xlongequal{\text{最小值-绝对值互化}}& \sum_{x=1}^{n} \sum_{y=1}^{n} \dfrac{1}{2}\left[ x+y - |2A_x-x + 2B_y-y| \right] \\
\xlongequal{\text{分离变量, 换元}}& \sum_{x=1}^{n} \sum_{y=1}^{n} \dfrac{1}{2}\left[ x+y - |C_x - D_y| \right] \\
\xlongequal{\text{提取}}& \frac{1}{2} \left[\sum_{x=1}^{n} \sum_{y=1}^{n} x + \sum_{x=1}^{n} \sum_{y=1}^{n} y - \sum_{x=1}^{n} \sum_{y=1}^{n} |C_x - D_y| \right]\\
=& \dfrac{n^2 (n+1)}{2} - \frac{1}{2} \sum_{x=1}^{n} \sum_{y=1}^{n} |C_x-D_y|\\
\xlongequal[\text{对 } C_x,D_y \text{ 排序}]{\text{预处理}}& \dfrac{n^2 (n+1)}{2} - \frac{1}{2} \sum_{x=1}^{n} \left(\sum_{y=1}^{y_0(x)} C'_x-D'_y\right) + \left(\sum_{y=y_0(x)+1}^{n} D'_y-C'_x\right) \\
&\text{其中 } y_0(x) = \max \bigl( \{0\} \cup \{y \mid C'_x \ge D'_y\} \bigr)\\
=& \dfrac{n^2 (n+1)}{2} - \frac{1}{2} \sum_{x=1}^{n} C'_x \bigl(2y_0(x)-n\bigr) - \left(\sum_{y=1}^{y_0} D'_y\right) + \left(\sum_{y=y_0+1}^{n} D'_y\right) \\
\xlongequal[\text{前缀和}]{\text{预处理}} &\dfrac{n^2 (n+1)}{2} - \frac{1}{2} \sum_{x=1}^{n} C'_x \bigl(2y_0(x)-n\bigr) + E_n - 2E_{y_0(x)}
\end{aligned}
$$
其中 $y_0(x)$ 可以用二分查找或双指针算出，时间复杂度瓶颈在排序，$O(n \log n)$。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+100;
int A[maxn], B[maxn], C[maxn], D[maxn], E[maxn];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
A[0] = B[0] = E[0] = 0;
for (int i=1; i<=n; i++) {
char a;
cin >> a;
A[i] = A[i-1] + a - '0';
C[i] = 2 * A[i] - i;
}
for (int i=1; i<=n; i++) {
char b;
cin >> b;
B[i] = B[i-1] + b - '0';
D[i] = i - 2 * B[i];
}
sort(C+1, C+n+1);
sort(D+1, D+n+1);
for (int i=1; i<=n; i++) {
E[i] = E[i-1] + D[i];
}
int x, y=0, sum=0;
for (x=1; x<=n; x++) {
while (y<n && C[x]>=D[y+1]) {
y++;
}
sum += C[x] * (2*y - n) + E[n] - 2*E[y];
}
cout << (n*n*(n+1) - sum) / 2 << '\n';
}
return 0;
}
```