---
url: /algo/qjb643xe/index.md
---
## Preface

题解是 $A\sim D$，本人战绩如下：

::: table align="center" hl-cells="success:(2,4)(2,5)(2,6)(2,7);"
| #    | Who                                                          | =        |     A500     |    B1000     |     C1500     |     D2000     | E2500 | F2750 | G2750 |
| :--- | :----------------------------------------------------------- | :------- | :----------------: | :----------------: | :-----------------: | :-----------------: | :---------: | :---------: | :---------: |
| 1498 | :cn: [TimothyStarman](https://codeforces.com/profile/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)$

```cpp title="A.cc" :collapsed-lines
#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` 来保证合理性以便切分。

```cpp title="B.cc" :collapsed-lines
// 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$ 最小可能值。

```cpp title="C.cc" :collapsed-lines
// WIP
```

## D. Shortest Statement Ever

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

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

### 官方题解

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

WIP