翻转01

题目链接: https://www.nowcoder.com/practice/2058328e7de94037b556fd4d892820d3

题意

给定一个长度为 的仅由 0、1 构成的字符串 和整数 。每次操作可以选择字符串中任意一个字符并将其翻转（0 变 1，1 变 0）。问经过恰好 次操作后，字符串 是否能成为回文字符串。

思路分析

关键观察：

1. 统计字符串中不匹配的对数 diff：即对于所有 ，满足 的对数。

1. 最少需要 diff 次操作才能将字符串变为回文（每个不匹配的对需要翻转其中一个字符）。

1. 如果 ，则无论如何也无法达成，输出 NO。

1. 如果 ，设 （多余的操作次数）：

- 每次多余的操作必须"抵消"：即对同一个字符翻转两次（相当于没有操作）。

- 如果 是偶数，可以直接抵消，输出 YES。

- 如果 是奇数，需要一个"自由位"来消耗 1 次操作：

- 若 为奇数，字符串有中间字符 ，它不参与任何配对，可以自由翻转 1 次（不影响回文性质），输出 YES。

- 若 为偶数，没有中间字符，无法消耗奇数次多余操作，输出 NO。

总结规则：

• 若 ：NO
• 若 为偶数：YES
• 若 为奇数且 为奇数：YES
• 其他：NO

等价写法：YES 当且仅当 且（ 或 ）。

复杂度

• 时间复杂度：，遍历一次字符串统计不匹配对数
• 空间复杂度：

代码

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while (t--) {
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;

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

        if (k < diff) {
            cout << "NO\n";
            continue;
        }

        int extra = k - diff;

        if (extra % 2 == 0) {
            cout << "YES\n";
        } else {
            cout << (n % 2 == 1 ? "YES" : "NO") << "\n";
        }
    }

    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        
        while (t-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            String s = br.readLine().trim();
            
            int diff = 0;
            for (int i = 0; i < n / 2; i++) {
                if (s.charAt(i) != s.charAt(n - 1 - i)) {
                    diff++;
                }
            }
            
            if (k < diff) {
                sb.append("NO\n");
                continue;
            }
            
            int extra = k - diff;
            
            if (extra % 2 == 0) {
                sb.append("YES\n");
            } else {
                sb.append(n % 2 == 1 ? "YES\n" : "NO\n");
            }
        }
        
        System.out.print(sb);
    }
}

样例验证

样例1：

• n=6, k=1, s="101100"：不匹配对为 (s[0],s[5])=(1,0) 和 (s[1],s[4])=(0,0)...

实际：s[0]='1' vs s[5]='0'（不匹配），s[1]='0' vs s[4]='0'（匹配），s[2]='1' vs s[3]='1'（匹配）→ diff=1。

k=1 ≥ diff=1，extra=0（偶数）→ YES ✓

• n=6, k=2, s="101100"：diff=1，extra=1（奇数），n=6（偶数）→ NO ✓
• n=6, k=3, s="101100"：diff=1，extra=2（偶数）→ YES ✓