Blog - Floating Ocean
0%

Codeforces - Round 830 Div 2

发表于 更新于
本文字数： 4.7k 阅读时长 ≈ 8 分钟
阅读次数： Valine：

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

数据结构题挺少见，这种简短的题更少见（（