现在的位置: 主页 > 企业简介 > 文章列表

HDOJ 5358 First One 暴力

作者:成都金海力科技有限公司 来源:www.scjinhaili.com 未知发布时间:2017-09-03 12:09:41
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 12
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

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:武汉网站建设 http://www.feimao666.com

上一篇:网站细分分析的十个要点 下一篇:最后一页