10.5 状压

(・∀・(・∀・(・∀・*)

T2

这道题看着比较麻烦，我们需要不断猜测特殊值才能猜出一个人，并且还要求最小

考虑到数据非常小，我们可以使用状态压缩或者

dfs

求解。关于这些方法，其实都没有特别多的差别。我们可以考虑使用

O(n^2m)

的时间去预处理每个人在被提问某个特征值时能够排除的集合。再使用

O(m^2)

的时间去枚举一个

01

序列，枚举出可能的提问方案。用这个方案与上述的预处理进行合并，判断能不能把除了需要的人以外的所有人排除就可以

T3

先说结论，T3的数据很小。需要考虑每一个字母出现次数等状态，判定为状压

看到

Trie

竟觉得有些熟悉。对于两个字符串

s、t

。设

s

与

t

的相同字符数为

x

。那么如果我们把它们插入字典树，那么最小的节点就是

s.size()+t.size()-x

我们可以枚举字符串，统计出现的字母次数。我们可以设数组

dp[i]

表示选了状态为

i

的字符串集合的最少节点数。我们枚举一段区间的子集

j

，

len[i]

是状态

i

中字符串的字母相同数量。那么我们不难得出转移方程：

$dp[i]=min(dp[i],dp[j]+dp[j^i]-len[i])$

计算

len[i]

时，我们可以枚举

i

中的字符串，然后把每个字母的数量取个最小值，再加出总和

注意：枚举子集的时候，有优化枚举为：

CPP

for(int j=i;j!=0;j=i&(j-1))

T4

状态压缩在这道题其实是为莫队做辅助的来着

如果是考虑回文串，如

aa

或者

abcdefedcba

这种。那么我们不难发现，回文串上的字母出现次数要么全都是偶数，要么只有一个是奇数。

仔细一看，区间内我们需要关心的就只是字母次数的奇偶，自然想到了异或。我们可以用数组

cnt[1<<26]

来维护字母出现次数的奇偶状态。先行预处理，把所有的前缀区间的状态计算出来，那么剩下的区间我们都可以用异或表示出答案。用数组

a

表示区间

[1,n]

的字母状态，那么关于区间

[x,y]

，该区间的状态值就是

a[y] xor a[x-1]

(

xor

为异或)

那么这道题就转化为了：

关于区间 $[x,y]$ ,选择 $i∈[x-1,y]$ 的两个不同位置的 $a$ 进行异或是否能得到 $0$ 或者 $2$ 的 $X$ 次方

得到

0

即字母都是奇数个，

2

的

X

次方即仅有一个字母是奇数个。区间拓展，莫队启动

文章操作

(・∀・(・∀・(・∀・*)

T2

T3

T4

相关推荐

评论

10.5 状压