题解：CF2114B 不完全是回文串

TheTrash · 2025-06-10 19:19:51 · 题解

题意

给你一个长度为 n 的字符串 s，问你能不能通过重新排列字符串中的某些字符使得正好有 k 个 s_i=s_{n-i+1}。

思路

先统计字符串内 0 和 1 的个数，分别保存在 x 和 y 里，然后让 x 和 y 都减去 \frac{n}{2}-k。如果 x<0 或 y<0 说明所有排列中符合 s_i=s_{n-i+1} 的 i 的数量最少也会大于 k，直接输出 NO 即可。接着还要判断能匹配到的索引对的数量是不是正好等于 k。如果是，输出 YES，否则输出 NO。

代码

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
int T,n,k,x,y;
string s;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>k>>s;
        for(int i=0;i<n;i++) s[i]=='0'?x++:y++;
        x-=(n/2-k),y-=(n/2-k);//先减再判断
        if(x<0||y<0) cout<<"NO\n";
        else if(x/2+y/2!=k) cout<<"NO\n";
        else cout<<"YES\n";
        x=0,y=0;//多测不清空，爆零两行泪
    }
}