0%

Codeforces - Round 830 Div 2

Practice.

A. Bestie

题意

给定一个数组 ,定义操作为将 改为 ,代价为 ,输出最小的操作代价总和,使所有数的最大公约数为

思路

首先,这里有一个结论:相邻数字的最大公约数一定为

所以,最多只需两次操作,即可满足题意。

所以,我们只需考虑 对应的元素是否需要进行操作,以及对应的代价总和的最小值。

时间复杂度:

对应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], b[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;
        int g = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            g = gcd(g, a[i]);
        }
        if (g == 1) cout << 0 << '\n';
        else if (gcd(g, n) == 1) cout << 1 << '\n';
        else if (gcd(g, n - 1) == 1) cout << 2 << '\n';
        else cout << 3 << '\n';
    }
}

这结论一开始还真没想到…

B. Ugu

题意

给定一个二进制字符串,定义操作为选定一个整数 ,将 内的数全都取反,输出让整个字符串变为不递减的操作数的最小值。

思路

考虑下面的模拟:

也就是说,我们只考虑拐点,统计拐点个数即可。

当然,需要根据第一个数的情况来扣去

时间复杂度:

对应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], b[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;
        string s;
        cin >> s;
        char pre = -1;
        int dif = 0;
        for(int i=0;i<n;i++){
            if(pre == -1) pre = s[i];
            else{
                if(pre != s[i]) dif ++;
                pre = s[i];
            }
        }
        dif ++;
        cout << max(0ll, dif - (s[0] == '1' ? 1 : 2)) << '\n';
    }
}

就这么模拟嘞

C1. Sheikh (Easy version)

题意

给定一个数组 ,定义子区间 的代价 为总和和所有数异或值的差。对于 个询问,输出询问的 内的子区间的代价最大值,以及对应的最短区间。

思路

首先,对于一段区间,我们加上一个值 ,那么总和会改变 ,而异或值改变量不会超过 ,也就是说,

因而,代价最大值一定是 ,我们只需找出最短区间即可。

因为本题 难度的数据量低,所以我们不妨直接二分长度,然后枚举所有可行解即可。

使用前缀和和前缀异或优化复杂度。

时间复杂度:

对应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], sum[N], xo[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while(t --) {
        int n, q;
        cin >> n >> q;
        for(int i=1;i<=n;i++) {
            cin >> a[i];
            sum[i] = sum[i - 1] + a[i];
            xo[i] = xo[i - 1] ^ a[i];
        }
        while(q --){
            int l, r;
            cin >> l >> r;
            int ans = (sum[r] - sum[l - 1]) - (xo[r] ^ xo[l - 1]);
            int L = 1, R = r - l + 1, mid;
            int ansL = l, ansR = r;
            while(L < R){
                mid = (L + R) >> 1;
                bool f = false;
                for(int i=l;i+mid-1<=r;i++){
                    if((sum[i+mid-1] - sum[i - 1]) - (xo[i+mid-1] ^ xo[i - 1]) == ans) {
                        if(mid < ansR - ansL + 1){
                            ansL = i, ansR = i + mid - 1;
                            f = true;
                        }
                    }
                }
                if(f) R = mid;
                else L = mid + 1;
            }
            cout << ansL << ' ' << ansR << '\n';
        }
    }
}

想不到结论就寄

C2. Sheikh (Hard Version)

待补充

D. Balance (Easy version)

题意

给定一个初始情况下只有一个元素 的序列,对于下述两种询问,进行对应的操作:

  1. :将 加入序列,满足 原先不在序列里;

  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, mod = 998244353;

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int q;
    cin >> q;
    map<int, bool> mp;
    map<int, int> to;
    while(q --){
        char op;
        int num;
        cin >> op >> num;
        mp[0] = true;
        if(op == '+') {
            mp[num] = true;
        }else {
            while(mp[to[num]]) to[num] += num;
            cout << to[num] << '\n';
        }
    }
}

数据结构题挺少见

D2. Balance (Hard version)

题意

给定一个初始情况下只有一个元素 的序列,对于下述两种询问,进行对应的操作:

  1. :将 加入序列,满足 原先不在序列里;

  2. :将 从序列中删除,满足 原先在序列里;

  3. :输出第一个能被 整除且不在序列里的数。

思路

我们可以继续之前的优化,但这里需要考虑删除数以后,该数的因数 是否已经将 其 下一个未被标记的数 标为大于等于 这个数 的值了。

也就是说,删除以后,我们需要更新这些因数。

暴力枚举因数是不可行的,但考虑到这些因数都是后来加进来的,所以我们可以在上一题输出优化部分,加上 下一个未被标记的数的原数字是什么(也就是它的因子)。然后,在加减操作的时候,我们不妨遍历我们之前记录下来的因子,标记一下这个因子对应原数字有没有被删去。

最后,我们只需按之前的操作,找出该数字下一个未被标记的数,然后判断这个数的倍数有没有已被删去的数,有的话两个数取最小值即可。

时间复杂度:有点小复杂

对应AC代码

#include <bits/stdc++.h>

using namespace std;

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

const int N = 2e5 + 10, inf = LONG_LONG_MAX, mod = 998244353;

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int q;
    cin >> q;
    map<int, bool> mp;
    map<int, int> to;
    map<int, set<int>> vis, del;
    mp[0] = true;
    while(q --){
        char op;
        int num;
        cin >> op >> num;
        if(op == '+') {
            for(auto &i : vis[num]) del[i].erase(num);
            mp[num] = true;
        }else if(op == '-'){
            for(auto &i : vis[num]) del[i].insert(num);
            mp[num] = false;
        }else{
            while(mp[to[num]]) vis[to[num]].insert(num), to[num] += num;
            cout << min(to[num], del[num].empty() ? inf : *del[num].begin()) << '\n';
        }
    }
}

数据结构题挺少见,这种简短的题更少见((