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中的字符串，然后把每个字母的数量取个最小值，再加出总和

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

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次方即仅有一个字母是奇数个。区间拓展，莫队启动