cfRound#764(Div.3)Summary

Codeforces Round 764(Div. 3)

CONTEST传送门

战况

Standing

Rating

补题

D - Palindromes Coloring

题目

• time limit per test: 2 seconds
• memory limit per test: 256 megabytes
• input: standard input
• output: standard output

You have a string s consisting of lowercase Latin alphabet letters.

You can color some letters in colors from 1 to k. It is not necessary to paint all the letters. But for each color, there must be a letter painted in that color.

Then you can swap any two symbols painted in the same color as many times as you want.

After that, k strings will be created, i-th of them will contain all the characters colored in the color i, written in the order of their sequence in the string s.

Your task is to color the characters of the string so that all the resulting k strings are palindromes, and the length of the shortest of these k strings is as large as possible.

Read the note for the first test case of the example if you need a clarification.

Recall that a string is a palindrome if it reads the same way both from left to right and from right to left. For example, the strings abacaba, cccc, z and dxd are palindromes, but the strings abab and aaabaa — are not.

Input

The first line of input data contains a single integer t (1 ≤ t ≤ 10⁴ ) — the number of input data sets in the test.

The descriptions of the input data sets follow.

The first line of the description of each input data set contains two integers n and k ( 1 ≤ k ≤ n ≤ 2⋅10⁵ ) — the length of the string and the number of colors in which its letters can be painted. The second line of the description of each input data set contains a string s of length n consisting of lowercase letters of the Latin alphabet.

It is guaranteed that the sum of n over all test cases does not exceed 2⋅10⁵ .

Output

For each set of input data, output a single integer — the maximum length of the shortest palindrome string that can be obtained.

Example

input

10
8 2
bxyaxzay
6 3
aaaaaa
6 1
abcdef
6 6
abcdef
3 2
dxd
11 2
abcabcabcac
6 6
sipkic
7 2
eatoohd
3 1
llw
6 2
bfvfbv

output

3
2
1
1
1
5
1
1
3
3

Note

• In the first test case, s =”bxyaxzay”, k=2. We use indices in the string from 1 to 8. The following coloring will work: bxyaxzaybxyaxzay (the letter z remained uncolored). After painting:

  • swap two red characters (with the indices 1 and 4), we get axybxzay;
  • swap two blue characters (with the indices 5 and 8), we get axybyzax.

  Now, for each of the two colors we write out the corresponding characters from left to right, we get two strings aba and xyyx. Both of them are palindromes, the length of the shortest is 3. It can be shown that the greatest length of the shortest palindrome cannot be achieved.

• In the second set of input data, the following coloring is suitable: [1,1,2,2,3,3]. There is no need to swap characters. Both received strings are equal to aa, they are palindromes and their length is 2.

• In the third set of input data, you can color any character and take it into a string.

• In the fourth set of input data, you can color the i-th character in the color i.

• In the fifth set of input data can be colored in each of the colors of one character.

• In the sixth set of input data, the following coloring is suitable:

  [1,1,1,1,1,2,2,2,2,2,0]. Rearrange the characters so as to get the palindromes abcba and acbca.

大概意思

输入一个长度为 n 的由小写字母组成的字符串，取其中的字母组成 k 个回文字符串，每个字母(位置不同的每个字母)最多只能属于一个字符串。问怎样取能使得取得的 k 个回文字符串中的最短的那一个尽量长。输出这个长度。

我当时的思路

在一个回文串中，若该回文串的长度为偶数，则每个字母出现的次数都是偶数(即成对出现)，若该回文串的长度为奇数，则有且只有一个字母出现的次数为奇数，且其他字母出现的次数为偶数(成对出现)。

记录下原字符串中每个字母出现的次数，接着，记录下成对出现的字母有几组(记两个相同的字母为一组)和单个出现的字母有几个。

接着，就是对每一种情况的分析及枚举(详见代码)。

当时的代码

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#define Inf 0x3f3f3f3f
using namespace std;
typedef pair<int,int> P;
typedef long long LL;
const int MAXX=200005;
const double eps=0.0000001;

int n,k,num[200];
char a[MAXX];

void solve_it(){
	scanf("%d%d",&n,&k);
	getchar();
	scanf("%s",a+1);
	int len=strlen(a+1);
	for(int i=1;i<=len;++i){
		++num[a[i]];
	}
	int sum=0,dan=0;
	for(int i='a';i<='z';++i){
		if(num[i]%2==1){
			sum+=num[i]-1;
			++dan;
		}
		else
			sum+=num[i];
	}
	
	sum/=2;
	int ans;
	if(k>n/2)
		ans=1;
	else if(sum<k)
		ans=1;
	else{
		ans=sum/k*2;
		if(sum%k==0){
			if(dan>=k)
				++ans;
		}
		else{
			int s=sum%k;
			dan+=s*2;
			if(dan<k)
				ans=ans;
			else
				++ans;
		}
	}
	
	printf("%d\n",ans);
	
	for(int i='a';i<='z';++i)
		num[i]=0;
}

int main(){
	int t;scanf("%d",&t);
	while(t--)
		solve_it();
	
	return 0;
}

现在想的思路

最小值最大化，典型的二分。(但是当时我不会写二分😭,而且看着E题和F题都好像要用到二分)

现在的代码

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#define Inf 0x3f3f3f3f
using namespace std;
typedef pair<int,int> P;
typedef long long LL;
const int MAXX=200005;
const double eps=0.0000001;

int n,k,num[200];
int sum=0,dan=0,can;
char a[MAXX];

bool check(int jj){
	if(jj<=sum/k*2+can)
		return true;
	else
		return false;
}

void solve_it(){
	scanf("%d%d",&n,&k);
	getchar();
	scanf("%s",a+1);
	int len=strlen(a+1);
	for(int i=1;i<=len;++i){
		++num[a[i]];
	}
	for(int i='a';i<='z';++i){
		sum+=num[i]/2;
		dan+=num[i]%2;
	}
	
	if(sum%k*2+dan>=k)
		can=1;
	else
		can=0;
	
	int l=1,r=n,mid;
	while(l<r){
		mid=(l+r+1)/2;
		if(check(mid))
			l=mid;
		else
			r=mid-1;
	}
	
	printf("%d\n",r);
	
	for(int i='a';i<='z';++i)
		num[i]=0;
	sum=dan=0;
}

int main(){
	int t;scanf("%d",&t);
	while(t--)
		solve_it();
	
	return 0;
}

总结

二分杀我