[FJSC2014]异或之

【题目描述】

　　给定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

【样例输出】

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。

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<ctime>

 int main()

 {

     freopen("xorit.in","w",stdout);

     srand(time());

     int n=,m=,mod=<<;mod--;

     printf("%d %d\n",n,m);

     for(int i=;i<=n;i++)printf("%d ",rand());

 }

Data Maker

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 int t[],d,n,k,a[],tmp;

 int main()

 {

     scanf("%d%d",&n,&k);int i,j,l;

     memset(t,,sizeof(t));

     for(d=;d<k;d<<=);

     for(i=;i<=n;i++)scanf("%d",&a[i]);

     std::sort(a+,a++n);

     for(i=;i<=n;i++)

     for(j=i-;j;j--)t[++tmp]=a[i]^a[j];

     std::sort(t+,t++tmp);

     for(i=;i<=k;i++)printf("%d ",t[i]);

 }

暴力

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 int t[],d,n,k,a[],cnt,tmp,now;

 int main()

 {

     scanf("%d%d",&n,&k);int i,j,l,o;k++;

     for(d=;d<k;d<<=);

     for(i=;i<=n;i++)scanf("%d",&a[i]);

     std::sort(a+,a++n);

     for(i=;i<=n;i++)

     for(j=i-;j;j--)

     {

         tmp=a[i]^a[j];now=;

         for(l=k+d-;l;l>>=)now<t[l]?now=t[l]:;

         if(now==&&cnt==k)break;

         if(cnt<k)

         {

             if(now<tmp)now=tmp;

             for(t[l=d+cnt]=tmp,cnt++,l>>=;l;l>>=)

             {

                 tmp=t[l<<]>t[l<<|]?t[l<<]:t[l<<|];

                 t[l]=tmp;

             }

         }

         else

         {

             if(tmp>=now&&a[i]-a[j]>now)break;

             if(tmp<now)

             {

                 for(o=;o<d;t[o<<|]==now?o=o<<|:o<<=);

                 if(now<tmp)now=tmp;

                 for(t[o]=tmp,o>>=;o;o>>=)

                 {

                     tmp=t[o<<]>t[o<<|]?t[o<<]:t[o<<|];

                     t[o]=tmp;

                 }

             }

         }

     }

     std::sort(t+d,t+d+k);k--;

     for(i=d;i<d+k;i++)printf("%d ",t[i]);

 }

std

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

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

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

巴特西

[FJSC2014]异或之

最新文章

热门文章