专栏文章
组一辈子钥队
题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @minni3lx
- 此快照首次捕获于
- 2025/12/02 05:18 3 个月前
- 此快照最后确认于
- 2025/12/02 05:18 3 个月前
ZROI#3312. 魔力之钥
题意：给两个长度为的数组其中,，找到一个使得最小，输出这个式子的最小值。
首先有个我一开始就没看出来的结论，通过比较两个数最高的不同位上谁是来比的，也就是两数的异或值的最高位上谁是1，因此和的大小就是看的最高位，也就是。而
当和能够放在一起考虑时，发现能够通过逐位确定把每一位的贡献从绝对值分离出来，具体而言，对于建字典树，然后让在上面，往左则表示此位为，此时右子树此位的值为，因此要加上右子树的贡献，但我们此时只知道的前位，低位的贡献就需要预处理了。
令表示所有在子树内的在第位为时在第位上的贡献，因此插入的时候遍历所有更低位，将在遍历的位上的正负性和点代表的位以下和的正负性相乘再乘上遍历的位本身的贡献即可。上面的位不需要考虑，因为遍历到说明是顺着子树内所有(显然相同)的高位走的，所以高位全为。
然后时记录表示第位为时所有的贡献，每次跳一边的点时把另一子节点的加到上即可，最后无法遍历时剩下没选的低位贪心选择每一位的较小贡献统计就行，具体看代码。
CPP#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
#define ll long long
const int K=32;
int trie[MAXN*K][2],n,cnt=1;
ll f[MAXN*K][2],ans=1e18;
ll g[MAXN*K][K][2];
void insert(int x,int a,int b){
int p=1;
for(int i=30;i>=0;i--){
int now=(x>>i)&1;
if(!trie[p][now])
trie[p][now]=++cnt;
p=trie[p][now];
int q=(((a>>i)&1)?1:-1);
for(int j=i;j>=0;j--)
for(int now:{0,1})
g[p][j][now]+=(1ll<<j)*(((a>>j)&1)-(((b>>j)&1)^now))*q;
}
}
void dfs(int x,int k,ll sum){
if(k<0||!x){
for(int i=0;i<=k;i++)
sum+=min(f[i][0],f[i][1]);
ans=min(ans,sum);
return;
}
for(int now:{0,1}){
for(int i=k;i>=0;i--)
for(int j:{0,1})
f[i][j]+=g[trie[x][!now]][i][j];
dfs(trie[x][now],k-1,sum+f[k][now]);
for(int i=k;i>=0;i--)
for(int j:{0,1})
f[i][j]-=g[trie[x][!now]][i][j];
}
}
int a[MAXN],b[MAXN];
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++){
cin>>b[i];
insert(a[i]^b[i],a[i],b[i]);
}
dfs(1,30,0);
cout<<ans<<"\n";
return 0;
}
相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...