CFR 1077 div1-2 题解
约 1183 字大约 4 分钟
2026-01-30
Preface
题解是 A∼D,本人战绩如下:
| # | Who | = | A 500 | B 1000 | C 1500 | D 2000 | E 2500 | F 2750 | G 2750 |
|---|---|---|---|---|---|---|---|---|---|
| 1498 | 🇨🇳 TimothyStarman | 3335 | 482 00:14 | 321 02:41 | 1284 00:54 | 1268 02:08 |
A. Divisible Permutation
本题的核心在于利用“震荡思维”在有限范围内构造出递增的差值序列。观察 n=5,p=[3,4,2,5,1] 和 n=6,p=[4,3,5,2,6,1] 可以发现,从中间点出发向两端交替“横跳”能最大限度利用空间,确保差值 ∣pi+1−pi∣ 恰好满足 1,2,…,n−1。
- 奇数情况 (n 为奇数): 从 M=(n+1)/2 出发,按“先加后减”震荡,序列为 [M,M+1,M−1,M+2,…,n,1]。
- 偶数情况 (n 为偶数): 从 M=n/2+1 出发,按“先减后加”震荡,序列为 [M,M−1,M+1,M−2,…,n,1]。
构造过程仅需单次遍历,时间与空间复杂度均为 O(n)
#include <bits/stdc++.h>
using namespace std;
void sol()
{
int n;
cin >> n;
vector<int> vi(n + 1);
int cnt = 1;
if (n % 2 == 0)
{
for (int i = n; i >= 1; i -= 2)
{
vi[i] = cnt;
cnt++;
}
for (int i = 1; i < n + 1; i += 2)
{
vi[i] = cnt;
cnt++;
}
}
else
{
for (int i = n; i >= 1; i -= 2)
{
vi[i] = cnt;
cnt++;
}
for (int i = 2; i < n + 1; i += 2)
{
vi[i] = cnt;
cnt++;
}
}
for (int i = 1; i < n + 1; i++)
{
cout << vi[i] << " ";
}
}
int main()
{
int t;
cin >> t;
for (int i = 0; i < t; i++)
{
sol();
cout << "\n";
}
return 0;
}B. Seats
题意是给定一个 01 串,两个 1 之间它们不能相邻,每次操作选择一个 0 变为 1 求无法再进行操作时 1 的最小个数。
思路是贪心地将数组填充为 1001,即每 2 个 0 就要至少安排一个 1 会保证总人数最少,考虑 10001000001 这个例子,我们按照 1 将其分段,那么 000 中间必须要插入一个 1 使其成立,00000中间也必须要至少插入一个 1 使其成立,那我们考虑 n000⋯000 这样的情况,这样中段可以放置 ⌊n/3⌋ 个 1,因为对于每一个 1 他可以占领周围的位置,即 0001000。
对于边界的 0 我们可以在边界添加 10 来保证合理性以便切分。
// WIPC. Restricted Sorting
题意是给定一个长为 n 的数组 a,设 b 为 a 的从小到大排序的数列,如果存在 k 使得存在一个 1⩽i<j⩽n 满足 ∣ai−aj∣⩽k,那么我们就可以交换 ai,aj。求最小能将将 a 转化为 b 的 k。
首先举个例子,a=[1,1,4,5,1,4,1,9,1,9,8,1,0],那么可得 b=[0,1,1,1,1,1,1,4,4,5,8,9,9] 接下来进行对比:
- a=[1,1,4,5,1,4,1,9,1,9,8,1,0]
- b=[0,1,1,1,1,1,1,4,4,5,8,9,9]
维护两个数为 min_val 与 max_val,那么对于每一个必须移动的数 ai,为了让它能动弹,它必须至少能连接到 min_val 或 max_val 中的一个。因此,对于每个满足 ai=bi 的下标 i,我们要计算它与两个极端值的最大距离:
di=max(∣ai−min_val∣,∣max_val−ai∣)
举个例子,我们将所有红色部分整理为一个数组
asub=[1,4,5,4,9,1,9,1,0]
- 让 [1,4] 可以随意变动,那么 k2=3,此时 min_val=1,max_val=4;
- 让 [1,4,5] 可以随意变动,那么 k3=max{k2,min{5−4,5−1}}=3,此时 min_val=1,max_val=5;
- 让 [1,4,5,4] 可以随意变动,那么 k4=max{k3,min{5−4,4−1}}=3,此时 min_val=1,max_val=5;
- 让 [1,4,5,4,9] 可以随意变动,那么 k5=max{k4,min{9−5,9−1}}=4,此时 min_val=1,max_val=9;
- ......
通过这个方案可以找到 k 最小可能值。
// WIPD. Shortest Statement Ever
题意很简短:给你两个非负整数 x , y。求两个非负整数 p 和 q 使 p&q=0 和 ∣x−p∣+∣y−q∣ 最小。
本体有很多很多做法,这里先讲官方题解:
官方题解
官方题解需要一些注意力,并且没有给证明:
WIP
