Contestant~. Rank 313. Rating +53.

这场的 \(E\) 难度感觉很有争议，感觉放 \(C\) 都不过分（个人看法

A. green_gold_dog, array and permutation

题意

给定一个序列 \(a\)，构造一个排列 \(b\)，使所有 \(a_i - b_i\) 中不同值的个数最大，并输出方案。

思路

显然地，因为我们可以减到负数，那么我们用大数减小数的方式，一定可以构造出尽可能多的 \(a_i - b_i\)。

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

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#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 = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n;
    cin >> n;
    vector<pii> a(n);
    for(int i=0;i<n;i++){
        cin >> a[i].fs;
        a[i].sc = i;
    }
    sort(all(a));
    vector<int> ans(n);
    for(int i=0;i<n;i++) ans[a[i].sc] = n - i;
    for(auto e : ans) cout << e << ' ';
    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();
}

题目差点没看懂（x

B. XOR Palindromes

题意

给定一个长为 \(n\) 的二进制字符串，对于 \(k \in [0, n]\)，输出是否可以构造出长为 \(n\) 且包含 \(k\) 个 \(1\) 的二进制字符串，满足和原串进行按位异或后，得到的结果是一个回文串。

以二进制的方式输出。

思路

首先，我们先判断有多少个位置是不满足回文的，对于每一对 \(<0, 1>\)，对应的我们构造的字符串上也应满足不是回文。

那么，\(k\) 至少得大于等于非回文对的个数，否则直接输出 \(0\)。

那么，在上述条件下，其他位置都放 \(0\)，就是对应的 \(1\) 最少的方案。

至于剩下的位置，我们直接一对一对放 \(1\) 即可。

因为会出现 \(n\) 为奇数的情况，所以中间的数是任意的，需要特判一下。

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

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#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 = 1e6 + 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;
    s = " " + s;
    int dif = 0;
    for(int i=1;i<=n/2;i++){
        if(s[i] != s[n - i + 1]) dif ++;
    }
    for(int i=0;i<=n;i++){
        if(i < dif){
            cout << 0;
            continue;
        }
        int lf = i - dif;
        if(n % 2 == 1){
            if(lf % 2 == 0 && lf <= (n / 2 - dif) * 2){
                cout << 1;
            }else if(lf % 2 == 1 && lf - 1 <= (n / 2 - dif) * 2){
                cout << 1;
            }else cout << 0;
        }else{
            if(lf % 2 == 0 && lf <= (n / 2 - dif) * 2){
                cout << 1;
            }else cout << 0;
        }
    }
    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. Salyg1n and the MEX Game

题意

这是一道交互题。

这是一道和测评机的博弈题。（？

在本题中，给定一个序列 \(s\)，你 \(A\) 和测评机 \(B\) 需要进行下面的博弈：

  1. 每轮，\(A\) 先手；

  2. \(A\) 选择一个数 \(x\)，并将其放入 \(s\)，需要满足 \(s\) 中本来不包含 \(x\)；

  3. \(B\) 从 \(s\) 中选择一个数 \(y\) 删除，需要满足 \(y\) 严格小于 上一次 \(A\) 放入的数

  4. 当 \(B\) 无法操作，或者两者的总操作数等于 \(2n + 1\) 时，游戏结束；

  5. 最后，\(MEX(s)\) 就是游戏的结果；

  6. \(A\) 希望最大化结果，\(B\) 希望最小化结果

在你足够聪明的条件下，和测评机博弈，使最后的结果一定是一个定值。

思路

如果我要最大化结果，我自然会填上空缺。

此时，如果测评机选了比较小的数，我一定可以重新填上去，并缩小 \(B\) 的范围，因而最后 \(B\) 一定会无法操作，而且他的所有操作都是无效的。

可以发现总操作数最大是奇数，也就是说最后一个操作的人一定是我，那么不存在 \(B\) 删掉了数的情况。

以上，本题题面中的结果为我填入 \(MEX(s)\) 后的 \(MEX(s')\)，为一个定值。

交互方式就是先填入 \(MEX(s)\)，然后测评机删一个我塞回去一个。

时间复杂度：\(O(测评机的无聊程度)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#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 = 1e6 + 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);
    for(int i=1;i<=n;i++) cin >> a[i];
    sort(all(a));
    int mn = 0;
    for(int i=1;i<=n;i++){
        if(a[i] == mn) mn ++;
    }
    cout << mn << '\n';
    cout.flush();
    int now;
    cin >> now;
    while(now != -1){
        cout << now << '\n';
        cout.flush();
        cin >> now;
    }
}

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

测评机直接删 \(0\) 不好吗（x

D. Cyclic Operations

题意

给定一个序列 \(a\)，最初序列全都是 \(0\)，定义一次操作为选择一个左端点 \(l\)，对于 \(i \in [1, k]\)，执行 \(a_{l_i} := l_{(i \bmod k) + 1}\)。

现在，给定可能的若干次操作后的序列 \(b\)，输出其是否合法。

思路

显然，一次操作对应着一个环，如果我们以 \(i \rightarrow b_i\) 的方式建图，最后的图是一种形为太阳的图的集合。

可以发现，因为存在覆盖，那么对于图上的所有链，我们都可以按顺序取 \(k\) 个节点，然后把最后一个节点指向第一个节点，即可构成一个环。

所以我们无需考虑链，去掉即可。

我们利用拓扑排序，标记非环点，然后枚举所有环，判断这些环长度是否都是 \(k\) 即可。

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

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#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 = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1), in(n + 1);
    for(int i=1;i<=n;i++) {
        cin >> a[i];
        in[a[i]] ++;
    }
    if(k == 1){
        for(int i=1;i<=n;i++){
            if(a[i] != i){
                cout << "NO\n";
                return;
            }
        }
        cout << "YES\n";
        return;
    }
    vector<bool> st(n + 1);
    queue<int> q;
    for(int i = 1;i <= n;i++){
        if(!in[i]){
            st[i] = true;
            q.push(i);
        }
    }
    while(!q.empty()){
        int u = q.front();
        q.pop();
        if(--in[a[u]] == 0){
            st[a[u]] = true;
            q.push(a[u]);
        }
    }
    auto dfs = [&](auto dfs, int x, int step) -> bool{
        if(st[x]){
            return step == k;
        }
        st[x] = true;
        return dfs(dfs, a[x], step + 1);
    };
    for(int i=1;i<=n;i++){
        if(st[i]) continue;
        if(!dfs(dfs, i, 0)){
            cout << "NO\n";
            return;
        }
    }
    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();
}

抽象的，具象的，好做的

E1. Salyg1n and Array (simple version)

详见 \(E2\)，区别是本题交互的次数是 \(100\)。

E2. Salyg1n and Array (hard version)

题意

这又是一道交互题。

对于一个未知的序列，定义一次询问为选定一个长为给定 \(k\) 的区间，测评机会给出这个区间内所有元素的异或和，并将这个区间翻转。

在不超过 \(57\) 次询问下，输出整个序列的异或和。

保证 \(1 \leq k \leq n \leq k^2 \leq 2500\)。n和k都是偶数！

思路

首先，我们先询问前面相邻的长度为 \(k\) 的区间，即询问满足条件的 \(1 + mk\)。

接着，如果 \(n \bmod k = 0\)，那么我们无需操作，最后答案就是上面询问的异或和。

否则，我们还需询问两次。

我们看下面的序列：

1 2 3 4 5 6 7 8 9 10

如果 \(k = 4\)，那么最后 \(9, 10\) 我们是没有算上的。

我们考虑将剩下的数分成两半，然后先询问以前面一半的数为结尾的区间，然后再询问以序列右端点为结尾的区间。

如上我们即可得到答案。

我们可以模拟一下：

  1. 第一种操作完成后：

    4 3 2 1 | 8 7 6 5 | 9 10

  2. 询问以前面一半的数为结尾的区间，得到 "7 6 5 9":

    4 3 2 1 8 | 9 5 6 7 | 10

  3. 询问以序列右端点为结尾的区间，得到 "5 6 7 10"

可以发现，我们抵消后得到了 "9 10"。

上面的翻转操作会将我们真正需要的翻转到前面，留下后面不需要的，而分成两半后，我们需要的前一半在操作后会翻转到前面，然后我们恰好又将询问区间向后移动了一半，刚好让前面一半的数在区间外，从而恰好可以抵消。

至于 \(100\) 次的方案，我们可以从以第一个剩余的数为结尾的区间开始询问，下一次询问是上一次询问的区间向右移动一格，可以发现也是类似的抵消方式。

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

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#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 = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n, k;
    cin >> n >> k;
    auto fetch = [&](){
        int x;
        cin >> x;
        return x;
    };
    int ans = 0;
    for(int i=1;i+k-1<=n;i+=k) {
        cout << "? " << i << '\n';
        cout.flush();
        ans ^= fetch();
    }
    if(n % k != 0){
        cout << "? " << n - (n % k) / 2 - k + 1 << '\n';
        cout.flush();
        ans ^= fetch();
        cout << "? " << n - k + 1 << '\n';
        cout.flush();
        ans ^= fetch();
    }
    cout << "! " << ans << '\n';
    cout.flush();
}

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

也是差点没看到那个偶数的条件，看到了就是个签到了（怎么不放在题面而是放在输入约束里啊啊啊啊啊