Codeforces1004(Div2 A-E)

TwindT Ranking++
  2025-02-12 15:24:36 2025-02-12 15:24:36 创建   2025-02-12 22:01:17 2025-02-12 22:01:17 更新      

感觉这场整体都很神秘, 很符合cf特色

A. Adjacent Digit Sums

题目链接:https://codeforces.com/contest/2067/problem/A

首先我们想到, 对一个数加 1 在不考虑进位时体现在数位和上其实也是加 1, 所以如果 y == x + 1 此时一定满足;

对于 y != x + 1 时, n至少个位是 9 , 这样加1出现进位才能使得数位和差大于 1;

这样 x 就会比 y 大 i * 9 - 1 (i为未知数) 我们只用枚举 i 即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve() {
    int x, y;
    cin >> x >> y;

    if (y == x + 1) {
        cout << "Yes\n";
        return;
    }

    for (int i = 1;i <= x / 9;i++) {
        if (y == x - 9 * i + 1) {
            cout << "Yes\n";
            return;
        }
    }

    cout << "No\n";
}

B. Two Large Bags

题目链接:https://codeforces.com/contest/2067/problem/B

通过题目我们可以知道, 对于大数无法平分给两个数组的情况, 我们可以利用小数加 1 这个条件来解决;

对于个数只有 0 或者 2 的元素我们无法再拆分, 而对于大于 2 的元素, 因为要满足加 1 这个条件我们必须剩两个平分两个数组,

所以我们贪心, 将剩下的全部加到后一个元素上, 最终如果剩下的数量为偶数则满足条件.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void solve() {
    int n;
    cin >> n;
    vector<int> v(n + 1);
    map<int, int> mp;
    for (int i = 1;i <= n;i++) {
        cin >> v[i];
        mp[v[i]]++;
    }

    for (int i = 1;i <= n;i++) {
        if (mp[i] == 0 || mp[i] == 2) {
            continue;
        } else if (mp[i] == 1) {
            cout << "No\n";
            return;
        } else {
            mp[i + 1] += mp[i] - 2;
        }
    }

    if (mp[n + 1] % 2) cout << "No\n";
    else cout << "Yes\n";
}

C. Devyatkino

题目链接:https://codeforces.com/contest/2067/problem/C

根据题目我们知道, 我们每次操作就是加上 9, 99, 999 … 其中一个;

仔细观察后我们能发现, 不管加上上述提到的那个数, 结果的个位都会-1, 因此我们就能在很有限的操作次数下得到结果;

考虑到可能出现进位或者其他数位与 9 相加得到 7 的情况, 我们只要暴力枚举 9, 99, 999 … 即可.

而由于 n 最大为1e9, 所以我们把枚举上限设置到小于1e9.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void solve() {
    int n;
    cin >> n;
    
    // 判断是否存在数位为7
    auto check7 = [&] (ll x) -> bool {
        while (x) {
            int mid = x % 10;
            x /= 10;
            if (mid == 7) return true;
        }
        return false;
    };

    ll x = 9;
    ll ans = 1e9;
    while (x < 1e9) {
        ll num = n;
        while (true) {
            if (check7(num)) {
                ans = min(ans, (num - n) / x);
                break;
            }
            num += x;
        }
        x = x * 10 + 9;
    }

    cout << ans << '\n';
}

D. Object Identification

题目链接:https://codeforces.com/contest/2067/problem/D

根据题目我们能得到一些关键信息:

  • 对于对象 A 如果没有路径则会返回 0 , 而因为题目限制对象 B 是不会返回 0 的, 我们可以以此区分 A, B;
  • 数组 x[i] 的范围是 1-n ,那么数组x可以分为两种情况:一种是 1-n 全部出现, 另一种没有全部出现;

首先对于全部出现的情况, 我们可以选择相差最大的两个x(只能是 1 和 n), 进行两次询问, 正着一次, 反着一次,

如果是 A 对象, 那么在路径最长的情况下两次询问结果中只可能有一次为 n - 1, 不可能两次都是 n - 1;

对于另一种情况, 那么未出现的数出度为0, 因此我们询问该点和另一个出现过的点, 结果一定为 0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void solve() {
    int n;
    cin >> n;
    map<int, int> mp;
    for (int i = 1;i <= n;i++) {
        int x;
        cin >> x;
        mp[x] = i;
    }

    auto query = [&] (int x, int y) -> int {
        cout << "?" << " " << x << " " << y << endl;
        int ans;
        cin >> ans;

        return ans;
    };

    if (mp.size() == n) {
        if (query(mp[1], mp[n]) >= n - 1 && query(mp[n], mp[1]) >= n - 1) cout << "! B" << endl;
        else cout << "! A" << endl;
    } else {
        int x,y;
        for (int i = 1;i <= n;i++)  {
            if (mp[i]) x = i;
            else y = i;
        }

        if (query(y, x)) cout << "! B" << endl;
        else cout << "! A" << endl;
    }
}

E. White Magic

题目链接:https://codeforces.com/contest/2067/problem/E

观察到如果序列中不存在 0 那么答案显然为 n;

假设出现了 0 那么一定是保留最左边的 0 将剩余的 0 全部删除最优, 这样保证了 0 右边的是全部满足题设条件的;

此时我们只用判读左边是否满足题设条件, 如果不满足我们就将剩下的一个 0 删除即可;

我们可以预处理出来每个位置的 mex, 然后在维护最小值的同时判断即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++) cin >> a[i];

    int flag = 0;
    vector<int> v;
    for (int i = 1;i <= n;i++) {
        if (a[i] == 0 && flag) continue;

        if (a[i] == 0) flag = 1;
        v.push_back(a[i]);
    }

    if (!flag) {
        cout << n << '\n';
        return;
    }

    // 预处理mex
    int len = v.size();
    vector<int> st(n + 1);
    vector<int> getmex(n + 1);
    for (int i = len - 1;i > 0;i--) {
        if (v[i] < n) st[v[i]] = 1;
        int mex = getmex[i + 1];
        while (mex < n && st[mex]) mex++;

        getmex[i] = mex;
    }

    int mi = INF;
    flag = 1;
    for (int i = 0;i < len;i++) {
        mi = min(mi, v[i]);

        if (mi < getmex[i + 1]) {
            flag = 0;
            break;
        }
    }

    cout << v.size() - 1 + flag << '\n';
}
目录
Codeforces1004(Div2 A-E)
  1. A. Adjacent Digit Sums
  2. B. Two Large Bags
  3. C. Devyatkino
  4. D. Object Identification
  5. E. White Magic