Codeforces Round 1022 (Div. 2)

2025-05-01

Codeforces Round 1022 (Div. 2)

link: https://codeforces.com/contest/2108

D题目前通过才一两百， 题目也大概都读了下， 感觉不太有必要看了， 来总结一下。。。

这场总的来说糖丸了， B 只需要讨论就好， C 代码思路都特别简单。 但是这两题加起来 WA 了三次。

其中两次都是很不应该错的地方， 再怎么也不该错的， 而且也耽误时间。 总之还是得多写题， 才能少错， 才能速度更快。

A

这个 A 给我紧张到了， 很看了一会才 AC， 猜了一下。 我猜的是最大的值是数组 $p$ 取 $p_{i} = n - i + 1$ ， 是最大的一个值， 然后每个值间隔 2 。 然后就 AC 了。

// Date: 2025-05-01
// Time: 22:36:38
void ChatGptDeepSeek()
{
    int n;
    cin >> n;
    /*
    0
    2 * (pi-pj)

    */
    int mx = 0;
    for(int i = 1, j = n; i <= n; i++, j--)
        mx += abs(j - i);
    cout << mx / 2 + 1 << '\n';
}

B

其实就分类讨论就行， 我第二次 WA 是因为判断 $x = 0$ 且 $n$ 为偶数时， 输出 $2$ ， 其实想的也是输出 $n$ 的。。。

也是耽误了 8 分钟和扣了50。一定得细心一点吧， 这种分类讨论的题， 提交之前， 一定再把每种情况去简单想一下。

$x = 0$ 时: $n = 1$ 肯定不行； 显然如果 $n$ 为偶数， 那么答案肯定是 $n$ ， 因为 $n$ 个数全取 $1$ 肯定答案是最小的; $n$ 如果是奇数， 那么我们必须找出三个数字， 使得它们异或和为 $0$ ， 然后其他数字全部取 $1$ ， 那么我们的答案就是 $1, 2, 3, 1, 1, ....$ 。

否则， 我们看一下 $x$ 的二进制的 $1$ 的个数， 设为 $cnt$ 。如果 $cnt \ge n$ ， 那么我们一定可以给每个数字二进制位分配正整数个 $1$ ， 使得它们的和恰好等于 $x$ 。

否则， 如果 $n- cnt$ 是偶数， 那么剩下的数字是不会影响答案的， 我们可以让 $cnt$ 个数字之和等于 $x$ 且异或和等于 $x$ （每个数字取 $x$ 的为 $1$ 的 1 个位）； 否则就是我们需要讨论的最后一种情况啦~ 如果 $cnt > 1$ ， 那么可以分一个数字过去， 使得 $1$ 的个数为偶数， 如果 $cnt = 1$ ， 就不能分数字过去， 如果 $x = 1$ ， 那么答案是 $2, 3, 1, 1, 1 , ...$ , 否则答案是 $x + 1, 1, 1, 1, ...$。

然后到这里， 答案应该就分类完了。

// Date: 2025-05-01
// Time: 22:56:16
void ChatGptDeepSeek()
{
    int n, x;
    cin >> n >> x;
    int cnt = 0, tmp = x;
    while (tmp) {
        cnt += tmp & 1;
        tmp >>= 1;
    }
    // cout <<cnt <<'\n';

    if (x == 0) {
        if (n == 1)
            cout << "-1\n";
        else{
            if(n % 2 == 0) cout << n << '\n';
            else{// 1 1 1 1, 2, 3
                cout << n + 3 <<'\n';
            }
        }
        return;
    }
    if (cnt < n) {
        if ((n - cnt) & 1) {
            if (cnt == 1) {
                // 1 2 3, 
                if(x == 1){
                    //2 3， 其他全取1
                    cout << 3 + n <<'\n';
                }else{
                    //x+1 1
                    cout << n + x << '\n';
                }
            }// 8, 9 ^ 1
            else{
                cout << x + n - cnt + 1 << '\n';
            }
        }else {
            cout << x + n - cnt << '\n';
        }
    }else{
        cout << x <<'\n';
    }
}

C

感觉确实不一定比 B 难， 排个序然后顺着弄就行。 可能还是读题比较难。。。

// Date: 2025-05-01
// Time: 23:35:57
void ChatGptDeepSeek()
{
    int n;
    cin >> n;
    vi a(n + 1);
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    int now = a[1], cnt = 0;
    vc<array<int, 3>> info;
    for(int i = 1; i <= n; i++){
        if(a[i] == now)
            cnt++;
        else{
            info.push_back({now, i - cnt, i - 1});
            now = a[i], cnt = 1;
        }
    }
    info.push_back({now, n - cnt + 1, n});
    sort(all(info), greater<>());
    vc<bool> vis(n + 1);
    int ans = 0;
    for(auto [val, l ,r] : info){
        // cerr << val << " " << l << " " << r <<'\n';
        if(l && vis[l - 1]){
            vis[r] = true;
        }else if(r < n && vis[r + 1]){
            vis[l] = true;
        }else{
            vis[l] = vis[r] = true;
            ans++;
        }
    }
    cout << ans << '\n';
}