Contestant. Rank 1936. Rating +9.

A. Serval and Mocha's Array

题意

给定一个数组 \(a\)，将其重新排序，满足对于所有前缀，如前 \(i\) 个数，满足它们的 \(gcd \leq i\)。

思路

首先，最优的方法当然是互质，只要把互质的两个数放到第一个，那么后面的 \(gcd\) 全都是 \(1\) 了。

其次，前两个数可以有公约数 \(2\)，这是毋庸置疑的。但是，若我们继续下去，前 \(3\) 个数可以有公约数 \(3\)，...，前 \(6\) 个数可以有公约数 \(6\)。停，不对劲：既然有公约数 \(2,3\)，那么一定能被 \(6\) 整除，那么前两个数的 \(gcd\) 一定至少是 \(6\) 了，产生了矛盾。

所以，我们只需找出一对数，满足 \(gcd \leq 2\) 即可。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10, inf = 0x3f3f3f3f;

int a[N];

int gcd(int x, int y) {
    while (y != 0) {
        int tmp = x;
        x = y;
        y = tmp % y;
    }
    return x;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        for(int i=0;i<n;i++) cin >> a[i];
        bool f = false;
        for(int i=0;i<n;i++)
            for(int j=i;j<n;j++){
                if(gcd(a[i], a[j]) <= 2) {
                    f = true;
                    break;
                }
            }
        cout << (f ? "YES\n" : "NO\n");
    }
}

为什么赛后反而思路这么清晰了（（

B. Serval and Inversion Magic

题意

给定一个二进制字符串，任选一个区间，将区间内的所有数取反，输出是否可以将整个字符串变为回文字符串。

思路

考虑到回文串的对称性，我们只需修改 \([0, \frac{n}{2}]\) 内的数即可。

下面是一种模拟思路：

我们不妨从外向里遍历，比较 \(i\) 和 \(n - i - 1\) 对应的数，若出现了不同的数，记录当前下标开始需要取反，然后一直找到结束，或者出现相同的数。出现相同数后，我们标记一下已经进行过取反操作，当我们再次遇到不同数的时候，考虑到只能选一个区间，所以直接返回 \(NO\)。

否则，一定是有解的。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10, inf = 0x3f3f3f3f;

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        string a;
        cin >> a;
        bool f = true, have = false, now = false;
        for(int i=0;i<n/2;i++){
            if(a[i] == a[n - i - 1]){
                if(now){
                    now = false;
                    have = true;
                }
            }else{
                if(have){
                    f = false;
                    break;
                }
                now = true;
            }
        }
        cout << (f ? "YES\n" : "NO\n");
    }
}

我的评价是：比A题简单

C. Serval and Toxel's Arrays

题意

给定一个无重复元素的数组 \(a\)，对于 \(q\) 个操作给定的 \(p_i, v_i\)，将 \(a_{p_i}\) 改为 \(v_i\)。每次操作后，将会得到一个新数组，新数组满足无重复元素。每次操作的对象为上次操作后的数组。对于所有数组（原数组 + 所有新数组），输出所有任意两个数组拼接后不同数字的个数的和。

思路

显然，我们不可能去暴力计算，而相反地，我们可以将问题拆分为所有单个数字的贡献和。

具体地说，对于一个数字，若它自始至终未被修改，那么任意两个数组组合，都会留下它，那么它的贡献即为 \(C_{m + 1}^2\)。

若它被修改了，那么在它未出现的时候，它将毫无贡献。因此，我们需要减去这些无贡献的数组组合，也就是 \(C_{m - cnt + 1}^2\)。因而，得到该条件下的总贡献：\(C_{m + 1}^2 - C_{m - cnt + 1}^2\)。

当然，我们还需算出一个数的出现次数 \(cnt\)，考虑到无重复，所以我们只需模拟即可。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 4e5 + 10, inf = 0x3f3f3f3f;

int cnt[N];
pii a[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while(t --){
        int n, m;
        cin >> n >> m;
        for(int i=1;i<=n+m;i++) cnt[i] = 0;
        for(int i=1;i<=n;i++) {
            cin >> a[i].first;
            a[i].second = 0;
        }
        for(int i=1;i<=m;i++){
            int p, v;
            cin >> p >> v;
            cnt[a[p].first] += i - a[p].second;
            a[p] = {v, i};
        }
        for(int i=1;i<=n;i++) cnt[a[i].first] += m + 1 - a[i].second;
        int ans = 0;
        for(int i=1;i<=n+m;i++){
            if(cnt[i] == 0) continue;
            if(cnt[i] > m) ans += m * (m + 1) / 2;
            else ans += (m * (m + 1) - (m - cnt[i]) * (m - cnt[i] + 1)) / 2;
        }
        cout << ans << '\n';
    }
}

我蠢了