题解：CF2114B 不完全是回文串

题意

给你一个长度为

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。

代码

CPP

#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;//多测不清空，爆零两行泪
	}
}

题解：CF2114B 不完全是回文串

文章操作

题意

思路

代码

相关推荐

评论

题解：CF2114B 不完全是回文串