Rock and Lever

本文主要是介绍Rock and Lever，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题意：

找出数列中满足，ai & aj >= ai ^ aj 的 (i,j)的数量，i<j

由样例发现，当ai 与 aj 的最高位一样时，不等式就成立

故，记录数的最高位的数目，假设一个最高位的数目为x，则能选,C(n,2)种

得到一个数的二进制的最高位，不断右移即可。

处理组合数即可。又：C(n,2)=(n/2)*C(n-1,1)=n*(n-1)/2.   O(n)递推即可

#include<iostream>
#include<map>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 1e1;
ll C[maxn];//只保存C(n,2)即可
int a[maxn];
int solve(int x)//返回x的最高位1
{
    int ans = 0;
    while (x)
    {
        ++ans; x >>= 1;
    }
    return ans;
}
void init()
{
    for (ll i = 1; i < maxn; i++)
    {
        C[i] = i * (i - 1) / 2;
    }
    return;
}
int main()
{
    init();
    int t; cin >> t;
    while (t--)
    {
        int n; cin >> n;
        map<int, int>m;
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
            ++m[solve(a[i])];
        }
        ll ans = 0;
        for (const auto& i : m)
        {
            ans += C[i.second];
        }
        cout << ans << "\n";
    }
    return 0;
}

这篇关于Rock and Lever的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！