A. Greatest Convex
题意：
给定一个 k ，求一个小于 k 的数 x ，使得 x! + (x - 1)! 是 k 的倍数
分析：
题目已经给出提示： y! = y ⋅ (y − 1)!，输出 n - 1
cout << n - 1 << endl;
B. Quick Sort
题意：
给定 n 个数，要求每次选择其中的 k 个数进行排序，并按排序后的顺序放在数列最后，问最少的操作次数使 n 个数单调递增
分析：
由于最后是有序的，每步不管怎么排，应该按照选较大的 k 个数放到最后，对与顺序正确但位置不正确的几个数，如 ...1...2...3...，只需要选择中间逆序的数进行排排序，即只需要从 1 开始的递增序列的长度不需要选出来排序;
所以先计算不需要重排的数最多有多少，然后剩下的数 ÷ k 上取整即可
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define mst(x, y) memset(x, y, sizeof x)
#define endl '\n'
#define INF LONG_LONG_MAX
#define x first
#define y second
#define int long long
#define Lson u << 1, l, mid
#define Rson u << 1 | 1, mid + 1, r
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 200010, MOD = 1e9 + 7;
const double EPS = 1e-6;
typedef pair<int, int> PII;
typedef unordered_map<int, int> Ump;
int T;
int n, k;
int a[N], pos[N];
int idx;
void solve()
{
idx = 0;
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
pos[a[i]] = i;
}
int res = 1;
for (int i = 2; i <= n; i++)
{
if (pos[i] > pos[i - 1])
res++;
else
break;
}
cout << ceil(1.0 * (n - res) / k) << endl;
}
signed main()
{
FAST;
cin >> T;
while (T--)
solve();
return 0;
}
C. Elemental Decompress
题意：
\[构造，构造排列 p1 ，p2, 使得 a[i] = max(p1[i], p2[i]) \]分析：
首先看出：每个数出现次数不能超过 2 (1 出现次数不超过 1)，
- 对于出现 2 次的数，p1 放一次， p2 放一次
- 对于出现 1 次的数，都放在 p1
这样安排后，对 p1 剩下的数进行放置，每次 p1[i] 安排一个没安排的且小于 a[i] 的最大的数，对 p2 也按照这样的方式计算，在过程中，若出现找不到这个数，那么说明出现矛盾，”NO“
举例：
下面只需要安排空格上的数字即可
知乎上更简洁的代码
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define mst(x, y) memset(x, y, sizeof x)
#define endl '\n'
#define INF LONG_LONG_MAX
#define x first
#define y second
#define int long long
#define Lson u << 1, l, mid
#define Rson u << 1 | 1, mid + 1, r
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 200010, MOD = 1e9 + 7;
const double EPS = 1e-6;
typedef pair<int, int> PII;
typedef unordered_map<int, int> Ump;
int T;
int n;
int a[N];
int p1[N], p2[N];
bool f[N], st1[N], st2[N];
map<int, int> mp;
void init()
{
mst(p1, 0), mst(p2, 0);
mp.clear();
mst(f, false);
mst(st1, false), mst(st2, false);
}
void solve()
{
init();
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
mp[a[i]]++;
if (mp[a[i]] == 2)
{
f[a[i]] = true;
}
}
for (int i = 1; i <= n; i++)
{
if (mp[a[i]] > 2 || mp[1] > 1)
{
cout << "NO" << endl;
return;
}
}
for (int i = 1; i <= n; i++)
{
if (mp[a[i]] == 1 && !f[a[i]])
{
p1[i] = p2[i] = a[i];
st1[a[i]] = true, st2[a[i]] = true;
}
else if (mp[a[i]] == 1 && f[a[i]])
{
p2[i] = a[i], st2[a[i]] = true;
}
else
{
p1[i] = a[i];
st1[a[i]] = true;
mp[a[i]]--;
}
}
vector<int> v1, v2;
for (int i = 1; i <= n; i++)
{
if (!st1[i])
v1.push_back(i);
if (!st2[i])
v2.push_back(i);
}
for (int i = 1; i <= n; i++)
{
if (!p1[i])
{
auto pos = lower_bound(v1.begin(), v1.end(), a[i]);
if (pos == v1.begin())
{
cout << "NO" << endl;
return;
}
pos--;
p1[i] = *pos;
v1.erase(pos);
}
}
for (int i = 1; i <= n; i++)
{
if (!p2[i])
{
auto pos = lower_bound(v2.begin(), v2.end(), a[i]);
if (pos == v2.begin())
{
cout << "NO" << endl;
return;
}
pos--;
p2[i] = *pos;
v2.erase(pos);
}
}
cout << "YES" << endl;
for (int i = 1; i <= n; i++)
cout << p1[i] << " ";
cout << endl;
for (int i = 1; i <= n; i++)
cout << p2[i] << " ";
cout << endl;
}
signed main()
{
FAST;
cin >> T;
while (T--)
solve();
return 0;
}