A.
首先建一棵01trie。每一个节点的子树都代表一个集合,然后显然在左儿子和右儿子,即相邻的集合连边费用最少(遵循kruskal.)
就完了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 100500 #define inf 2147483646 using namespace std; long long n,w[maxn],ls[maxn*15],rs[maxn*15],size[maxn*15],tot=0,ans=0,root,mn; void insert(long long &now,long long bit,long long x) { if (!now) now=++tot;size[now]++; if (bit==-1) return; long long nb=x&(1<<bit); if (!nb) insert(ls[now],bit-1,x); else insert(rs[now],bit-1,x); } long long dfs3(long long now,long long bit,long long num) { if (bit==-1) return 0; long long nb=num&(1<<bit); if (!nb) { if (ls[now]) return dfs3(ls[now],bit-1,num); else return dfs3(rs[now],bit-1,num)+(1<<bit); } else { if (rs[now]) return dfs3(rs[now],bit-1,num); else return dfs3(ls[now],bit-1,num)+(1<<bit); } } void dfs2(long long now,long long bit,long long num,long long pos,long long nx,long long pb) { if (!now) return; if (bit==-1) { mn=min(mn,dfs3(pos,pb,num)+nx); return; } dfs2(ls[now],bit-1,num<<1,pos,nx,pb); dfs2(rs[now],bit-1,num<<1|1,pos,nx,pb); return; } void dfs1(long long now,long long bit,long long num) { if ((bit==-1) || (!now)) return; dfs1(ls[now],bit-1,num<<1); dfs1(rs[now],bit-1,num<<1|1); if ((!ls[now]) || (!rs[now])) return; if (size[ls[now]]<=size[rs[now]]) {mn=inf;dfs2(ls[now],bit-1,num<<1,rs[now],1<<bit,bit-1);ans+=mn;} else {mn=inf;dfs2(rs[now],bit-1,num<<1|1,ls[now],1<<bit,bit-1);ans+=mn;} return; } int main() { scanf("%lld",&n); for (long long i=1;i<=n;i++) { scanf("%lld",&w[i]); insert(root,30,w[i]); } dfs1(root,30,0); printf("%lld\n",ans); return 0; }
B.
直接枚举gcd再枚举倍数连边,复杂度调和级数nlogn。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 100500 using namespace std; int n,father[maxn]; int ans=0; int getfather(int x) { if (x!=father[x]) father[x]=getfather(father[x]); return father[x]; } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) father[i]=i; for (int d=n/2;d>=1;d--) for (int i=2;i*d<=n;i++) { int x=(i-1)*d,y=i*d,w=d; int f1=getfather(x),f2=getfather(y); if (f1!=f2) {father[f1]=f2;ans+=w;} } printf("%d\n",ans); return 0; }
C.
三角剖分还要nlogn?。。。弃坑。