题目链接

翻转01

题目描述

给定一个长度为 的 01 字符串和一个整数 。每次操作可以翻转字符串中的任意一个字符（'0' 变为 '1'，'1' 变为 '0'）。

任务是判断是否能通过恰好 次操作，使得字符串变为一个回文字符串。

解题思路

这个问题的核心在于分析将字符串变为回文串所需的翻转次数与给定的操作次数 之间的关系。

1. 计算最小所需翻转次数

要使一个字符串成为回文串，对于所有 （从 0 到 ），必须满足 S[i] == S[n-1-i]。

我们可以遍历字符串的前半部分，比较每一对对称位置的字符 S[i] 和 S[n-1-i]。如果它们不相同，我们必须至少翻转其中一个才能使它们匹配。因此，将字符串变为回文所需的最少翻转次数，就等于这些不匹配的对称字符对的数量。

我们定义这个最小次数为 mismatches。

2. 分析剩余的操作次数

我们总共有 次操作机会。

  • 一个基本条件是 。如果 连最基本的修正都无法完成，那么肯定无法达成目标。

  • 如果 ，我们首先花费 mismatches 次操作来修正所有不匹配的字符对。之后，我们还剩下 remaining_flips = k - mismatches 次操作。

  • 根据题目要求，这 remaining_flips 次操作也必须全部用完，并且不能破坏已经形成的回文结构。我们如何“浪费”掉这些多余的操作呢？

    • 成对消耗: 对于任意一对对称位置 (i, n-1-i)，我们可以同时翻转 S[i] 和 S[n-1-i]。这样会消耗 2 次操作，并且它们之间的相等关系保持不变（a == b 变为 !a == !b）。
    • 单独消耗: 如果字符串的长度 是奇数，那么存在一个中心字符 S[n/2]。我们可以单独翻转这个字符，只消耗 1 次操作，并且不会影响任何对称关系。

3. 得出结论

  • 我们剩下的 remaining_flips 次操作必须被完全消耗掉。
  • 如果 remaining_flips 是偶数，我们可以通过在任意 remaining_flips / 2 对称位置上进行成对翻转来消耗掉它们。这总是可行的。
  • 如果 remaining_flips 是奇数，我们需要一个单独的位置来消耗掉这多出来的 1 次操作。唯一可能的位置就是当 为奇数时的中心字符。
    • 因此，如果 remaining_flips 为奇数且 为奇数，我们可以翻转中心字符 1 次，剩下的偶数次操作再成对消耗。
    • 如果 remaining_flips 为奇数且 为偶数，我们找不到可以单独消耗操作的地方，因此无法达成目标。

最终算法:

  1. 计算不匹配的对称字符对数量 mismatches。
  2. 如果 ，输出 "NO"。
  3. 否则，计算 remaining_flips = k - mismatches。
  4. 如果 remaining_flips 是偶数，输出 "YES"。
  5. 如果 remaining_flips 是奇数：
    • 如果 是奇数，输出 "YES"。
    • 如果 是偶数，输出 "NO"。

代码

#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <cmath>

using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    int mismatches = 0;
    for (int i = 0; i < n / 2; ++i) {
        if (s[i] != s[n - 1 - i]) {
            mismatches++;
        }
    }

    if (k < mismatches) {
        cout << "NO" << endl;
        return;
    }

    int remaining_flips = k - mismatches;
    if (remaining_flips % 2 == 0) {
        cout << "YES" << endl;
    } else {
        if (n % 2 == 1) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }

    private static void solve(Scanner sc) {
        int n = sc.nextInt();
        int k = sc.nextInt();
        String s = sc.next();

        int mismatches = 0;
        for (int i = 0; i < n / 2; i++) {
            if (s.charAt(i) != s.charAt(n - 1 - i)) {
                mismatches++;
            }
        }

        if (k < mismatches) {
            System.out.println("NO");
            return;
        }

        int remainingFlips = k - mismatches;
        if (remainingFlips % 2 == 0) {
            System.out.println("YES");
        } else {
            if (n % 2 == 1) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }
}

import sys

def solve():
    n, k = map(int, sys.stdin.readline().split())
    s = sys.stdin.readline().strip()

    mismatches = 0
    for i in range(n // 2):
        if s[i] != s[n - 1 - i]:
            mismatches += 1

    if k < mismatches:
        print("NO")
        return

    remaining_flips = k - mismatches
    if remaining_flips % 2 == 0:
        print("YES")
    else:
        if n % 2 == 1:
            print("YES")
        else:
            print("NO")

def main():
    try:
        t_str = sys.stdin.readline()
        if not t_str: return
        t = int(t_str)
        for _ in range(t):
            solve()
    except (IOError, ValueError):
        pass

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法: 计数、奇偶性分析
  • 时间复杂度: 对于每组测试数据，我们只需要遍历字符串的前半部分一次，因此时间复杂度为 。
  • 空间复杂度: ，用于存储输入的字符串。