First One

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

soda has an integer array $a_1,a_2,\dots,a_n$. Let $S(i,j)$ be the sum of $a_i,a_i+1,\dots,a_j$. Now soda wants to know the value below:

\[\sum_{i = 1}^{n}\sum_{j = i}^{n}(\lfloor \log_{2}{S(i,j)} \rfloor + 1)\times (i+j) \]

Note: In this problem, you can consider $\log_{2}{0}$ 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 \geq n \leq 10^5)$,the number of integers in the array.

The next line contains n integers $0 \leq a_{i} \leq 10^{5}$

Output

For each test case, output the value.

Sample Input

1 1

Sample Output

Source

2015 Multi-University Training Contest 6 F-1006

解题：这道题目有意思，我们可以发现 $a_{i} \leq 10^{5}$ 这是一个信息，破题的关键.

$\log_{2}{sum}$大概会在什么范围呢？sum最多是 $10^{5} \times 10^{5} = 10^{10}$

也就是说$\log_{2}{sum} \leq 34$

才35，sum的特点是什么?很明显都是非负数，那么sum必须是递增的，单调的，F-100. 我们可以固定$log_{2}{S(i,j)}$ 后固定左区间j,找出以j作为左区间，然后当然是找出最小的r 和最大的 R

最小最大？当然是这样的区间，该区间的和取对数是我们刚刚固定的那个数。区间可以表示成这样 $[j,r\dots R]$ 那么从j到r,j到 r+1,...,j 到R ，这些区间的和取对数都会等于同一个数。。

好了如何算$[j,r\dots R]$ 的下标和？很明显吗。。j r,j r+1, j r+2,..., j R.把左区间下标一起算了，右区间是个等差数列，求和。

我们在最后把那个表达式里面的1加上

同样的计算方法

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 const int maxn = ;

 LL p[] = {},sum[maxn];

 void init() {

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

         p[i] = (p[i-]<<);

 }

 int main() {

     init();

     int kase,n;

     scanf("%d",&kase);

     while(kase--){

         scanf("%d",&n);

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

             scanf("%I64d",sum+i);

             sum[i] += sum[i-];

         }

         LL ret = ;

         for(int i = ; i <=  && p[i] <= sum[n]; ++i){

             int L = ,R = ;

             LL tmp = ;

             for(int j = ; j <= n; ++j){

                 while(L <= n && sum[L] - sum[j-] < p[i]) ++L;

                 while(R +  <= n && sum[R + ] - sum[j-] < p[i+]) ++R;

                 if(L <= R) tmp += (LL)j*(R - L + ) + 1LL*(L + R)*(R - L + )/;

             }

             ret += tmp*i;

         }

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

             ret += LL(n + i)*(n - i + )/ + LL(i)*(n - i + );

         printf("%I64d\n",ret);

     }

     return ;

 }

巴特西

2015 Multi-University Training Contest 6 hdu 5358 First One

First One

最新文章

热门文章