cdoj第13 th校試合初戦H-Hug the princess
8694 ワード
http://acm.uestc.edu.cn/#/contest/show/54
H - Hug the princess
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit
Status
There is a sequence with n elements. Assuming they are a1,a2,⋯,an.Please calculate the following expession.
In the expression above, ^ | & is bit operation.
Input
The first line contains a single integer n, which is the size of the sequence.
The second line contains n integers, the ith integer ai is the ith element of the sequence.
1≤n≤100000,0≤ai≤100000000
Output
Print the answer in one line.
Sample input and output
Sample Input
Sample Output
考え方:まず、自分でいくつかの例を挙げて検証することができて、異或演算と演算の和はちょうどあるいは演算に等価で、あるいはこのように考えることができて、異或は(1,0)、(0,1)、与是(1,1)、合わせてちょうどあるいは.それからテーマは2倍のあるいは演算を求めました.そして、各aiはajまたは演算(iこれは公式の問題です.
コード:
View Code
H - Hug the princess
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit
Status
There is a sequence with n elements. Assuming they are a1,a2,⋯,an.Please calculate the following expession.
In the expression above, ^ | & is bit operation. Input
The first line contains a single integer n, which is the size of the sequence.
The second line contains n integers, the ith integer ai is the ith element of the sequence.
1≤n≤100000,0≤ai≤100000000
Output
Print the answer in one line.
Sample input and output
Sample Input
Sample Output
2
1 26考え方:まず、自分でいくつかの例を挙げて検証することができて、異或演算と演算の和はちょうどあるいは演算に等価で、あるいはこのように考えることができて、異或は(1,0)、(0,1)、与是(1,1)、合わせてちょうどあるいは.それからテーマは2倍のあるいは演算を求めました.そして、各aiはajまたは演算(i
コード:
1 #include <fstream>
2 #include <iostream>
3 #include <algorithm>
4 #include <cstdio>
5 #include <cstring>
6 #include <cmath>
7 #include <cstdlib>
8 #include <vector>
9
10 using namespace std;
11
12 #define PI acos(-1.0)
13 #define EPS 1e-10
14 #define lll __int64
15 #define ll long long
16 #define INF 0x7fffffff
17
18 ll a[100005];
19 vector<ll> cnt;
20
21 int main(){
22 //freopen("D:\\input.in","r",stdin);
23 //freopen("D:\\output.out","w",stdout);
24 int n;
25 ll tn=0;
26 scanf("%d",&n);
27 for(int i=0;i<n;i++){
28 scanf("%lld",&a[i]);
29 tn=max(tn,a[i]);
30 }
31 ll ans=0,t=0;
32 while(tn){
33 t++;
34 tn>>=1;
35 cnt.push_back(0);
36 }
37 for(int i=0;i<n;i++){
38 ans+=a[i]*i;
39 for(int j=0;j<t;j++){
40 if(!((a[i]>>j)&1)){
41 ans+=(1<<j)*cnt[j];
42 }else{
43 cnt[j]++;
44 }
45 }
46 }
47 printf("%lld
",ans*2);
48 return 0;
49 }View Code