Codeforces Round 908 (Div. 2)
C. Anonymous Informant
思路
可以发现,每次操作后a数组的变化: \(a_1 a_2 a_3 a_4 ... a_x ... a_n\) \(->\) \(a_1\)\(_+\)\(_x\) \(a_2\)\(_+\)\(_x\) \(a_3\)\(_+\)\(_x\)...\(a_x\),\(a_x\)会变到最后一位。我们只需要撤销k次操作就知道能不能把数组还原,但是k的范围有1e9,直接枚举会超时。我们注意到:如果能成功撤销\(n\)次,则会进入一个循环,所以\(k = min(n, k)\)。还有,但数组最后一位数大于\(n\)时,这时无法撤销操作
ac代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 inf = 8e18;
typedef pair<int, int> pii;
const int N = 3e5 + 10;
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (auto &i : a) cin >> i;
int last = n - 1;//last表示一次撤销后数组最后一个元素再原数组里的下标
for (int i = 0; i < min(k, n); i++) {
if (a[last] > n) {
cout << "No\n";
return;
}
last += n - a[last];
if (last >= n) last -= n;
}
cout << "Yes\n";
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1;
cin >> t;
while (t --) solve();
return 0;
}
D. Neutral Tonality
题目大意
给你一个数组\(a\)和一个数组\(b\),你可以把b数组不考虑顺序的插入数组\(a\)中,让你输出一个按照上述方法构造出的最长上升子序列最小的数组
思路
对于输出的数组\(c\),一定有\(LIS(c) >= LIS(a)\),\(LIS(c) <= LIS(a) + 1\),我们只需要将\(b\)数组中小于\(a\)数组的最小值的数插到\(a\)数组后面,其他的插到\(a\)数组前面就行
ac代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 inf = 8e18;
typedef pair<int, int> pii;
const int N = 3e5 + 10;
void solve() {
int n, m;
cin >> n >> m;
std::vector<int> a(n), b(m), c(n + m);
for (auto &i : a) cin >> i;
for (auto &i : b) cin >> i;
sort(b.begin(), b.end(), greater<int>());
merge(b.begin(), b.end(), a.begin(), a.end(), c.begin(), greater<int>());
for (auto i : c) cout << i << ' ';
cout << endl;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1;
cin >> t;
while (t --) solve();
return 0;
}