位运算 ZOJ 3870 Team Formation

题目传送门

 /*
题意:找出符合 A^B > max (A, B) 的组数;
位运算:异或的性质,1^1=0, 1^0=1, 0^1=1, 0^0=0;与的性质:1^1=1, 1^0=0, 0^1=0, 0^0=0;
假设A < B,一定要满足B的最高位对应A的值是0,这样才可能>B(即0^1=1);
然后比赛时假设A的极限是类似0111111的情况,最后假设有误;
题解是先把每个数最高位(1)的位置统计个数,1<<4 的意思是 000010000;
只要与为0,表示最高位p位置的所有数字和当前a[i]异或一定满足,累加ans; 位运算不熟悉, '⊕'还是别人告诉我是异或的;
详细解释:http://blog.csdn.net/LYHVOYAGE/article/details/45285731
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std; const int MAXN = 1e5 + ;
const int INF = 0x3f3f3f3f;
int a[MAXN];
int bit[]; void solve(int x)
{
int p = ;
while (p >= )
{
if (x & (<<p))
{
bit[p]++; return ;
}
p--;
} return ;
} int main(void) //ZOJ 3870 Team Formation
{
//freopen ("B.in", "r", stdin); int t, n;
scanf ("%d", &t);
while (t--)
{
memset (bit, , sizeof (bit));
scanf ("%d", &n);
for (int i=; i<=n; ++i)
{
scanf ("%d", &a[i]); solve (a[i]);
} long long ans = ;
for (int i=; i<=n; ++i)
{
int p = ;
while (p >= )
{
if (a[i] & (<<p)) break;
p--;
}
while (p >= )
{
if (!(a[i] & (<<p))) ans += bit[p];
p--;
}
} printf ("%lld\n", ans);
} return ;
}
上一篇:CentOS 7 下使用yum安装MySQL5.7.20 最简单图文详解


下一篇:H2O是开源基于大数据的机器学习库包