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;
}