CF1995D Cases 题解

Acoipp · 2024-07-26 15:12:56 · 题解

不太清楚为什么题解大部分是 O(2^cc^2)。

比较显然的，任意相邻 k 个字符必须至少选中一个，那么设这 k 个字符的字符集（不可重）为 T，一共有 n-k+1 个字符集记为 T_1,T_2,\dots,T_{n-k+1}。

题目就要我们构造 S 满足 \forall i 都要有 T_i 和 S 有交，并且 |S| 最小。

那么对于一个 T_i，与它没有交的集合一定是 U-T_i 的子集，其中 U 是字符的全集，于是对 U-T_i 的子集枚举一下然后打上标记就可以了，最后看没有标记的 S 中最小的即可。

于是采用高维前缀和优化，时间复杂度很显然是 O(n+c2^c)。

#include<bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
ll T,n,c,k,i,j,now,p[N],cnt[20],ans;
char s[N];
int main(){
    ios::sync_with_stdio(false);
    cin>>T;
    while(T--){
        memset(cnt,0,sizeof(cnt));
        cin>>n>>c>>k>>(s+1),ans=c,now=0;
        for(i=1;i<=k;i++) now|=(1ll<<(s[i]-'A')),cnt[s[i]-'A']++;
        p[((1<<c)-1)-now]=1;
        for(i=k+1;i<=n;i++){
            now|=(1ll<<(s[i]-'A')),cnt[s[i]-'A']++;
            if(--cnt[s[i-k]-'A']==0) now-=(1ll<<(s[i-k]-'A'));
            p[((1<<c)-1)-now]=1;
        }
        p[((1<<c)-1)-(1<<s[n]-'A')]=1;
        for(i=0;i<c;i++){
            for(j=0;j<(1<<c);j++) if((j>>i)&1) p[j-(1<<i)]|=p[j];
        }
        for(i=0;i<(1<<c);i++) if(!p[i]) ans=min(ans,(ll)__builtin_popcount(i));
        cout<<ans<<endl;
        for(i=0;i<(1<<c);i++) p[i]=0;
    }
    return 0;
}