UESTC--1041--Hug the princess（位运算）

本文主要是介绍UESTC--1041--Hug the princess（位运算），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Hug the princess

Time Limit: 1000MS

Memory Limit: 65535KB

64bit IO Format: %lld & %llu

Submit Status

Description

There is a sequence with elements. Assuming they are .

Please calculate the following expession.

In the expression above, ^|& is bit operation. If you don’t know bit operation, you can visit

http://en.wikipedia.org/wiki/Bitwise_operation

to get some useful information.

Input

The first line contains a single integer , which is the size of the sequence.

The second line contains integers, the integer is the element of the sequence.

Output

Print the answer in one line.

Sample Input

2
1 2

Sample Output

Hint

Because the answer is so large, please use long long instead of int. Correspondingly, please use %lld instead of %d to scanf and printf.

Large input. You may get Time Limit Exceeded if you use “cin” to get the input. So “scanf” is suggested.

Likewise, you are supposed to use “printf” instead of “cout”.

Source

The 13th UESTC Programming Contest Preliminary

n个数，然后每个数对他后边的数字进行所有的位运算，然后取这些位运算的和，因为数的个数太多，所以不能直接暴力，所以这一步把数字转化为2进制，然后记录前缀和，并且记录每个数的最高位，同时对他下边的二进制位进行染色，表示这一位有多少个数字可以影响到，最后根据位运算的规则，对后边的前缀和操作，因为我们已经记录了每一个数对一个二进制位的影响，所以可以分清1还有0都是谁的

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 1e5 + 100;
int num[MAXN][35];
int a[35];
int p[MAXN];
typedef long long LL;
int main()
{int n;while(~scanf("%d", &n)){int x;memset(num, 0, sizeof(num));for(int i = 1; i <= n; i++){scanf("%d", &x);for(int j = 0; j < 33; j++){num[i][j] = num[i - 1][j] + x % 2;x = x / 2;}}LL ans = 0;for(int i = 1; i <= n; i++){int temp = 0, pos = -1;for(int j = 0; j < 33; j++){a[j] = num[i][j] - num[i - 1][j];}for(int j = 0; j < 33; j++){int cnt = 0;if(a[j]){cnt += (i - 1 - num[i - 1][j]);cnt += i - 1;cnt += num[i - 1][j];}else{cnt += num[i - 1][j];cnt += num[i - 1][j];}ans += (LL)cnt * (1 << j);}}printf("%lld\n", ans);}return 0;
}

这篇关于UESTC--1041--Hug the princess（位运算）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！