链接
边权可为0就排序建一条链子。 但是边权不为0 除了第一个有0的不行。 x连向上一个比他小的数。 期间判断有无解。
#include <bits/stdc++.h> #define ll long long using namespace std; const int _=2e5+7; int read() { int x=0,f=1;char s=getchar(); for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1; for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0'; return x*f; } int n,S; struct edge{int a,b,c;}; struct node { int id,val; bool operator < (const node &b) const { return val==b.val?id<b.id:val<b.val; } }a[_]; std::vector<edge> ans; int main() { // freopen("a.in","r",stdin); n=read(),S=read(); for(int i=1;i<=n;++i) a[i].val=read(),a[i].id=i; sort(a+1,a+1+n); for(int i=2;i<=n;++i) if(!a[i].val) return puts("-1"),0; for(int i=2;i<=n;) { int las=i; if(a[i].val-a[i-1].val>S) return puts("-1"),0; while(a[i].val==a[las].val) ans.push_back(edge{a[las-1].id,a[i].id,a[i].val-a[las-1].val}),++i; } printf("%d\n",(int)ans.size()); for(auto x:ans) printf("%d %d %d\n", x.a,x.b,x.c); return 0; }和XOR-MST差不多，就应该早做掉这个ZR题，要不就不用想呢么久了。答案就是XOR-MST上的最大的那条边。 感性：字数内的也是个完全图。因为边权都比外边的那条边小，随便连，两颗子树就可以变成任意形态的链子了。枚举端点就行了。
#include <bits/stdc++.h> #define ll long long using namespace std; const int _=1e6+7; ll read() { ll x=0,f=1;char s=getchar(); for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1; for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0'; return x*f; } int n,ch[_*60][2],cnt=1,rt,dsr; ll a[_],ans; void insert(ll x) { int p=1; for(int i=59;i>=0;--i) { bool k=x&(1LL<<i); if(!ch[p][k]) ch[p][k]=++cnt; p=ch[p][k]; } } ll query(ll x) { int p=rt; ll ans=0; for(int i=dsr;i>=0;--i) { bool k=x&(1LL<<i); if(ch[p][k]) p=ch[p][k]; else p=ch[p][!k],ans|=1LL<<i; } return ans; } int main() { // freopen("b.in","r",stdin); n=read(); for(int i=1;i<=n;++i) a[i]=read(),insert(a[i]); rt=1,dsr=59; while((!ch[rt][0]||!ch[rt][1])&&dsr>=0) rt=ch[rt][0]|ch[rt][1],dsr--; if(dsr<0) return puts("0"),0; ch[rt][1]=0; ans=1LL<<60; for(int i=1;i<=n;++i) if(a[i]&(1LL<<dsr)) ans=min(ans,query(a[i])); cout<<ans<<"\n"; return 0; }没大看题，貌似很恶心的亚子。
转载于:https://www.cnblogs.com/dsrdsr/p/11379882.html
相关资源：JAVA上百实例源码以及开源项目