文章目录

题目思路代码思考

题目

思路

我们可以得到： $$\{\begin{array}{l}{x}_1=y_1\wedge k\\ x_2=y_2\wedge k\\ ...\\ x_n=y_n\wedge k\\ {\sum }_{i=1}^n{x}_i=S\end{array}$$ 对所有 $y$ 第 $i$ 位为 $0$ 记为 $cn{t}_{i0}$ 对所有 $y$ 第 $i$ 位为 $1$ 记为 $cn{t}_{i1}$ 如果我们 $k$ 第 $i$ 位为 $0$ ，答案就会增加 $(1<<i)\ast cn{t}_{i1}$ 如果我们 $k$ 第 $i$ 位为 $1$ ，答案就会增加 $(1<<i)\ast cn{t}_{i0}$ 即对于 $k$ 的每一位要考虑填 $0$ 或者 $1$ 如果直接枚举会爆掉 但是我们发现所有 $cnt\in [0,n]$ 发现 $n$ 最大 $18$ 位左右 如果认为是从低位到高位确定，把答案增加表示成二进制形式 此时 $0\sim i$ 位的答案统一表示成 $(1<<i)\ast t$ 的形式 (少的部分就是 $S$ 最低的 $i-1$ 位)， $i$ 位对 $i+1$位的答案增加最多只会让位数加1，也就 $20$ 位左右 而如果我们第 $i$ 位确定后肯定 $i$ 位和比 $i$ 位小的位数都和 $S$ 一样 于是我们可以反过来通过这 $20$ 位保存 $k$ 最小的 于是就有 $Dp$ 定义： $f[i][j]:前i位,第i位对第i+1位进位为j的最小秘钥$

代码

#include<set> #include<map> #include<stack> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<climits> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define LL long long using namespace std; LL read(){ bool f=0;LL x=0;char c=getchar(); while(c<'0'||'9'<c){if(c=='-')f=1;c=getchar();} while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar(); return !f?x:-x; } #define MAXN 300000 #define INF 4600000000000000000ll LL num[MAXN+5],cnt[100][2],f[65][(1<<20)+5]; int main(){//4611686018427387903 int n=read();LL S=read(); for(int i=1;i<=n;i++)//f[i][j]:前i位,第i位对第i+1位进位为j的最小秘钥 num[i]=read(); for(int j=0;j<=60;j++) for(int i=1;i<=n;i++) cnt[j][(num[i]>>j)&1]++; for(int i=0;i<=60;i++) for(int j=0;j<=(1<<20);j++) f[i][j]=INF; if((cnt[0][0]&1)==(S&1)) f[0][cnt[0][0]>>1]=1; if((cnt[0][1]&1)==(S&1)) f[0][cnt[0][1]>>1]=0; for(int i=0;i<60;i++){ LL t=(1ll<<(i+1)); for(int j=0;j<=(1<<20);j++){ if(f[i][j]==INF) continue; if(((j+cnt[i+1][0])&1)==((S>>(i+1))&1)) f[i+1][(j+cnt[i+1][0])>>1]=min(f[i+1][(j+cnt[i+1][0])>>1],f[i][j]+t); if(((j+cnt[i+1][1])&1)==((S>>(i+1))&1)) f[i+1][(j+cnt[i+1][1])>>1]=min(f[i+1][(j+cnt[i+1][1])>>1],f[i][j]); } } if(f[60][0]==INF) puts("-1"); else printf("%lld\n",f[60][0]); return 0; }

思考

考试时想到了 $cnt$ 很小，但是思路很接近，往状压方面想了，但就是没写出来，反映出对状压不熟悉。