Blog - Floating Ocean
0%

Codeforces - Round 828 Div 3

发表于
本文字数： 5k 阅读时长 ≈ 9 分钟
阅读次数： Valine：

Practice.

A. Number Replacement

题意

给定一个序列，一个字母可以映射到任意一个数字，但要求一个字母只能映射到一个数字，一个数字可以映射到多个字母。输出是否合法。

思路

简单，我们用哈希即可。用 即可解决本题。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

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

const int N = 1e6 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin >> a[i];
    string s;
    cin >> s;
    map<int, char> mp;
    bool f = true;
    for(int i=0;i<n;i++){
        if(mp[a[i]] > 0 && mp[a[i]] != s[i]) f = false;
        mp[a[i]] = s[i];
    }
    cout << (f ? "YES\n" : "NO\n");
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    //init();
    int t;
    cin >> t;
    while(t --) solve();
}

水.jpg

B. Even-Odd Increments

题意

给定一个序列，含有奇数和偶数，定义操作如下：

  1. 表示将 添加到所有偶数上；

  2. 表示将 添加到所有奇数上。

在每次操作后，输出总和。前面的操作会影响后面的值。

思路

显然，我们只需统计当前序列有多少偶数即可。

设偶数的个数为 ，那么第一个操作即为将 加上 ，第二个操作即为将 加上 。

显然，我们不需要在每次操作后遍历找偶数个数，而是考虑下面的规律：

  1. 偶数加奇数为奇数；

  2. 奇数加奇数为偶数。

因而，若出现将奇数加在奇数上的情况，那么 ，若出现将奇数加在偶数上的情况，那么 。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

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

const int N = 1e6 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n); //注意一下偶数和奇数的相加即可
    int even = 0, sum = 0;
    for(int i=0;i<n;i++){
        cin >> a[i];
        sum += a[i];
        if(a[i] % 2 == 0) even ++;
    }
    while(q --){
        int t, v;
        cin >> t >> v;
        if(t % 2 == 0){ //加到偶数上
            sum += even * v;
            cout << sum << '\n';
            if(v % 2 == 1) even = 0; //偶加奇
        }else{ //加到奇数上
            sum += (n - even) * v;
            cout << sum << '\n';
            if(v % 2 == 1) even = n; //奇加奇
        }
    }
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    //init();
    int t;
    cin >> t;
    while(t --) solve();
}

偏模拟的思维题

C. Traffic Light

题意

定义三种交通信号灯：，只有位于 的时间下才可过马路。交通信号灯的切换具有周期性，因而给定一个周期的信号灯切换情况 ，如 ，那么在执行五秒后，将会重新执行一次，构成 。给定当前的信号灯种类 ，输出遇到下一个 所间隔的最长时间。

思路

如上，我们只需遍历所有 ，找出其和下一个 的距离即可。

至于距离，数据范围貌似可以允许我们暴力往后搜，但后缀数组会出手。

我们维护后缀数组， 表示 及以后第一个出现的 的位置。

那么，查询的复杂度即为 。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

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

const int N = 1e6 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;

void solve() {
    int n;
    char c;
    cin >> n >> c;
    string s;
    cin >> s;
    s = " " + s + s;
    n *= 2;
    vector<int> suf(n + 1);
    suf[n] = -1;
    for(int i=n - 1;i>=1;i--){
        if(s[i] == 'g') suf[i] = i;
        else suf[i] = suf[i + 1];
    }
    int mx = 0;
    for(int i=0;i<n;i++){
        if(s[i] == c) mx = max(mx, suf[i] - i);
    }
    cout << mx << '\n';
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    //init();
    int t;
    cin >> t;
    while(t --) solve();
}

可能就真的能暴力（（

D. Divisibility by 2^n

题意

给定一个长度为 的序列，定义一次操作为选取一个 并将其改为 。输出最少的操作数，使最后的序列的乘积为 的倍数。

思路

首先，乘上奇数绝对没什么用，所以我们只需考虑偶数。

观察偶数的递推性以及二进制下的规律，我们不难发现所有的偶数都是一个 乘上一个奇数得到的。

上述没必要乘上偶数，毕竟那就是 的事情了，为何要考虑重复呢。

因而，我们自然希望我们能在一次操作中乘上尽可能多的 ，也就是让 尽可能大。

这个 是很容易求的，我们只需循环乘二直到不超过 的最大值即可。

那么，我们不妨去枚举 的奇数倍，然后在超过 后将 递减，这样即可满足条件。

在加之前，我们判断一下当前能除多少个 ，和 比较即可。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

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

const int N = 1e6 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;

void solve() {
    int n;
    cin >> n;
    int cnt = 0;
    for(int i=0;i<n;i++){
        int cur;
        cin >> cur;
        while(cur % 2 == 0){
            cur /= 2;
            cnt ++;
        }
    }
    int mx = 1, cur = 2;
    while(true){
        if(cur * 2 > n) break;
        mx ++;
        cur *= 2;
    }
    int ans = 0;
    for(int i=mx;i>=1;i--){
        for(int j=1;pow(2, i)*j<=n;j+=2){ //奇数倍
            if(cnt >= n) break;
            cnt += i;
            ans ++;
        }
        if(cnt >= n) break;
    }
    cout << (cnt >= n ? ans : -1) << '\n';
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    //init();
    int t;
    cin >> t;
    while(t --) solve();
}

奇怪的清晰思路增加了

E1. Divisible Numbers (easy version)

详见E2，区别是本题的数据范围小

E2. Divisible Numbers (hard version)

题意

给定 个整数 ，找出一对 ，满足 可以被 整除。

思路

首先，我们不难发现，，其中 为常数，那么，我们可以很简单的用 的复杂度算出 。

那么我们来考虑 。显然，，所以 就是 的倍数，或者说，是 的因数的倍数。

那么，我们只需枚举所有的因数，然后，我们也可以用 的方法算出 ，和求 的方法类似。

但是，枚举 的因数是不现实的，因为 太大了。但是，既然我们可以将这个数分解为 ，那么它的所有因数就是 的所有因数和 的所有因数配对相乘。

因而， 可以减到 的复杂度，足以。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

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

const int N = 1e6 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;

vector<int> fact(int x) {
    vector<int> facts;
    int sq = (int) sqrt(x);
    for (int i = 1; i < sqrt(x); i++) {
        if (x % i == 0) facts.emplace_back(i), facts.emplace_back(x / i);
    }
    if (sq * sq == x) facts.emplace_back(sq);
    return facts;
}

void solve() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    vector<int> factA = fact(a), factB = fact(b);
    bool f = false;
    for (int i: factA) {
        for (int j: factB) {
            int bx = i * j, by = a * b / (i * j);
            int x = ((int) ceil((double) a / (double) bx) + (a % bx == 0 ? 1 : 0)) * bx,
                    y = ((int) ceil((double) b / (double) by) + (b % by == 0 ? 1 : 0)) * by;
            if (x <= c && y <= d) {
                cout << x << ' ' << y << '\n';
                f = true;
                break;
            }
        }
        if (f) break;
    }
    if (!f) cout << -1 << ' ' << -1 << '\n';
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    //init();
    int t;
    cin >> t;
    while (t --) solve();
}

一开始还想着贪心，似也做不出来，淦