外国网站上做雅思考试,安监局网站做模拟,做soho的网站,视频制作和剪辑教程CF888G XOR-MST 链接 CF888G 思路 trie上贪心#xff0c;先左右两边连边#xff0c;再用一条边的代价连起左右两颗树。因为内部的边一定比跨两棵树的边权笑#xff0c;显然是对的。 代码自己瞎yy的。启发式合并 代码 #include bits/stdc.h
#define ll long long
usi… CF888G XOR-MST 链接 CF888G 思路 trie上贪心先左右两边连边再用一条边的代价连起左右两颗树。因为内部的边一定比跨两棵树的边权笑显然是对的。 代码自己瞎yy的。启发式合并 代码 #include bits/stdc.h
#define ll long long
using namespace std;
const int _2e57;
int n,a[_],ch[_*30][2],siz[_*30],cnt,col,rt[_*30];
ll ans;
std::vectorint dsr[_*30];
void insert(int x) {int p0;for(int i29;i0;--i) {bool kx(1LLi);siz[p];if(!ch[p][k]) ch[p][k]cnt;pch[p][k];} siz[p];if(!rt[p]) rt[p]col;dsr[rt[p]].push_back(x);
}
int query(int rt,int init,int x) {int prt,ans0;for(int iinit;i0;--i) {bool kx(1LLi);if(ch[p][k]) pch[p][k];else pch[p][!k],ans|1i;}return ans;
}
void dfs(int p,int dep) {if(!ch[p][0]!ch[p][1]) return;if(!ch[p][0]||!ch[p][1]) {dfs(ch[p][0]|ch[p][1],dep-1);rt[p]rt[ch[p][0]|ch[p][1]];} else {int ksiz[ch[p][0]]siz[ch[p][1]];dfs(ch[p][0],dep-1),dfs(ch[p][1],dep-1);rt[p]rt[ch[p][k]];int tmp0x3f3f3f3f;int nbch[p][!k];ch[p][!k]0;for(auto x:dsr[rt[nb]]) {tmpmin(tmp,query(p,dep,x));dsr[rt[p]].push_back(x);}anstmp;ch[p][!k]nb;}
}
int main() {// freopen(a.in,r,stdin);scanf(%d,n);for(int i1;in;i) scanf(%d,a[i]),insert(a[i]);dfs(0,29);coutans\n;return 0;
} 转载于:https://www.cnblogs.com/dsrdsr/p/11405990.html
