题解：CF2252B Always Changing

_Chaison_ · 2026-08-10 21:45:44 · 题解

洛谷链接

Codeforces 链接

Vjudge 链接

\text{AC} 记录

题目简述

给定一个由 0 和 1 组成的字符串，每次操作可以删除一个字符，但删除的字符必须严格交替。求最少删除次数，使剩下的字符串成为相邻字符均不相同的交替串。若无法做到，输出 -1。

代码思路

首先计算出原串中 0 和 1 的个数，并根据 n 的奇偶性确定最终保留的交替字符串中两种字符的最少需求量；若删除次数 k 超过了最大可能删除次数，则无解；否则，最终保留的字符串长度 m=n-k，它必然是一个交替串，该交替串的奇数位置全部是一种字符、偶数位置全部是另一种字符，我们只需要确定这两种角色分别由 0 还是 1 来担任。通过比较原串中 0 和 1 的实际数量与填充奇数，偶数位置所需的最少数量，哪边不够就把对应的字符角色交换，以确保原串中的 0 和 1 数量足够覆盖；多余的 0 或 1 会被分别附加到交替串的第一个位置块和第二个位置块上，这样既能维持交替性，又能正好消耗掉所有字符，最终构造出的交替串恰好由删除后剩余的字符组成，且删除过程必定满足交替删除规则，因为删除的总 0 数和总 1 数之差不超过 1，并且都可以通过先删一种字符再交替删另一种来完成。

\color{green}\text{AC Code}

#include <cstdio>
#include <string>
#include <algorithm>

void solve() {
    int n, k;
    scanf("%d%d", &n, &k);
    int rem = n & 1;
    std::string s;

    int one = n >> 1;
    int zero = one + rem;
    int max_k = (one - 1) + (zero - 1);
    if (max_k < k) {
        puts("-1");
        return;
    }

    int m = n - k;
    int odd_cnt = (m + 1) >> 1;
    int even_cnt = m >> 1;
    s.resize(n);
    int pos = 0;
    char odd_char = '0', even_char = '1';
    int cnt0 = zero, cnt1 = one;

    if (cnt0 < odd_cnt || cnt1 < even_cnt) {
        std::swap(odd_char, even_char);
        std::swap(cnt0, cnt1);
    }

    int odd = cnt0 - odd_cnt;
    int even = cnt1 - even_cnt;

    for (int i = 1; i <= m; ++i) {
        int len = 1;
        if (i == 1) len += odd;
        if (i == 2) len += even;
        char ch = (i & 1) ? odd_char : even_char;
        for (int j = 0; j < len; ++j)
            s[pos++] = ch;
    }

    printf("%s\n", s.c_str());
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        solve();
    }
    return 0;
}