第三场模拟赛了,还是打得不是很好……这道题因为数据边界 $2^{59}$ 判断错了,直接爆掉 75 分 QwQ
Part1. 题面
有一种加密方式:
密钥为 $k$,明文为 $x$,那么加密过后得到的密文是 $y=x\oplus k$($\oplus$ 是异或)
现在有 $n$ 条密文 $y_1,y_2,\cdots,y_n$,它们是由同一个密钥 $k$ 加密得到的。已知这 $n$ 条密文对应的明文之和为 $S$,求密钥 $k$。
如果没有这样的 $k$,输出 -1
,否则输出可能的最小的 $k$。
数据规模:$1\le n\le3\times10^5,0\le S<2^{60},0\le y_i<2^{60}$
Part2. 题解
对于这样的问题,首先发现没有办法贪心(因为异或和对于每一位并没有非常强的限制)。然后就有一种比较常见的方法就是逐位 DP!
之前做过不少限制“几个数异或起来的大小”的数位 DP,这些 DP 往往利用异或的最高位限制来转移、判断非法情况。但是这道题比较特别——它是从低位开始 DP 的,因为这道题限制的是“异或之和”,最高位其实限制比较低,因为该位可能是后面的数进位得到的;相反,最低位的限制就较强,因为任何一个数位的异或值只可能影响到更高位。
也就是说,当我们决策第 i 位时,这个决策不可能影响到低位的异或和,就可以限制了。
于是我们从低位开始,决策密钥的第 i 位是多少。不难发现,决策第 i 位最多影响到第 $\left\lceil\log_2n\right\rceil+i$ 位,因此我们需要状压一下从第 i 位到第 $ \left\lceil\log_2n\right\rceil+i$ 位的异或和。
定义 DP 状态为 dp[i][S]
表示“已经决策了密钥的从低位开始的 i 位,得到的 从第 i 位开始的 异或和为 S”的最小密钥为多少。
然后考虑由 dp[i-1][S]
转移到 dp[i][S']
:
- (当然要先预处理一下有多少个密文的第 i 位为 1,记为
cnt[i]
) - 如果第 i 位取 0,就会产生 $2^i\times cnt[i]$ 的异或和,因为异或和是从第 i 位开始的,所以 $2^i$ 就不考虑、第 i-1 位直接左移一位删去,所以
S'=(S>>1)+cnt[i]
; - 如果第 i 位取 1,就会产生 $2^i\times(n-cnt[i])$ 的异或和,对 S 的贡献是
S'=(S>>1)+n-cnt[i]
。
总的来说,就得到了这样两个状态转移:dp[i][(S>>1)+cnt[i]]=min{dp[i-1][S]}
;dp[i][(S>>1)+n-cnt[i]]=min{dp[i-1][S]|(1<<i)}
。
但是计算时有一些 S 是不合法的,即判断异或和的第 i 位是否和要求相符,因为之后的决策都不可能影响到第 i 位的异或和,所以必须保证第 i 位决策后,第 i 位的异或和正确。
然后最后转移到第 60 位开始的异或和为 0,也就是 dp[60][0]
就是答案,因为异或和最多只有 59 位,从 60 位开始的异或和一定为 0。
>> 考场上的锅
就是最后这里判断错了,误把答案当成了dp[59][0]
,实际上第 59 位可能是 1。
Part3. 源代码
可以状压一下(好像不状压也开得下)。
1 | /*Lucky_Glass*/ |
The End
Thanks for reading!
刷题刷题……