2019 Multi-University Training Contest 9 Rikka with Stable Marriage —— 字典树

本文主要是介绍2019 Multi-University Training Contest 9 Rikka with Stable Marriage —— 字典树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

给你a,b两个数组，让他们两辆匹配，ai与bj是稳定的，当且仅当不存在ak与bl使得ai^bl>ai^bj&&ak^bj>ak^bl。问你所有稳定匹配中ai^bj之和最大的是多少

题解：

好像和6625是同一道题目（羞愧）
只需要将01,10的路劲选择放在前面即可，其它地方不变
This way

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
int tr[2][N*31][2],num[2][N*31];
int cnt[2];
void update(int x,int u)
{int rt=0;for(int i=30;i>=0;i--){if(!tr[u][rt][((x>>i)&1)])tr[u][rt][((x>>i)&1)]=++cnt[u];rt=tr[u][rt][((x>>i)&1)];num[u][rt]++;}
}
int query()
{int rt0=0,rt1=0,ans=0;for(int i=30;i>=0;i--){if(tr[0][rt0][0]&&tr[1][rt1][1]&&num[0][tr[0][rt0][0]]&&num[1][tr[1][rt1][1]])rt0=tr[0][rt0][0],rt1=tr[1][rt1][1],num[0][rt0]--,num[1][rt1]--,ans|=(1<<i);else if(tr[0][rt0][1]&&tr[1][rt1][0]&&num[0][tr[0][rt0][1]]&&num[1][tr[1][rt1][0]])rt0=tr[0][rt0][1],rt1=tr[1][rt1][0],num[0][rt0]--,num[1][rt1]--,ans|=(1<<i);else if(tr[0][rt0][1]&&tr[1][rt1][1]&&num[0][tr[0][rt0][1]]&&num[1][tr[1][rt1][1]])rt0=tr[0][rt0][1],rt1=tr[1][rt1][1],num[0][rt0]--,num[1][rt1]--;else if(tr[0][rt0][0]&&tr[1][rt1][0]&&num[0][tr[0][rt0][0]]&&num[1][tr[1][rt1][0]])rt0=tr[0][rt0][0],rt1=tr[1][rt1][0],num[0][rt0]--,num[1][rt1]--;}return ans;
}
int main()
{int t;scanf("%d",&t);while(t--){int n,x;cnt[0]=cnt[1]=0;scanf("%d",&n);for(int i=0;i<=n*31;i++){tr[0][i][0]=tr[0][i][1]=tr[1][i][0]=tr[1][i][1]=0;num[0][i]=num[1][i]=0;}for(int i=1;i<=n;i++)scanf("%d",&x),update(x,0);for(int i=1;i<=n;i++)scanf("%d",&x),update(x,1);ll ans=0;for(int i=1;i<=n;i++)ans+=(ll)query();printf("%lld\n",ans);}return 0;
}

这篇关于2019 Multi-University Training Contest 9 Rikka with Stable Marriage —— 字典树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---