over 3 years ago

一道一题多解的典型题目

自己的做法

    按二进制位分层,很容易发现越靠底部的数xor后所得的数越小。所以可以分层看分到哪一层时所得的数>k,在这一层上sort暴力。一开始想到之后没敢写,因为觉得复杂度会有问题,后来看了hzwer神犇的题解。发现了一个证明:对于第i+1层得到的数<k,则对于第i层的数不超过2k。所以复杂度是30n+klogk
写的时候要注意一点点细节,比如说一开始即相等的情况,以及枚举每个数要按i+1位的1|0分组。详见代码
可能是因为数据没有卡,所以这种做法跑的特别快。。目前是bzoj rank1

据说是标解

    类似noi2005超级钢琴的思路。用堆来筛选最值。每个节点为第i号点和[l,r]中的值j xor的最小值。注意一开始i号点只需要在[i+1,n]里面筛选。每次取出最小值计入答案,将区间拆分成[l,j-1] [j+1,r]加入堆,查询的话用可持久化trie。因为总共会加入n+2k个节点,所以复杂度是klogk。不过据说很慢。。

gty的做法

    同样用堆维护,不过每个点为第i号点和与其xor第j大的结果值。每次取出最小,插入第j+1大。查询第j大只需要在全局trie中用类似主席树查询的方法查询第j+1大即可【因为最小的是自己xor自己】。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=100001;
const int maxm=250001;
const int MAXM=600001;
const int maxbit=31;
int a[maxn],b[maxn],ans[maxm],order[MAXM];
int n,k,on=0,ansn=0;
int read()
{
    char c=getchar();int bj=1,result=0;
    while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
    if(c=='-') bj=-1,c=getchar();
    while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
    return result*bj; 
}
void calc(int left,int right,int bit)
{
    if (bit==1) 
    {
        on+=(right-left)*(right-left);
        return;
    }
    int mid,i,j;
    for (mid=left;mid<=right;mid++)
        if (a[mid]>>(bit-2) &1) break;
    for (i=left;i<=mid-1;i++)
        for (j=mid;j<=right;j++)
            order[++on]=a[i]^a[j];
}
int main()
{
    int i,j;
    n=read();k=read();
    for (i=1;i<=n;i++) a[i]=read();
    sort(a+1,a+n+1);
    for (i=1;i<=n;i++) b[i]=a[i];
    for (int bit=1;bit<=maxbit;bit++)//注意边界,因为每次做的是bit-1那一层(在bit=1时做的是相等的数)所以maxbit是31而不是30 
 {
        on=0;
        for (i=1;i<=n;i=j+1)
        {
            j=i;
            while (j<n&&b[j]==b[j+1]) j++;
            if (i!=j) calc(i,j,bit);
        }
        sort(order+1,order+on+1);
        for (i=1;i<=min(on,k);i++) ans[++ansn]=order[i];
        k-=on;
        if (k<=0) break;
        for (i=1;i<=n;i++) b[i]>>=1;
    }
    for (i=1;i<=ansn;i++) printf("%d ",ans[i]);
}
← 三维凸包 【bzoj1964&hdu4266】 【bzoj3052】【WC2013】【树上莫队】糖果公园 →
 
comments powered by Disqus