Preface

题解是 $A\sim 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]$ 可以发现，从中间点出发向两端交替“横跳”能最大限度利用空间，确保差值 $|p_{i+1}-p_i|$ 恰好满足 $1,2,\dots,n-1$。

• 奇数情况 ($n$ 为奇数)： 从 $M = (n+1)/2$ 出发，按“先加后减”震荡，序列为 $[M,M+1,M-1,M+2,\dots,n,1]$。
• 偶数情况 ($n$ 为偶数)： 从 $M = n/2+1$ 出发，按“先减后加”震荡，序列为 $[M,M-1,M+1,M-2,\dots,n,1]$。

构造过程仅需单次遍历，时间与空间复杂度均为 $O(n)$

A.cc

#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 使其成立，那我们考虑 $\underbrace{000\cdots000} _n$ 这样的情况，这样中段可以放置 $\left \lfloor n/3 \right \rfloor$ 个 1，因为对于每一个 1 他可以占领周围的位置，即 $00{\color{red}010}00$。

对于边界的 0 我们可以在边界添加 10 来保证合理性以便切分。

B.cc

// WIP

C. Restricted Sorting

题意是给定一个长为 $n$ 的数组 $a$，设 $b$ 为 $a$ 的从小到大排序的数列，如果存在 $k$ 使得存在一个 $1\leqslant i<j\leqslant n$ 满足 $|a_i-a_j|\leqslant k$，那么我们就可以交换 $a_i,a_j$。求最小能将将 $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=[{\color{red}1},1,{\color{red}4},{\color{red}5},1,{\color{red}4},1,{\color{red}9},{\color{red}1},{\color{red}9},8,{\color{red}1},{\color{red}0}]$
• $b=[0,1,1,1,1,1,1,4,4,5,8,9,9]$

部分为必须要替换的内容，也就是说我们要讲这些部分通过 $k$ 全部链接成一个整体即可。这样它们就可以灵活地变动。

维护两个数为 $min\_val$ 与 $max\_val$，那么对于每一个必须移动的数 $a_i$，为了让它能动弹，它必须至少能连接到 $min\_val$ 或 $max\_val$ 中的一个。因此，对于每个满足 $a_i \neq b_i$ 的下标 $i$，我们要计算它与两个极端值的最大距离：

$$d_i = \max(|a_i - min\_val|, |max\_val - a_i|)$$

举个例子，我们将所有红色部分整理为一个数组

$$a_{sub}=[1,4,5,4,9,1,9,1,0]$$

1. 让 $[1,4]$ 可以随意变动，那么 $k_2=3$，此时 $min\_val=1$，$max\_val=4$；
2. 让 $[1,4,5]$ 可以随意变动，那么 $k_3=\max\{k_2,\min\{5-4,5-1\}\}=3$，此时 $min\_val=1$，$max\_val=5$；
3. 让 $[1,4,5,4]$ 可以随意变动，那么 $k_4=\max\{k_3,\min\{5-4,4-1\}\}=3$，此时 $min\_val=1$，$max\_val=5$；
4. 让 $[1,4,5,4,9]$ 可以随意变动，那么 $k_5=\max\{k_4,\min\{9-5,9-1\}\}=4$，此时 $min\_val=1$，$max\_val=9$；
5. ......

通过这个方案可以找到 $k$ 最小可能值。

C.cc

// WIP

D. Shortest Statement Ever

题意很简短：给你两个非负整数 $x$ , $y$。求两个非负整数 $p$ 和 $q$ 使 $p\;\&\;q=0$ 和 $|x-p|+|y-q|$ 最小。

本体有很多很多做法，这里先讲官方题解：

官方题解

官方题解需要一些注意力，并且没有给证明:

WIP

贡献者

Timothy Starman

版权所有

版权归属：Timothy Starman

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)

编辑此页

上一页CFR 1076 div3 题解

下一页牛客寒假训练营-1