0%

Codeforces - Round 853 Div 2

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

我蠢了