hdu 5358 First One

　　题目链接：hdu 5358

　　思路不难理解，就是个尺取法而已，floor(log₂X) + 1 就是求 X 的二进制表示的位数，对于题目来说这个值最多只是 30+，从这里入手开始枚举，运用尺取法可以达到 O(n) 的复杂度，具体百度之，按照这个思路写的代码 wa 了无数遍，一下午又这样没了，唉，好无语啊~~让我吃尽苦头的一道题，先记录下来，有空再慢慢琢磨。已AC代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef long long ll;
 6 const int N = 100005;
 7 
 8 int n, a[N];
 9 ll sum[N];
10 ll p2[40] = {1, };
11 inline void init(int n = 35) {
12     for(int i = 1; i <= n; ++i)
13         p2[i] = p2[i - 1] * 2;
14 }
15 
16 inline ll func(ll L, ll r1, ll r2) {
17     return (L + r1 + L + r2) * (r2 - r1 + 1) / 2;
18 }
19 
20 ll cal(int k) {
21     ll res = 0;
22     ll low = (k == 1 ? 0: p2[k - 1]), up = p2[k] - 1;
23     int r1 = 1, r2 = 0;
24     for(int L = 1; L <= n; ++L) {
25         r1 = max(r1, L);
26         while(r1 <= n && (sum[r1] - sum[L - 1]) < low)   ++r1;
27         if(r1 > n || sum[r1] - sum[L - 1] > up)   continue;
28 
29         r2 = max(r2, r1 - 1);
30         while(r2 + 1 <= n && sum[r2 + 1] - sum[L - 1] >= low
31               && sum[r2 + 1] - sum[L - 1] <= up)    ++r2;
32 
33         if(r1 > r2)   continue;
34         res += func(L, r1, r2);
35     }
36     return res * k;
37 }
38 
39 int main() {
40     int t;
41     init();
42     scanf("%d",&t);
43     while(t--) {
44         scanf("%d",&n);
45         for(int i = 1; i <= n; ++i) {
46             scanf("%d", a + i);
47             sum[i] = sum[i - 1] + a[i];
48         }
49         ll ans = 0;
50         for(int i = 1; i <= 35; ++i)
51             ans += cal(i);
52         printf("%I64d
",ans);
53     }
54     return 0;
55 }