前注:关于这题,本人的解法暂时没有成功通过此题,原因是被卡常了。可能需要等待某种机缘来请人调试。


类似uoj的一道题(新年的繁荣),不过是一个有些简单的版本。

因为是完全图,有没有办法明显优化建边,所以考虑用这个Boruvka算法。MST学习笔记里应当记下来了,可以自行前往。然后在这里,就发现使用Boruvka的话明显就有了可以优化的地方——每个点向外找一条最小的边。这里,因为异或的特殊性,所以可以想到用01trie来查找xor最小值。于是boruvka就与数据结构结合起来了。然后照着流程做即可。

不过注意一个问题:每轮连通块内的点找trie上最小异或值,可能会找到块内的点(甚至自己),所以要避免,这里可以对于每个子树,维护一个min,max,代表子树内叶子代表的点所在的块编号的最大最小值,于是查找的时候就可以提前判断,避免走入不合法的地方。

但是被卡常了。。2s时限,跑了2.6左右。。难受。。等待救援。咕咕。

 #pragma comment(linker,"/STACK:102400000,102400000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define dbg(x) cerr << #x << " = " << x <<endl
#define dbg2(x,y) cerr<< #x <<" = "<< x <<" "<< #y <<" = "<< y <<endl
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,):;}
template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,):;}
template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}
template<typename T>inline T read(T&x){
x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;
while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;
}
const int N=2e5+,INF=0x3f3f3f3f;
int len,n,thxorz;
int A[N];
int anc[N];
inline int get_anc(int x){return anc[x]==x?x:anc[x]=get_anc(anc[x]);}
struct _01trie{
int tr[N*][],maxv[N*],minv[N*],id[N*],tot;
_01trie(){maxv[]=,minv[]=INF;}
inline void Insert(int x,int j){//dbg2(x,j);
int u=;
for(register int i=len,d;~i;--i){
if(!tr[u][d=(x>>i)&])tr[u][d]=++tot;
u=tr[u][d];
}
id[u]=j;
}
void Maintain(int i){//++thxorz;
if(!tr[i][]&&!tr[i][]){maxv[i]=minv[i]=get_anc(id[i]);return;}
if(tr[i][])Maintain(tr[i][]);
if(tr[i][])Maintain(tr[i][]);
maxv[i]=_max(maxv[tr[i][]],maxv[tr[i][]]);
minv[i]=_min(minv[tr[i][]],minv[tr[i][]]);//dbg2(i,tr[i][0]),dbg2(minv[i],maxv[i]);
}
inline void Build(){for(register int i=;i<=n;++i)Insert(A[i],i);}
inline int Query(int x,int j){
int u=,rt=get_anc(j);//dbg2(rt,x);
for(register int i=len,d;~i;--i){//++thxorz;
d=(x>>i)&;//dbg2(d,tr[u][d]),dbg2(maxv[tr[u][d]],minv[tr[u][d]]);
if(tr[u][d]&&(maxv[tr[u][d]]^rt||minv[tr[u][d]]^rt))u=tr[u][d];
else u=tr[u][d^];
}//dbg(id[u]);
return id[u];
}
}T;
int minw[N],minp[N];
inline void Boruvka(){
int k=;ll ans=;
T.Build();
for(register int i=;i<=n;++i)anc[i]=i;
while(k<n-){//dbg("new round");
T.maxv[]=,T.minv[]=INF,T.Maintain();memset(minw,0x7f,sizeof minw);
for(register int i=,tmp;i<=n;++i)tmp=T.Query(A[i],i),MIN(minw[get_anc(i)],A[tmp]^A[i])&&(minp[anc[i]]=tmp);
for(register int i=;i<=n;++i)if(get_anc(i)^get_anc(minp[get_anc(i)]))
ans+=minw[anc[i]],++k,anc[anc[i]]=anc[minp[anc[i]]];//attention the order.
}
printf("%I64d\n",ans);
} int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);
read(n);for(register int i=;i<=n;++i)MAX(len,read(A[i]));
len=__lg(len);
Boruvka();//dbg(thxorz);
return ;
}

最新文章

  1. Tomcat中的Session小结
  2. Sql Server系列:DBCC命令
  3. IOS开发 - TextField 控件详细
  4. vs2015产品密钥
  5. OpenMP求完数
  6. python——有限状态机
  7. C#和Javascript间互转的Xxtea加解密
  8. Tempter of the Bone---hdu1010(dfs+剪枝)
  9. jdk和tomcat环境部署
  10. 【HDOJ】4729 An Easy Problem for Elfness
  11. 【兼容】IE下PNG色差
  12. Verilog-1995 VS Verilog-2001
  13. Oracle 监控索引使用
  14. 数数字(Digit Counting,ACM/ICPC Danang 2007,UVa1225)
  15. iOS之 Auto Layout
  16. CentsOS7无网情况下安装mysql5.7
  17. flume安装配置
  18. Android中将十六进制 颜色代码 转换为int类型数值
  19. [Sublime-Text] Linux下用Sublime-Text3编译输出Java文件
  20. Spring,Struts2,MyBatis,Activiti,Maven,H2,Tomcat集成(二)——Struts2集成

热门文章

  1. CSS - Animate动画
  2. English 邮件
  3. django进阶版1
  4. Docker结合Jenkins构建持续集成环境
  5. Jmeter入门(一)干货吐槽
  6. join函数详解
  7. centos7.4 安装 .net core 2.2
  8. 【原创】Java基础之Nginx缓存
  9. LeetCode:181.超过经理收入的员工
  10. 帝国cms常用标签