注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3689][FJSC2014]异或之  

2014-07-20 20:54:14|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

【题目描述】

  给定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++中的“^”。

【输入格式】

  第一行2个正整数 n,k,如题所述。

  以下n行,每行一个非负整数表示A[i]。

【输出格式】

  共一行k个数,表示前k小的数。

【样例输入】

4 5

1

1

3

4

【样例输出】

0 2 2 5 5

【样例解释】

  1 xor 1 = 0 (A[1] xor A[2])

  1 xor 3 = 2 (A[1] xor A[3])

  1 xor 4 = 5 (A[1] xor A[4])

  1 xor 3 = 2 (A[2] xor A[3])

  1 xor 4 = 5 (A[2] xor A[4])

  3 xor 4 = 7 (A[3] xor A[4])

  前5小的数:0 2 2 5 5

【数据范围】

  第一个数据点,n <= 1000; 

  第二个数据点,k = 1;

  对于40%的数据,n <= 10000; k <= 10;

  对于60%的数据,n <= 20000;

  对于100%的数据,2 <= n <= 100000; 1 <= k <= min{250000, n*(n-1)/2};0 <= A[i] < 2^31

 

Solution

  由于出题人数据是随机生成的就卡不掉我的暴力骗分啦~不过我是构了一组。

  很明显,a-b<=a^b<=a+b

  先对A[]排序,选取k个可能成为答案的数,用堆或者线段树维护修改和查询。当插进去的数比当前堆中的最大数还大的话就break。

/*Data Maker*/

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
int main()
{
freopen("xorit.in","w",stdout);
srand(time(0));
int n=1000,m=2500,mod=1<<30;mod--;
printf("%d %d\n",n,m);
for(int i=1;i<=n;i++)printf("%d ",rand());
}

/*暴力*/

#include<cstdio>
#include<algorithm>
#include<cstring>
int t[1000010],d,n,k,a[100010],tmp;
int main()
{
scanf("%d%d",&n,&k);int i,j,l;
memset(t,127,sizeof(t));
for(d=1;d<k;d<<=1);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
std::sort(a+1,a+1+n);
for(i=2;i<=n;i++)
for(j=i-1;j;j--)t[++tmp]=a[i]^a[j];
std::sort(t+1,t+1+tmp);
for(i=1;i<=k;i++)printf("%d ",t[i]);
}

/*std*/

#include<cstdio>
#include<algorithm>
#include<cstring>
int t[524288],d,n,k,a[100010],cnt,tmp,now;
int main()
{
scanf("%d%d",&n,&k);int i,j,l,o;k++;
for(d=1;d<k;d<<=1);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
std::sort(a+1,a+1+n);
for(i=2;i<=n;i++)
for(j=i-1;j;j--)
{
tmp=a[i]^a[j];now=0;
for(l=k+d-2;l;l>>=1)now<t[l]?now=t[l]:1;
if(now==0&&cnt==k)break;
if(cnt<k)
{
if(now<tmp)now=tmp;
for(t[l=d+cnt]=tmp,cnt++,l>>=1;l;l>>=1)
{
tmp=t[l<<1]>t[l<<1|1]?t[l<<1]:t[l<<1|1];
t[l]=tmp;
}
}
else
{
if(tmp>=now&&a[i]-a[j]>now)break;
if(tmp<now)
{
for(o=1;o<d;t[o<<1|1]==now?o=o<<1|1:o<<=1);
if(now<tmp)now=tmp;
for(t[o]=tmp,o>>=1;o;o>>=1)
{
tmp=t[o<<1]>t[o<<1|1]?t[o<<1]:t[o<<1|1];
t[o]=tmp;
}
}
}
}
std::sort(t+d,t+d+k);k--;
for(i=d;i<d+k;i++)printf("%d ",t[i]);
}

另外还有一种二进制分组的做法。考虑在二进制中前k位相同的数,k+1位对答案的贡献为cnt[0]*cnt[1],cnt[i]表示k+1位为i的数。

于是我们可以找到第k小的答案范围,然后暴力就行了。复杂度O(nlogn)

还有一种可持久化Trie树的做法--详见Noi超级钢琴并Orz龙犇

  评论这张
 
阅读(69)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018