题解
位运算简单理解:
and(&):有假则假;
or(|):有真则真;
不妨从输入样例入手,看看能有什么发现。
举几个例子:
1(001) & 2(010) == 3(011)
1(001) | 2(010) == 0(000)
2(010) & 3(011) == 3(011)
2(010) | 3(011) == 2(010)
3(011) & 4(100) == 7(111)
3(011) | 4(100) == 0(000)
4(100) & 5(101) == 5(101)
4(100) | 5(101) == 4(100)
先观察每组等式两边十进制数和的情况,我们得出第一个结论:
a + b == a & b + a | b
再观察每组等式两边二进制数每一位的情况,我们得出第二个结论:
a、b二进制中每一位上0、1的个数==a & b、a | b二进制中每一位上0、1的个数
解释一下,以下面这两个数为例。
3(011) & 4(100) == 7(111)
3(011) | 4(100) == 0(000)
3(011) 4(100) vs 7(111) 0(000)
然后设计程序就很轻松了。
首先,用类似桶的思想将每一位上\(1\)的个数存下来。
然后,为了使最终生成的数尽可能大,我们从最高位开始遍历。遇到一位存在\(1\)的,我们便由那一位接着向低位遍历,若该位存在\(1\)则为当前生成数增加\(1<<(j-1)\)(\(j\)是遍历到的位),并消耗一个当前位上\(1\)的数量。由此我们可以生成一个数。
最后,求所有生成数的平方和即可。
AC代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=100005;
int n;
int wei[200];
ll num[1000000];//num存了所有生成的数,必须开得足够大
ll ans;
int main()
{
//freopen("wei.in","r",stdin);
//freopen("wei.out","w",stdout);
scanf("%d",&n);
for(int i=1,x,y,cnt;i<=n;i++)
{
cnt=0;
scanf("%d",&x);
y=x;
while(y!=0)
{
wei[++cnt]+=y%2;//wei[i]存第i位上1的个数和
y>>=1;
}
}
int cnt=0;
for(int i=20;i>=1;i--)
while(wei[i]!=0)
{
cnt++;
for(int j=i;j>=1;j--)
if(wei[j]!=0)
{
num[cnt]+=1<<(j-1);//为生成数作贡献
wei[j]--;//消耗当前位上的1
}
}
for(int i=1;i<=cnt;i++)
ans+=1ll*num[i]*num[i];
printf("%lld",ans);
return 0;
}
标签:运算,记录,位位,wei,010,011,int,100,include
From: https://www.cnblogs.com/fish4174/p/16773316.html