A、Greatest Convex
非常的简单。根据样例直接猜是输出 \(n - 1\).
上一个 \(Python\) 代码。
T = int(input())
while T > 0:
T -= 1
n = int(input())
print(n - 1)
B、Quick Sort
题目大意是每次选 \(k\) 个，然后把他们排序后放到末尾。
那不妨这么看。每次我们先把已经有序的部分提取出来，即 \(1, 2, 3 ...\) 一直到最后一位。对于这些已经有序的部分，我们是不用进行任何操作的。而对于他们周围以及中间的无序部分，我们全部都要提取出来并排序。（无序部分的排序规则很简单，每次选未被排序的前 k 小并将其排到末尾。）那么，如果碰到不是 \(k\) 的倍数怎么办？可以发现，将已经有序的最后几位扒出来跟多余部分再排就好了。 所以答案就是无序部分的个数 \(num / k\)(向上取整)。
#include <bits/stdc++.h>
using namespace std;
#define N 1000100
int n, k;
int a[N];
int main(){
int T; cin >> T;
while(T--){
cin >> n >> k;
for(int i = 1; i <= n; i++)
cin >> a[i];
int now = 1, tot = 0;
for(int i = 1; i <= n; i++){
if(a[i] == now){
now++;
tot++;
}
}
int sum = n - tot;
int ans = sum / k + (sum % k != 0);
cout << ans << endl;
}
return 0;
}
C、Elemental Decompress
首先特判几个显然的特殊情况：
- 任何数字出现个数不超过 3
- 最大值必须出现（不能为 \(0\) 次）
- 最小值(即 \(1\)) 出现次数不超过 \(1\) 次。
然后考虑普通数字的出现 \(0, 1, 2\)次 情况。
对于出现一次的数字，有个显然的方法，就是两个数组都放同样的数字（自己）。可以发现这样放比起其中一个放更小的值是绝对不亏的。（不可能放更大的值对吧。）
对于出现两次的数字，我们记录下来他们出现的两个位置。然后两个数组分别设为对应值即可。
可以发现，如果有出现两次的数字，那么两个数组对应的另外一个位置就会出现空缺。那么我们肯定要在对应的那个空缺填上一个更小值。可以发现，这时候我们剩下的能填的值只有出现 \(0\) 次的数字。最优填法肯定就是每次填一个最大的小于他的数。所以把所有剩下的数字放进 \(set\) 里面，用lower_bound 查询一下是否等于begin()，如果不是，就 it--, 取得对应值。如果是，就说明没有更小值，输出 \(NO\) 即可。
#include <bits/stdc++.h>
using namespace std;
#define N 200010
int n, k;
int a[N];
int vis[N]; // 每个数字的出现次数
int ans[N][2];
vector <int> G[N]; // 每个数字出现的位置
int main(){
// freopen("hh.txt", "r", stdin);
int T; cin >> T;
while(T--){
for(int i = 1; i <= n; i++){
ans[i][0] = ans[i][1] = 0;
G[i].clear();
}
int maxn = 0;
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i], maxn = max(maxn, a[i]);
for(int i = 1; i <= maxn; i++)
vis[i] = 0;
for(int i = 1; i <= n; i++){
G[a[i]].push_back(i);
}
set <int> s;
bool flag = 1;
for(int i = 1; i <= maxn; i++){
sort(G[i].begin(), G[i].end());
if(G[i].size() == 0) s.insert(i);
else if(G[i].size() == 1) ans[G[i][0]][0] = ans[G[i][0]][1] = i;
else if(G[i].size() == 2){
ans[G[i][0]][0] = ans[G[i][1]][1] = i;
}
else if(G[i].size() >= 3){
flag = 0;
break;
}
}
if(G[n].size() == 0) flag = 0;
if(G[1].size() > 1) flag = 0;
for(int i = 1; i <= n; i++){
if(ans[i][0] && !ans[i][1]){
int pos = G[ans[i][0]][1]; // 二号位的 pos
set<int>::iterator it = s.lower_bound(ans[i][0]);
if(it == s.begin()){
flag = 0;
break;
}
else{
it--;
ans[i][1] = ans[pos][0] = *it;
s.erase(it);
}
}
}
if(!flag){
puts("NO");
}
else{
puts("YES");
for(int i = 1; i <= n; i++)
printf("%d ", ans[i][0]);
cout << endl;
for(int i = 1; i <= n; i++)
printf("%d ", ans[i][1]);
cout << endl;
}
}
return 0;
}
D、Lucky Permutation
发现题目要求只剩下一个逆序对。
可以想到，这个剩下的逆序对肯定是原序列（称有序序列为原序列）中相邻的两个数。那么不妨先把他们排成总体有序的数列，这样子就和题目要求的情况只有一步之遥了。
考虑如何求出排成总体有序数列的最快步数。
偷懒，上 \(Tutorial\) 截图先。
这句话是什么意思呢，就是将序列按照下标的下标，下标的下标的下标。。。。。建成一张图。可以发现这张图就是一个个环。注意，这里是通过下标的访问建图的。而下标也就对应着这个数字本应前往的地方。因此，如果我们要进行排序，对于一个环上所有的数字，只需要在环内进行交换即可。那么，对于一个有 \(k\) 个元素的环，我们不妨以其中一个点为基准，将他沿任意固定方向一直移动（交换），那么我们只需要移动 \(k - 1\) 次便能使环上元素全部到达其应到的位置。
接下来考虑如何剩下一个逆序对。其实这个过程就是在对原序列排成整体有序时，某一对相邻元素不交换。因此，如果有任意一对相邻元素在同一个环内，我们就可以将两个元素反向移动，只需要 \(k - 2\) 步便能达到对方的应到位置，形成逆序对，故此时总答案减一。
如果没有任何一组，那么我们只能在完全排有序后将任意一组互换，故此时总答案加一。
上一个 C# 代码。
using System;
namespace CodeForces
{
class NewBaseType
{
public static void Main(string[] args)
{
var T = Convert.ToInt32(Console.ReadLine());
while(T > 0){
T--;
var n = Convert.ToInt32(Console.ReadLine());
int[] a = new int[n + 10];
string[] tmp = Console.ReadLine().Split();
for(int i = 0; i < tmp.Count(); i++){
a[i] = Convert.ToInt32(tmp[i]) - 1;
}
int[] comp = new int[n + 10];
int id = 1, ans = 0;
for(int i = 0; i < n; i++){
if(comp[i] != 0) continue;
int v = i;
while(comp[v] == 0){
comp[v] = id;
v = a[v];
ans++;
}
id++;
ans--;
}
bool flag = false;
for(int i = 0; i < n - 1; i++){
if(comp[i] == comp[i + 1]){
flag = true;
break;
}
}
if(flag == true){
Console.WriteLine(ans - 1);
}
else Console.WriteLine(ans + 1);
}
}
}
}