Contestant. Rank 1948. Rating +8.

A. Serval and Mocha’s Array

题意

给定一个数组 ，将其重新排序，满足对于所有前缀，如前 个数，满足它们的 。

思路

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

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

所以，我们只需找出一对数，满足 即可。

时间复杂度：

对应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

题意

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

思路

考虑到回文串的对称性，我们只需修改 内的数即可。

下面是一种模拟思路：

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

否则，一定是有解的。

时间复杂度：

对应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

题意

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

思路

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

具体地说，对于一个数字，若它自始至终未被修改，那么任意两个数组组合，都会留下它，那么它的贡献即为 。

若它被修改了，那么在它未出现的时候，它将毫无贡献。因此，我们需要减去这些无贡献的数组组合，也就是 $C{m - cnt + 1}^2C{m + 1}^2 - C_{m - cnt + 1}^2$。

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

时间复杂度：

对应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';
    }
}

我蠢了