BZOJ 5043 密码破译

发布于 2017-09-23  383 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=5043

题意:求最小的 k 满足\(\sum_{i=1}^{n}b_i \oplus k =m\)。


注意

由于我偷懒,式子均忽略一些边界情况...

由于我菜,说的废话比较多...


考虑到可以按位去考虑答案是什么,对于 k 的第 i 位,选 1/0 都可以把答案消掉一部分,具体地,可以消掉 b 中第 i 位为 0/1 的个数乘\(2^i\) 那么多。我们可以预处理出这个东西。

记\(c_{i,0/1}\) 表示 k 的第 i 位选 1/0 能消掉的数\(x\cdot 2^i\) 的系数 x。

现在考虑 dp,状态怎么设呢?考场上我就想到这里了 T.T

正解是这样的:\(f_{i,j}\) 表示从高到低考虑到第 i 位,m 还剩下 j 时最小的 k 是什么

什么叫 还剩下 j 呢?为了不考虑过多的状态,我们转移时只考虑\(x\cdot 2^i\) 的系数 x。(同时目前考虑的 k 也是这样)每次考虑到下一位时,可以直接的将这些系数乘二去 退位

(由于目前只考虑到了大于等于 i 位的那些情况,真实的 j 肯定可以表示成一个\(x\cdot 2^i\) 的形式,所以只记录系数 x 即可。)

这样就可以转移了,我们枚举这一位下我们 k 选择 1 还是 0,考虑 j 能转移到哪里,首先\(j*2\) 退位,然后消掉了\(c_{i,k}\) 这么多的系数,再加上 m 这一位的系数。

即转移到的状态\(tp=2j-c_{i,k}+[m 的第 i 位为 1]\)(其中,k 为目前枚举的 1/0)

但是直接转移的话 tp 的状态数会很多... 考虑到 tp 大于 n 时是不可能合法的,为什么呢?

显然\(c_{i,0/1}\leq n\),那么如果 tp 在第 j 位大于 n,则一定有\(\sum_{i=1}^{j}c_{i,0/1}\cdot 2^i< 2^{j+1}\),所以大于 n 的状态 tp 一定是消不成 0 的,当然没有记录的意义了。

这样的话状态的总数就是\(60n\) 级别的了,复杂度可以接受。这题太神了...

 


一个非常弱的准退役OIER