每日一题- CF1995D

唐氏小状压

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&-(x))
int t,n,c,k,cnt[(1<<18)+5][35];
bool f[(1<<18)+5];
char s[(1<<18)+5];
int calc(int x){
	int res=0;
	while(x)x^=lowbit(x),res++;
	return res;
}
void init(){
	for(int i=0;i<(1<<c);i++)f[i]=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=c;j++)
			cnt[i][j]=0;
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d",&n,&c,&k);
		scanf("%s",s+1);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=c;j++)
				cnt[i][j]=cnt[i-1][j]+(s[i]==j+'A'-1);
		for(int i=0;i<=n-k;i++){
			int st=0;
			for(int j=1;j<=c;j++)
				if(cnt[i+k][j]-cnt[i][j]>=1)
					st|=1<<(j-1);
			f[((1<<c)-1)^st]=1;
		}
		f[((1<<c)-1)^(1<<(s[n]-'A'))]=1;
		for(int i=(1<<c)-1;i>=0;i--)
			for(int j=0;j<c;j++)
				f[i]|=f[i|(1<<j)];
		int res=1e9;
		for(int i=0;i<(1<<c);i++)
			if(!f[i])
				res=min(res,calc(i));
		printf("%d\n",res); 
		init();
	}
	return 0;
}