商务网站建设pdf,龙华做棋牌网站建设哪家公司便宜,如何把官网,怎么自建一个网站题目大意
有一段长度为nnn的密文#xff0c;密文的每一位都可以用一个非负整数来描述#xff0c;并且每一位都有一个权值aia_iai。你可以操作任意多次#xff0c;每次操作可以选择任意一段密文#xff0c;花费选择的所有位上权值的异或和的代价获得这段密文每一位的异或…题目大意
有一段长度为nnn的密文密文的每一位都可以用一个非负整数来描述并且每一位都有一个权值aia_iai。你可以操作任意多次每次操作可以选择任意一段密文花费选择的所有位上权值的异或和的代价获得这段密文每一位的异或和。求至少需要花费多少代价才能将密文的每一位都破解出来。
数据范围
1≤n≤105,0≤ai≤1091\leq n\leq 10^5,0\leq a_i\leq 10^91≤n≤105,0≤ai≤109 题解
令前iii个未知数的异或和为xix_ixi那么询问[l,r][l,r][l,r]就是询问xr⊕xl−1x_r\oplus x_{l-1}xr⊕xl−1的值。而知道每一个数的值等同于知道每个xix_ixi的值。
一开始我们只知道x0x_0x0的值。对于一次询问[l,r][l,r][l,r]如果在询问之前我们已经知道xl−1x_{l-1}xl−1的值或xrx_rxr的值那么询问之后我们就能知道它们两个的值分别为多少。
将每个xix_ixi看作点iii将询问[l,r][l,r][l,r]看作点l−1l-1l−1向点rrr连一条边那么题目就转化为求让000到nnn的所有点连通的最小代价即求最小生成树。
令前iii个aaa值的异或和为sis_isi那么点iii到点jjj的边的边权为si⊕sjs_i\oplus s_jsi⊕sj。考虑如何求最小生成树。
我们可以把所有sis_isi放在字典树上。对于字典树上的每一个节点它有两棵子树。只需要从两棵子树中各选一个点使它们的异或和最小再把它们连起来即可将这两部分中的点连通。
那怎么选点呢我们可以暴力枚举其中一棵子树中的数然后在另一棵子树上贪心去找与其异或和最小的数对所有数求最小值即可。
因为每个节点只会被其每个父亲枚举一次所以这样做的时间复杂度为O(nlog2w)O(n\log^2 w)O(nlog2w)其中www为aia_iai的最大值。
code
#includebits/stdc.h
using namespace std;
const int N30;
int n,tot1,tmp,a[100005],s[100005],ch[5000005][2];
vectorintv[5000005];
long long ans0;
void pt(int s){int q1;for(int iN;i0;i--){if(!ch[q][(si)1]) ch[q][(si)1]tot;qch[q][(si)1];v[q].push_back(s);}
}
int find(int u,int s,int now){int re0,vq;for(int inow-1;i0;i--){int vq(si)1;if(!ch[u][vq]){re|(1i);vq^1;}uch[u][vq];}return re;
}
void gt(int u,int now){--now;if(ch[u][0]) gt(ch[u][0],now);if(ch[u][1]) gt(ch[u][1],now);if(ch[u][0]ch[u][1]){tmp1N;for(int i0;iv[ch[u][0]].size();i){tmpmin(tmp,find(ch[u][1],v[ch[u][0]][i],now));}anstmp(1llnow);}
}
int main()
{scanf(%d,n);for(int i1;in;i){scanf(%d,a[i]);s[i]s[i-1]^a[i];}for(int i0;in;i) pt(s[i]);gt(1,N1);printf(%lld,ans);return 0;
}
