2018-03-16
异或的性质
- a ⊕ a = 0
- a ⊕ b = b ⊕ a
- a ⊕b ⊕ c = a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c;
- d = a ⊕ b ⊕ c 可以推出 a = d ⊕ b ⊕ c.
- a ⊕ b ⊕ a = b.
6.若x是二进制数0101，y是二进制数1011；
则x⊕y=1110
有上述性质，对于区间异或和要知道如下性质：
XOR[l,r] = XOR[1,l-1] ^ XOR[1,r]
异或的知识还有很多有趣的解释和应用，详情可以移步知乎。
(CodeForces - 948D)Perfect Security
题意：先给你一串数字a[n]，然后再给你一串数字b[n]，让你任意排列b[n]，使得a[i]^b[i]的值的输出字典序最小。
思想：想办法让一个数字k异或后的结果最小，其实就是想办法让该数字二进制高位变为0，而由上面异或的性质可以知道，其实就是在另一串数字中找到一个数字d，使得数字d的二进制与数字k的二进制在高位上尽可能多得相同，于是就有了两个方法。
方法一：暴力寻找（？？）
for(ll i=1<<30;i;i>>=1){
ans+=(i&x);
multiset<ll>::iterator it=S.lower_bound(ans);
if(it==S.end() || *it>=ans+i){
ans^=i;
}
}
S.erase(S.find(ans));
从x的高位找，如果a[n]中的数字最大值还不能达到高位，或者大于x的最小数字在二进制中甚至比x还高一位，那么异或取消。
还有一个有趣的一点就是：怎么确认我找到的ans一定是在b[n]呢——其实关键点就在lower_bound这里，举个例子就能理解。
//#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<string>
#include<math.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<stdlib.h>
#define lowbit(x) (x&(-x))
#define ll long long
#define PI acos(-1)
#define FILEIN freopen("in.txt","r",stdin)
#define FILEOUT freopen("out.txt","w",stdout)
#define CLR(x) memset(x,0,sizeof(x))
#define mem(a,x) memset(a,x,sizeof(a))
#define debug printf("!!");
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fll;
using namespace std;
//const double eps = 1e-6;
const ll mod = 1e9+7;
const int maxn = 300000+100;
const int maxe = 1e6+100;
using namespace std;
multiset<ll>S;
ll a[maxn];
void Solve()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%lld",&a[i]);
for(int i=0;i<n;i++){
ll x;
scanf("%lld",&x);
S.insert(x);
}
for(int i=0;i<n;i++){
if(i!=0) printf(" ");
ll ans=0; ll x=a[i];
for(ll i=1<<30;i;i>>=1){
ans+=(i&x);
multiset<ll>::iterator it=S.lower_bound(ans);
if(it==S.end() || *it>=ans+i){
ans^=i;
}
}
S.erase(S.find(ans));
printf("%lld",x^ans);
}
}
int main()
{
//FILEIN
//FILEOUT
//std::ios::sync_with_stdio(false);
int Case=1,cases;
//scanf("%d", &Case); cases=Case;
while(Case--){
//printf("Case #%d:",cases-Case);
Solve();
}
return 0;
}
方法二：常规01字典树。O(n*32(字典树深度))
//#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<string>
#include<math.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<stdlib.h>
#define lowbit(x) (x&(-x))
#define ll long long
#define PI acos(-1)
#define FILEIN freopen("in.txt","r",stdin)
#define FILEOUT freopen("out.txt","w",stdout)
#define CLR(x) memset(x,0,sizeof(x))
#define mem(a,x) memset(a,x,sizeof(a))
#define debug printf("!!");
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fll;
using namespace std;
//const double eps = 1e-6;
const ll mod = 1e9+7;
const int maxn = 9e6+100;
const int maxe = 1e6+100;
using namespace std;
struct node{
int nex[2],num;
}trie[maxn];
int tot=1;
int num[maxn],a[maxn],b[maxn];
void Insert(int x,int id){
int rt=0;
for(int i=30;i>=0;i--){
int t=((x&(1<<i))!=0);
if(!trie[rt].nex[t]) trie[rt].nex[t]=tot++;
rt=trie[rt].nex[t];
trie[rt].num++;
}
num[rt]=id;
}
void del(int x){
int rt=0;
for(int i=30;i>=0;i--){
int t=((x&(1<<i))!=0);
rt=trie[rt].nex[t];
trie[rt].num--;
}
}
int Cal(int x){
int rt=0;
for(int i=30;i>=0;i--){
int t=((x&(1<<i))!=0);
if(trie[rt].nex[t] && trie[trie[rt].nex[t]].num) rt=trie[rt].nex[t];
else rt=trie[rt].nex[t^1]; //各种异或用法真的精彩
}
del(b[num[rt]]);
return b[num[rt]]^x;
}
void Solve()
{
int n;
scanf("%d",&n);
CLR(trie);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
scanf("%d",&b[i]);
Insert(b[i],i);
}
for(int i=1;i<=n;i++){
printf("%d ",Cal(a[i]));
}
}
int main()
{
//FILEIN
//FILEOUT
//std::ios::sync_with_stdio(false);
int Case=1,cases;
//scanf("%d", &Case); cases=Case;
while(Case--){
//printf("Case #%d:",cases-Case);
Solve();
}
return 0;
}
