codeforces（E. XOR Inverse） 字典树（异或）

原题链接

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
#include 
#define pb push_back
#define ll long long
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
inline int read() {char c = getchar(); int x = 0, f = 1;while (c < '0' || c > '9') {if (c == '-')f = -1; c = getchar();}while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}return x * f;
}
using namespace std;int n;
int a[300005];
int tree[9000005][2];
int s[50],vis[9000005];
ll z[50],f[50],c[50],tot;
ll apow(ll a,ll b)
{ll s=1;for(int i=1;i<=b;i++){s*=2;}return s;
}
void build(int x)
{int tmp=a[x];for(int i=29;i>=0;i--){s[i]=(tmp%2);tmp/=2;}int p=0;vis[p]++;for(int i=0;i<30;i++){int c=s[i];if(c==0){if(tree[p][1]!=0){f[i]+=vis[tree[p][1]];}}else{if(tree[p][0]!=0){z[i]+=vis[tree[p][0]];}}if(tree[p][c]==0){tree[p][c]=++tot;}p=tree[p][c];vis[p]++;}
}
int main()
{IOScin>>n;for(int i=1;i<=n;i++){cin>>a[i];build(i);}ll ans=0,base=0,all=0;for(int i=0;i<30;i++){if(f[i]>z[i]){c[i]=1;all+=z[i];}else{all+=f[i];}}for(int i=29;i>=0;i--){if(c[i]==0){base++;continue;}else{ans+=apow(2,base);base++;}}cout<<all<<" "<<ans<<'\n';return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！