当前位置：首页 > news >正文

赛前训练6 状压

news 2026/6/14 11:55:24

A

简单树上差分.

B

维护 $d_{i,j}$ 表示人 $i$ 在第 $j$ 位与哪些人有区别.预处理即可.

对于每个人,枚举提问的二进制状态;对于提问的每个二进制位,将它们的 $d$ 全部拼起来,若能拼成 ((1<<n)-1)^(1<<i),则产生 $c(j)$ 的贡献,其中 $c(x)$ 代表 $x$ 在二进制下 $1$ 的个数, $j$ 表示当前提问状态.

实现

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
//#define int long long
using namespace std;const int N=25;
int n,m;
int a[N][N],diff[N][N];signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>a[i][j];for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int k=0;k<m;k++)if(a[i][k]!=a[j][k])diff[i][k]|=(1<<j);for(int i=0;i<n;i++){int ans=1e9;for(int j=0;j<(1<<m);j++){int cnt=0,person=0;for(int k=0;k<m;k++)if((j>>k)&1)person|=diff[i][k],cnt++;//cout<<person<<'\n';if((person|(1<<i))==(1<<n)-1)ans=min(ans,cnt);}cout<<(ans==1e9?-1:ans)<<' ';}return 0;
}

C

$n \le 16$,直接状压 dp.

令 $dp_i$ 表示字符串选取情况为 $i$ 时的 trie 树节点最小值.

初始 $dp_{1<<i}=|s_i|$,答案 $dp_{(1<<n)-1}$.

转移考虑两棵 trie 树合并成 $i$,易得 $dp_i=dp_j+dp_{i \oplus j}-len(i)$.其中 $len(i)$ 表示 $i$ 状态下的 LCP.

这东西如何维护?我们发现,一堆字符串重排之后的 LCP,是由它们每种字母的最小出现次数决定的.于是可以维护 $lcp(i,j)$ 表示 $i$ 状态下字母 $j$ 的最小出现次数.要维护 $lcp(i,j)$,则必然还需要维护 $cnt(i,j)$ 表示 $s_i$ 中字母 $j$ 的出现次数.这样,统计出 $cnt$ 后,$lcp$ 只需要枚举状态然后对它们取 $\min$,而 $len(i)$ 只需要加上 26 个字母的 $lcp$ 即可.

实现

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define int long long
using namespace std;const int N=1<<17,M=48,K=1e6+5;
int n;
int len[N],lcp[N][M],cnt[K][M],dp[N];
string s[M];signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n;memset(dp,0x3f,sizeof dp);memset(lcp,0x3f,sizeof lcp);for(int i=0;i<n;i++){cin>>s[i];dp[1<<i]=s[i].size();for(int j:s[i])cnt[i][j-'a']++;}for(int i=0;i<(1<<n);i++){for(int j=0;j<n;j++)if((i>>j)&1)for(int k=0;k<26;k++)lcp[i][k]=min(lcp[i][k],cnt[j][k]);for(int j=0;j<26;j++)len[i]+=lcp[i][j];}for(int i=0;i<(1<<n);i++)for(int j=i;j;j=i&(j-1))dp[i]=min(dp[i],dp[j]+dp[i^j]-len[i]);cout<<dp[(1<<n)-1]+1;return 0;
}