Codeforces Round 908 (Div. 2)
一个教训：做题的时候一定要自己模拟一遍所有样例，这样思路出来的很快！！！
C. Anonymous Informant
Example
input
Copy
6
5 3
4 3 3 2 3
3 100
7 2 1
5 5
6 1 1 1 1
1 1000000000
1
8 48
9 10 11 12 13 14 15 8
2 1
1 42
output
Copy
Yes Yes No Yes Yes No
大意：给一个数组a，看能不能有一个数组b能经过k次操作转换成a。有k次操作机会，每次操作选一个b[i] = i的数（i从1开始），然后整个数组向左移i位
思路：主要是要找到一个规律，经过一次操作后，选中的b[i]会到数组的最后一个元素
例如：1，4，3，5，6.。选i = 3的a[3] = 3，左移后变成，5，6，1，4，3
经过若干次操作后就变成了a。因此可以从a逆推b。
当然了，如果选中的数 a[i] > n（n是数组的大小），那么就跟操作的原则相矛盾，无法转换成a，输出-1.
还有一个要点，如果k太大，这样一遍遍模拟一定会超时，所以我们会发现，这是有周期T的，如果能模拟过了一个周期T，那么b一定可以转换成a。在能转换成a的情况下，模拟到一定次数就会选中先前选过的数，因此要用到vis数组
总结：
1.找规律
2.逆推
2.周期T，vis数组
#include<cstdio>
#include<set>
#include<list>
#include<queue>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<string.h>
#include <stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<sstream>
#include<stack>
#include <utility>
#include<map>
#include <vector>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f
//2147483647
#define int long long
//#include <bits/stdc++.h>
typedef long long ll;
#include<iostream>
using namespace std;
const int N = 2e5 + 10;
//long long MAX(long long a, long long b) { return a < b ? b : a; }
int a[N];
int vis[N];
signed main() {
int t; cin >> t;
while (t--) {
memset(vis, 0, sizeof vis);
int n, k; cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
int pa = n;
int f = 1;
while (k--) {
//如果pa即将访问之前访问过的结点
//那么一个周期已经结束，要开始下一个周期
//如果在第一个周期没有问题，下一个周期也不会有问题
//因为下一个周期是重复上一个周期的步骤
int temp = a[pa];
if (temp > n) {
f = 0;
break;
}
if (vis[pa] == 1) break;
vis[pa] = 1;
pa = (pa - temp + n) % n;
}
if (f) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}D. Neutral Tonality
Example
input
Copy
7
2 1
6 4
5
5 5
1 7 2 4 5
5 4 1 2 7
1 9
7
1 2 3 4 5 6 7 8 9
3 2
1 3 5
2 4
10 5
1 9 2 3 8 1 4 7 2 9
7 8 5 4 6
2 1
2 2
1
6 1
1 1 1 1 1 1
777
output
Copy
6 5 4 1 1 7 7 2 2 4 4 5 5 9 8 7 7 6 5 4 3 2 1 1 3 5 2 4 1 9 2 3 8 8 1 4 4 7 7 2 9 6 5 2 2 1 777 1 1 1 1 1 1
大意：给出数组a和数组b，在a数组中插入b的所有元素，问怎么插能使最后的数组的最长上升子序列最小
分析：双指针
1.首先要明白一点，答案的下界是a本身的LIS（即b不会增加LIS的长度）。
2.为了让数组b不贡献长度，要对b排降序后再插入
3.接下来考虑，怎么插入才能不增加LIS长度。结论是，如果ai<bj，那么将bj插到ai前面就不会贡献长度，如图（红色是b，黑色是a）
4.如果a已经遍历完最后一个，b却还没插入完，就把b剩下的（bn-i,bn-i+1,bn-i+2......bn）全部放到an后面。如果bn-i > an，那么b就会贡献一个长度，否则就不贡献长度。由此还可以得出一个小结论，LIS是a(LIS)或者a(LIS)+1
#include<cstdio>
#include<set>
#include<list>
#include<queue>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<string.h>
#include <stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<sstream>
#include<stack>
#include <utility>
#include<map>
#include <vector>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f
//2147483647
#define int long long
//#include <bits/stdc++.h>
typedef long long ll;
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
//long long MAX(long long a, long long b) { return a < b ? b : a; }
int a[N];
int b[N];
bool cmp(int e1, int e2) {
return e1 > e2;
}
signed main() {
int t; cin >> t;
while (t--) {
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= m; i++) cin >> b[i];
sort(b + 1, b + 1 + m, cmp);
vector<int> ans;
int pb = 1;
for (int i = 1; i <= n; i++) {
if (pb <= m && b[pb] >= a[i]) {
ans.push_back(b[pb]);
pb++;
i -= 1;
}
else ans.push_back(a[i]);
}
for (int i = pb; i <= m; i++) ans.push_back(b[i]);
//cout << "答案：";
cout << ans[0];
for (int i = 1; i < ans.size(); i++) {
cout << " " << ans[i];
}
cout << endl;
}
return 0;
}