Hdu 5358 First One (尺取法+枚举)

题目链接：

　　Hdu 5358 First One

题目描述：

　　数组a有n个元素，S[i,j]定义为a[i]+a[i+1]+.....+a[j]，问：这个死东西等于多少？

解题思路：

　　二分肯定超，这个题目的时间卡的炒鸡严格，只有n*log(n)的复杂度才能过，n*log(n)^2都不可以的。

　　只需要枚举K，并且枚举区间左端i值，计算K的贡献值，然后遍历时候计算一下常数相加即可。

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef long long LL;

 const LL maxn = ;

 LL dp[maxn][], arr[maxn];

 int main ()

 {

     int t, n;

     scanf ("%d", &t);

     while (t --)

     {

         scanf ("%d", &n);

         arr[] = ;

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

             scanf ("%lld", &arr[i]);

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

         {

             LL sum = 1LL<<(i+);

             LL num = arr[];

             LL p = ;

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

             {

                 num -= arr[j-];

                 while (num<sum && p<=n)

                     num += arr[++p];

                 dp[j][i] = p;//S[j,p]<2^i

             }

         }

         LL ans = , res;

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

         {

             LL p = i, q;

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

             {

                 q = dp[i][j];

                 res = (j+)*(i*(q-p) + (q+p-)*(q-p)/);

                 ans += res;

                 p = q;

             }

         }

         printf ("%lld\n", ans);

     }

     return ;

 }

对了，大家看了我的题解如果还是TLE的话，希望大家不要留言骂我哦。因为编译环境不同，HDU就会返回不同的答案，什么为什么，我也不知道啦。