「NOIP模拟赛」求和式

2014年4月5日2,5640

题目描述

作为本场考试的第一题，你的任务十分简单：

给定长度为n的序列A[i]，求所有A[i] xor A[j] (i<j)的值之和

输入

第一行一个整数N

接下来N行，第i行为A[i]

输出

所需的值

样例输入

样例输出

样例解释

7 xor 3+3 xor 5+7 xor 5 = 4+6+2 = 12

数据范围

对于40%的数据，N<=5000

对于100%的数据，N<=1000000

题解

转为二进制

一位一位处理

统计第i位所有数字0或1的个数，记为a[i]和b[i]

则对于答案的贡献为a[i]*b[i]*1<<(i-1)

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define ll long long
using namespace std;
int n,f0[32],f1[32];
ll ans;
void get(int x)
{
	int k=1;
	while(x)
	{
		if(x&1)f1[k]++;
		else f0[k]++;
		x>>=1;
		k++;
	}
	for(k=k;k<=31;k++)f0[k]++;
}
int main()
{
	//freopen("x3.in","r",stdin);
	//freopen("x3.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int x;scanf("%d",&x);
		get(x);
	}
	for(int i=1;i<=31;i++)
	   ans+=(ll)(1<<(i-1))*f0[i]*f1[i];
    printf("%I64d",ans);
	return 0;
}

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cstdio>

#define ll long long

using namespace std;

int n,f0[32],f1[32];

ll ans;

void get(int x)

{

int k=1;

while(x)

{

if(x&1)f1[k]++;

else f0[k]++;

x>>=1;

k++;

}

for(k=k;k<=31;k++)f0[k]++;

}

int main()

{

//freopen("x3.in","r",stdin);

//freopen("x3.out","w",stdout);

scanf("%d",&n);

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

{

int x;scanf("%d",&x);

get(x);

}

for(int i=1;i<=31;i++)

ans+=(ll)(1<<(i-1))*f0[i]*f1[i];

printf("%I64d",ans);

return 0;

}

« 「BZOJ1121」[POI2008] 激光发射器SZK 「NOIP模拟赛」翻转排序 »

hzwer.com _ Home | http://hzwer.com

「NOIP模拟赛」求和式

分类目录

热门文章

Myfriends

近期评论