首页 > 代码库 > BZOJ3689: 异或之
BZOJ3689: 异或之
题解：
首先知道一点trie不仅可以求与某个数异或的最大值.最小值，还能求第k大值，不能再神，orz！！！多添加一个size域即可。
然后本题做法
类似于超级钢琴。
我们先求出每个a[i]的第二异或最小值，然后放进堆里（第一是和自己）
然后我们往外取最小值，每次取出一个之后a[i]的第k小异或值就压入a[i]的第k+1小异或值。
正确性显然。输出的时候注意重复的。
代码：写pair套pair感觉很舒爽
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 100000+514 #define maxm 4000000+515 #define eps 1e-1016 #define ll long long17 #define for0(i,n) for(int i=0;i<=(n);i++)18 #define for1(i,n) for(int i=1;i<=(n);i++)19 #define for2(i,x,y) for(int i=(x);i<=(y);i++)20 #define for3(i,x,y) for(int i=(x);i>=(y);i--)21 #define for4(i,x) for(int i=head[x],y;i;i=e[i].next)22 #define mod 100000000723 using namespace std;24 inline int read()25 {26 int x=0,f=1;char ch=getchar();27 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}28 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}29 return x*f;30 }31 typedef pair<int,pair<int,int> > pa;32 priority_queue<pa,vector<pa>,greater<pa> >q;33 int n,m,tot,a[maxn],t[maxm][2],s[maxm];34 inline void add(int x)35 {36 int now=1;s[now]++;37 for3(i,30,0)38 {39 int j=x>>i&1;40 if(!t[now][j])t[now][j]=++tot;41 now=t[now][j];42 s[now]++;43 }44 }45 inline int query(int x,int k)46 {47 int now=1,ans=0;48 for3(i,30,0)49 {50 int j=x>>i&1;51 if(k<=s[t[now][j]])now=t[now][j];52 else53 {54 k-=s[t[now][j]];55 ans|=1<<i;56 now=t[now][j^1];57 }58 }59 return ans;60 }61 int main()62 {63 freopen("input.txt","r",stdin);64 freopen("output.txt","w",stdout);65 n=read();m=read();tot=1;66 for1(i,n)add(a[i]=read());67 for1(i,n)q.push(make_pair(query(a[i],2),make_pair(a[i],2)));68 for1(i,2*m)69 {70 int x=q.top().first,y=q.top().second.first,k=q.top().second.second;71 if(i&1){if(i!=1)printf(" ");printf("%d",x);}72 q.pop();73 q.push(make_pair(query(y,k+1),make_pair(y,k+1)));74 }75 return 0;76 }
T_T没想到改成一个pair居然还慢了
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 100000+514 #define maxm 4000000+515 #define eps 1e-1016 #define ll long long17 #define for0(i,n) for(int i=0;i<=(n);i++)18 #define for1(i,n) for(int i=1;i<=(n);i++)19 #define for2(i,x,y) for(int i=(x);i<=(y);i++)20 #define for3(i,x,y) for(int i=(x);i>=(y);i--)21 #define for4(i,x) for(int i=head[x],y;i;i=e[i].next)22 #define mod 100000000723 using namespace std;24 inline int read()25 {26 int x=0,f=1;char ch=getchar();27 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}28 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}29 return x*f;30 }31 typedef pair<int,int>pa;32 priority_queue<pa,vector<pa>,greater<pa> >q;33 int n,m,tot,a[maxn],b[maxn],t[maxm][2],s[maxm];34 inline void add(int x)35 {36 int now=1;s[now]++;37 for3(i,30,0)38 {39 int j=x>>i&1;40 if(!t[now][j])t[now][j]=++tot;41 now=t[now][j];42 s[now]++;43 }44 }45 inline int query(int x,int k)46 {47 int now=1,ans=0;48 for3(i,30,0)49 {50 int j=x>>i&1;51 if(k<=s[t[now][j]])now=t[now][j];52 else53 {54 k-=s[t[now][j]];55 ans|=1<<i;56 now=t[now][j^1];57 }58 }59 return ans;60 }61 int main()62 {63 freopen("input.txt","r",stdin);64 freopen("output.txt","w",stdout);65 n=read();m=read();tot=1;66 for1(i,n)add(a[i]=read());67 for1(i,n)q.push(make_pair(query(a[i],b[i]=2),i));68 for1(i,2*m)69 {70 int x=q.top().first,y=q.top().second;71 if(i&1){if(i!=1)printf(" ");printf("%d",x);}72 q.pop();73 q.push(make_pair(query(a[y],++b[y]),y));74 }75 return 0;76 }
3689: 异或之
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 63 Solved: 34
[Submit][Status]
Description
给定n个非负整数A[1], A[2], ……, A[n]。
对于每对(i, j)满足1 <= i < j <= n，得到一个新的数A[i] xor A[j]，这样共有n*(n-1)/2个新的数。求这些数（不包含A[i]）中前k小的数。
注：xor对应于pascal中的“xor”，C++中的“^”。
Input
第一行2个正整数 n,k，如题所述。
以下n行，每行一个非负整数表示A[i]。
Output
共一行k个数，表示前k小的数。
BZOJ3689: 异或之
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。