XOR Clique（按位异或）

XOR Clique（按位异或）：

传送门：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4057

准备：异或：参加运算的两个数据，按二进制位进行“异或”运算。

运算规则：0^0=0, 0^1=1， 1^0=1, 1^1=0；

即：参加运算的两个对象，如果两个相应位为“异”，则该位结果为1，否则为0；

题意：

有一个a1到an的序列，问能不能找到一个长度为S的序列，对于在S里面的任意的i,j满足ai⊕aj<min(ai,aj) 这个条件，两个数的异或小于这两个数的最小值，要求输出S的最大长度。

解题思路：

多找几组数据就会发现若想异或结果小于最小值，只需要两个数二进制形式位数相同，即二进制前面第一位都为1，进行异或运算后就会第一位变为0，自然比原来两个数都小所以只需要将序列中所有数的二进制形式位数进行统计即可（学长说二进制运算一般找最高位是常用的方法）

以下为AC代码：

 /* */

 # include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int INF = 0x3f3f3f3f;

 const int MAXN = ;///用来记录路最高位的值，2的30次方就可以达到1e9

 int a[MAXN];///用来记录某一最高位所包含的数有几个

 int bt(int x)

 {

     int cnt = ;

     while( x )

     {

         x >>= ;///x除以2，10进制化2进制运算

         cnt++;

     }

     return cnt;///返回最高位

 }

 int main()

 {

     int T

     cin >> T;

     while( T-- )

     {

         memset(a, , sizeof(a));

         int n;

         scanf("%d", &n);

         int ans = ;

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

         {

             int e;

             scanf("%d", &e);

             ans = max(ans, ++a[bt(e)]);///找出最高位为bt(e)的值的个数，找出哪一最高位对应的数最多，极为最长子集包含的数的个数

         }

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

     }

     return ;

 }

以下为超时代码：

 #include<bits/stdc++.h>

 using namespace std;

 int main()

 {

     int t;

     scanf("%d", &t);

     while (t--)

     {

         int n;

         int a[]={};///相当于建了一个桶来标记

         scanf("%d", &n);

         int k=;

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

         {

             int x,sum=;

             scanf("%d", &x);

             while(x)

             {

                 sum++;

                 x/=;

             }

             a[sum]++;

         }

        for(int i=;i<;i++)///这样遍历，无用循环做的次数太多了，所以超时

        {

            k=max(k,a[i]);

        }

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

     }

     return ;

 }

巴特西

XOR Clique（按位异或）

最新文章

热门文章