负责人

• 035966_L3

注意

请严格按照提交方式进行操作。

题目描述

主题干

小 F 发明了一个基于排列的算法——快速排列变换（Fast Permutation Transform，FPT）。这一算法可以将一个 $1 \sim n$ 的排列 $p$ 变换为任意一个字典序更大的排列 $q$。

FPT 的实现如下：对排列 $p$ 进行若干次操作，每次操作选定 $p$ 中连续的若干个数（即选定一个区间）并调用一次 next_permutation 函数。

next_permutation 对长度为 $k$ 的排列 $\{r_k\}$ 的实现如下：

• 找到满足 $r_i<r_{i+1}$ 的最大正整数 $i$；
• 找到满足 $r_i<r_j$ 的最大正整数 $j$；
• 交换 $r_i$ 和 $r_j$；
• 翻转 $r_{i+1} \sim r_k$；
• 如果正整数 $i$ 不存在，那么会发生运行错误；
• 否则，该次调用的时间开销为 $O(k-i+1)$。

可以证明，FPT 可以在不发生运行错误的前提下将一个 $1 \sim n$ 的排列 $p$ 变换为任意一个字典序更大的排列 $q$。

第一小题

假设 FPT 每次必须对整个排列调用 next_permutation 函数，请分析 FPT 的最坏时间复杂度，并给出证明。

第二小题

假设 FPT 每次可以选定任意一个区间，并且总能以最优策略（即最小化总时间开销，寻找最优策略时的时间开销不计）调用 next_permutation 函数，请分析 FPT 的最坏时间复杂度，并给出证明。

提交方式

## 第一小题（$50$ 分）

### 第一部分（$10$ 分）

此时 FPT 的最坏时间复杂度是 $O(n)$。

### 第二部分（$30$ 分）

根据小 F 第三公理（充分性部分），此时 FPT 的最坏时间复杂度显然是 $O(n)$。

### 第三部分（$10$ 分）

以下是一组可能的数据：

- $p=\{1,2,\ldots,n\}$。
- $q=\{n,n-1,\ldots,1\}$。

## 第二小题（$50$ 分）

### 第一部分（$10$ 分）

此时 FPT 的最坏时间复杂度是 $O(n)$。

### 第二部分（$30$ 分）

根据小 F 第三公理（必要性部分），此时 FPT 的最坏时间复杂度显然是 $O(n)$。

### 第三部分（$10$ 分）

以下是一组可能的数据：

- $p=\{1,2,\ldots,n\}$。
- $q=\{n,n-1,\ldots,1\}$。

1. 对于每个小题，你需要分三部分进行证明（以上是一份证明示例，它显然是错误的）：
   • 第一部分： 指出 FPT 的最坏时间复杂度。
   • 第二部分： 构造一个调用 next_permutation 函数的策略，使得 FPT 的总时间开销无论对于哪两个合法的 $1 \sim n$ 的排列 $p,q$，总是不高于你所认为给出的时间复杂度；
   • 第三部分： 构造一组数据，使得 FPT 的总时间开销无论采用哪种调用 next_permutation 函数的策略，都会退化为你所认为的时间复杂度。
2. 你需要在下面的代码中填入你的 Sleeping Cup UID，并用 C++ 提交。
3. 本题的部分分设计已经在上面的证明示例中给出。
4. 本题将在赛后将进行人工批改，并更新 AC 记录，因此赛时无法 AC。若你提交了多个证明，则以最后一个为准。请严格按照上述要求进行提交，否则后果自负。

#include <bits/stdc++.h>
using namespace std;
const int UID = /*Enter your UID here*/;
int main()
{
    freopen("proof.in", "r", stdin);
    freopen("proof.out", "w", stdout);
    cout << UID;
    return 0;
}

5. 请不要恶意填写 UID，违者将被处以警告或封禁惩罚。
6. 赛后提交方式如下，管理员将不定期进行批改。

#include <bits/stdc++.h>
using namespace std;
const int UID = (-1) * /*Enter your UID here*/;
int main()
{
    freopen("proof.in", "r", stdin);
    freopen("proof.out", "w", stdout);
    cout << UID;
    return 0;
}
/*
## 第一小题（$50$ 分）

### 第一部分（$10$ 分）

此时 FPT 的最坏时间复杂度是 $O(n)$。

### 第二部分（$30$ 分）

根据小 F 第三公理（充分性部分），此时 FPT 的最坏时间复杂度显然是 $O(n)$。

### 第三部分（$10$ 分）

以下是一组可能的数据：

- $p=\{1,2,\ldots,n\}$。
- $q=\{n,n-1,\ldots,1\}$。

## 第二小题（$50$ 分）

### 第一部分（$10$ 分）

此时 FPT 的最坏时间复杂度是 $O(n)$。

### 第二部分（$30$ 分）

根据小 F 第三公理（必要性部分），此时 FPT 的最坏时间复杂度显然是 $O(n)$。

### 第三部分（$10$ 分）

以下是一组可能的数据：

- $p=\{1,2,\ldots,n\}$。
- $q=\{n,n-1,\ldots,1\}$。
*/

官方题解

link