OI - 加密 (NOI.AC)

第三场模拟赛了,还是打得不是很好……这道题因为数据边界 $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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/*Lucky_Glass*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N=3e5;

int n;
ll S;
ll inp[N+3],dp[2][1<<21];
int cnt[100];

int main(){
scanf("%d%lld",&n,&S);
for(int i=1;i<=n;i++) scanf("%lld",&inp[i]);
for(int i=0;i<60;i++)
for(int j=1;j<=n;j++)
if(inp[j]&(1ll<<i))
cnt[i]++;
int fn=1,lgfn=0;
while(fn<=2*n) fn<<=1,lgfn++;
memset(dp,-1,sizeof dp);
dp[1][0]=0;
for(int i=0;i<=60;i++){
int now=i&1,las=!(i&1);
for(int j=0;j<=fn;j++)
dp[now][j]=-1;
for(int j=0;j<=fn;j++)
if(dp[las][j]!=-1){
int j_=n-cnt[i]+(j>>1);
if(dp[now][j_]==-1) dp[now][j_]=dp[las][j]|(1ll<<i);
else dp[now][j_]=min(dp[now][j_],dp[las][j]|(1ll<<i));
j_=cnt[i]+(j>>1);
if(dp[now][j_]==-1) dp[now][j_]=dp[las][j];
else dp[now][j_]=min(dp[now][j_],dp[las][j]);
}
ll fS=((S>>i)&1ll)^1ll;
for(int j=fS;j<(1<<21);j+=2)
dp[now][j]=-1;
}
printf("%lld\n",dp[0][0]);
return 0;
}

The End

Thanks for reading!

刷题刷题……

0%