网站建设 企泰科技,成都市青羊区建设局官方网站,设计师图片素材,网站设计及建设合同解析
有的时候#xff0c;看起来是暴力的东西再稍微想想性质就是正解了。
本题有两种做法#xff0c;一种使用了trie树#xff0c;一种没有。但本质是一样的#xff0c;只是trie树把我们的所求显性的表达了出来。
考虑trie树暴力怎么做。 对于一个特定的 xxx 走到一个结…解析
有的时候看起来是暴力的东西再稍微想想性质就是正解了。
本题有两种做法一种使用了trie树一种没有。但本质是一样的只是trie树把我们的所求显性的表达了出来。
考虑trie树暴力怎么做。 对于一个特定的 xxx 走到一个结点时有两种选择
两个数都在某一棵子树里选择。两个数分别在两棵子树中选择。
对于第一种递归寻找答案对于第二种因为它们在当前结点已经产生了 2k2^k2k 的异或因此接下来递归一定是同向子树尽可能大异向子树尽可能小。 直接做单次复杂度是 O(nk)O(nk)O(nk) 的无法接受。
注意到如果 ai,aja_i,a_jai,aj 二进制的一些前缀相同那么 xxx 的这些位是什么并不影响最终结果。 那么回到刚才的第一种选择我们如果这是第 iii 层的结点递归寻找的答案前 iii 位必然相同那么我们其实并不关心这些位 xxx 的取值也就是说一共只有 2k−i2^{k-i}2k−i 种答案是我们需要关注的。
类似的第二种选择所需要的 mn,mxmn,mxmn,mx 也只关心第 iii 位之后的取值。
这些取值状态的总数是 O(2kk)O(2^kk)O(2kk) 的不难通过分析从两棵子树的状态 O(1)O(1)O(1) 得到其父亲各状态的转移。 总复杂度 O(2kk)O(2^kk)O(2kk)。
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
using namespace std;const int N6e5100;
const int inf1e9;
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}int n;
int mi[25],mn[20][N],mx[20][N],res[20][N];signed main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifnread();int limread();mi[0]1;for(int i1;ilim;i) mi[i]mi[i-1]1;for(int i0;imi[lim];i){mn[0][i]inf;mx[0][i]-inf;res[0][i]inf;}for(int i1;in;i){int xread();mn[0][x]mx[0][x]0;}for(int k1;klim;k){for(int x0;xmi[lim];x){int yx^mi[k-1];mn[k][x]min(mn[k-1][x],mn[k-1][y]mi[k-1]);mx[k][x]max(mx[k-1][x],mx[k-1][y]mi[k-1]);res[k][x]min(min(res[k-1][x],res[k-1][y]),mn[k-1][y]mi[k-1]-mx[k-1][x]);//printf(k%d x%d y%d mn%d mx%d res%d\n,k,x,y,mn[k][x],mx[k][x],res[k][x]);}}for(int i0;imi[lim];i) printf(%d ,res[lim][i]);return 0;
}
/*
*/
