Contestant. Rank 309. Rating +66.

A. Secret Sport

题意

对于两个人之间的博弈，定义一局中先赢了 \(X\) 次的玩家在该局中获胜，赢了 \(Y\) 局的玩家获得最后的胜利。

其中，若能确定最后的赢家，那么将立即停止博弈。

现在，在 \(X, Y\) 未知的条件下，给定一次游戏中，每局获胜的玩家，输出最后的赢家。

思路

既然能确定最后的赢家，那么后面就不会有新的一局了。

换句话说，最后一局决定了当前的赢家。

显然，决定的条件只有一个：最后一个玩家赢了 \(X\) 次。那么，显然最后一局的赢家就是最后的赢家了。

因而，读入字符串后，输出最后一个字符即可。

时间复杂度：\(O(1)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pdd pair<double, double>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    cout << s[n - 1] << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

逆天题面，逆天网络

B. Two Out of Three

题意

给定一个长为 \(n\) 的数组 \(a\)，构造一个由 \(1, 2, 3\) 组成的长为 \(n\) 的数组 \(b\)，使得下面的 \(3\) 个条件恰好有 \(2\) 个满足：

存在 \(a_i = a_j, b_i = 1, b_j = 2\)；
存在 \(a_i = a_j, b_i = 1, b_j = 3\)；
存在 \(a_i = a_j, b_i = 2, b_j = 3\)

思路

显然，我们可以先按值分组，然后将个数为 \(1\) 的所有组都填上任意的数字。

接着，随便挑一组，\(1, 2\) 交替填入。

最后，剩下的组，\(2, 3\) 交替填入。

上面的构造一定是最优的，而显然，当个数 \(\geq 2\) 的组的数量 \(<2\) 时，我们就无法满足任意两个条件了。

时间复杂度：\(O(n \log n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pdd pair<double, double>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    map<int, int> cnt;
    int t = 0;
    for(int i=1;i<=n;i++) {
        cin >> a[i];
        cnt[a[i]] ++;
        if(cnt[a[i]] == 2) t ++;
    }
    if(t < 2) {
        cout << -1 << '\n';
        return;
    }
    int p = 0;
    for(int i=1;i<=n;i++){
        if(cnt[a[i]] == 1) cout << "1 ";
        else if(p == 0 || a[i] == p){
            p = a[i];
            if(cnt[a[i]] % 2 == 1) cout << "1 ";
            else cout << "2 ";
        }else{
            if(cnt[a[i]] % 2 == 1) cout << "2 ";
            else cout << "3 ";
        }
        cnt[a[i]] ++;
    }
    cout << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

简单构造

C. Anonymous Informant

题意

对于一个未知的数组 \(a\)，定义一次操作为：

选定 \(x\)，满足 \(a_x = x\)；
将数组 \(a\) 循环左移 \(x\) 格

现在，给定一个数组 \(b\)，判断其是否由数组 \(a\) 经过 \(k\) 次操作后得到。

思路

循环左移 \(x\) 格后，\(a_x\) 会来到数组的最后一位。

那么显然，我们只要按照这个性质，反向推回去即可，如果出现循环，或者\(a_x > n\)，那么即可判定答案，否则只需判断是否可以循环 \(k\) 次。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pdd pair<double, double>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    for(int i=1;i<=n;i++) cin >> a[i];
    vector<bool> st(n + 1);
    int now = n;
    while(m --){
        if(a[now] > n){
            cout << "NO\n";
            return;
        }
        if(st[now]){
            cout << "YES\n";
            return;
        }
        st[now] = true;
        now = (now - a[now] + n - 1) % n + 1;
    }
    cout << "YES\n";
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

逆向思维（

D. Neutral Tonality

题意

给定两个数组 \(a, b\)，将 \(b\) 按任意顺序排列后，逐一任意插入 \(a\) 中。

输出一种构造，使最后的数组的 最长递增子序列 (LIS) 长度最小。

思路

显然，我们不可以升序插入，那么我们考虑降序插入。

可以发现，按这样插入的话，一定不会让 LIS 变大 \(2\) 或者更多。

那么我们考虑如何让 LIS 不变：

对于当前的一个 LIS，它的每一个元素都可以有多个选择，从而我们可以得到很多长度相等的 LIS。

那么，我们只需降序插入时，让这些插入的元素成为某一个元素 \(a_i\) 的多个合法选择，或者大于等于 LIS 的下一个元素 \(a_j\) 即可。

这就简单了。我们在枚举 \(a_i\) 时，如果上次降序插到了第 \(x\) 大的数，那么我们只需从第 \(x+1\) 大的数开始，降序插入所有 \(\geq a_i\) 的数即可。

显然，如果出现了多余的数字，我们降序放到末尾即可，一定不会影响 LIS 的大小。

时间复杂度：\(O(n + m + m \log m)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pdd pair<double, double>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1), b(m + 1);
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=m;i++) cin >> b[i];
    sort(all(b));
    int ind = m;
    for(int i=1;i<=n;i++){
        while(ind >= 1 && b[ind] >= a[i]) cout << b[ind --] << ' ';
        cout << a[i] << ' ';
    }
    while(ind >= 1) cout << b[ind --] << ' ';
    cout << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

感觉思维力也没有 \(B\) 大