题解 | 翻转01

#include <bits/stdc++.h>
using namespace std;
// 判断：长度为 n 的二进制串 s，是否能在恰好 k 次单点翻转后变成回文
bool can(const string& s, int k) {
    int n = (int)s.size();
    int mism = 0;                         // 两端不相等的“对数”
    for (int i = 0; i < n / 2; ++i) {
        if (s[i] != s[n - 1 - i]) ++mism;
    }
    if (k < mism) return false;           // 不够修复所有不相等的对
    if (n % 2 == 1) return true;          // 有中间位，剩余随便花
    return ((k - mism) % 2 == 0);         // 偶长度：剩余必须是偶数
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, k;
        string s;
        cin >> n >> k >> s;               // 读入 n, k, s
        cout << (can(s, k) ? "YES" : "NO") << '\n';
    }
    return 0;
}
// 64 位输出请用 printf("%lld")