程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDOJ 5358 First One 暴力

HDOJ 5358 First One 暴力

編輯：C++入門知識

HDOJ 5358 First One 暴力

⌊log2S(i,j)⌋+1 就是S(i,j) 的二進制位數.....

枚舉二進制的每一位數,計算相應的權值

具體作法就是對每個二進制位數 i ,掃一遍數組,對每個數 j 維護一個L,R 表示以該數為左端點,右端點可以在L~R的范圍,這個區間內的值

加起來有 i 位二進制位數,那麼這個數對答案的貢獻為設: dur = (R-L+1) 貢獻值: dur*j+(R+L)*dur/2

C++秒T , G++ 1.3s ac

First One

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1183 Accepted Submission(s): 357

Problem Description soda has an integer array a1,a2,…,an. Let S(i,j) be the sum of ai,ai+1,…,aj. Now soda wants to know the value below: ∑i=1n∑j=in(⌊log2S(i,j)⌋+1)×(i+j)
Note: In this problem, you can consider log20 as 0.

Input There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first line contains an integer n (1≤n≤105), the number of integers in the array.
The next line contains n integers a1,a2,…,an (0≤ai≤105).
Output For each test case, output the value.
Sample Input

1
2
1 1

Sample Output

Source 2015 Multi-University Training Contest 6

/* ***********************************************
Author        :CKboss
Created Time  :2015年08月07日 星期五 16時48分08秒
File Name     :HDOJ5358.cpp
************************************************ */

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include

using namespace std;

typedef long long int LL;

const int maxn=100100;

int n;
LL s[maxn];

int main()
{
	//freopen(in.txt,r,stdin);
	//freopen(out.txt,w,stdout);

	int T_T;
	scanf(%d,&T_T);
	while(T_T--)
	{
		scanf(%d,&n);
		for(int i=1,x;i<=n;i++)
		{
			scanf(%d,&x);
			s[i]=s[i-1]+x;
		}

		LL ans=0;

		for(int i=0;i<35;i++)
		{
			/// 在left 和 right 之間的數有(i+1)個1

			LL left=(1LL<right) R--;

				LL dur=R-L+1;
				ans=ans+(i+1LL)*(dur*j+(R+L)*dur/2LL);
			}
		}

		cout<