HDU 5358 First One(枚举)-白红宇

HDU 5358 First One(枚举)

阅读量：7066 次

发布时间：2019-06-28

本文共 1540 字，大约阅读时间需要 5 分钟。

这道题假设依照表达式一个个来算肯定超时，下午时候想了一个O(nlogn*logn)的算法。可是t了。由于这道题卡的很紧几百个例子，必须nlogn的算法才干够ac

回到这道题，考虑log(sum(i,j))+1的特点，能够发现它的值域范围很小。在1-34之间。那么我们能够考虑枚举log(sum(i,j)+1的值。记为k，然后统计(i+j)的和就可以。

对于每个k，找到全部满足2^(k-1)<=sum(i,j)<=2^k-1的（i+j），

那么我们考虑每一个前缀i，找到这个前缀满足2^(k-1)<=sum(i,j)<=2^k-1的区间[l,r]，即对于这个区间的每一个元素s(i,j),都满足上式(l<=j<=r)。

这一步枚举有一个小技巧，当我们找到前缀i的区间[l,r]之后。那么前缀i+1满足上式的区间一定不可能在前缀i的[l, r]之前。

那么我们用两个指针维护这个区间就可以，那么时间复杂度就降为了O(n*logn).

ps:下午写的n*logn*logn的代码在我电脑上跑了22000ms，ac代码在我电脑上跑了5500ms，ac代码在oj上跑了1600ms。

#include
     
        #include
      
         #include
       
          #include
        
           #include
         
            #include
          
            #include
           
             #include
             #include
             
               #include
              
                #include
               
                #include
                
                  #include
                  #include
                  
                   #define eps 1e-6 #define LL long long #define pii (pair
                   
                    )//#pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const int maxn = 100000 + 500;//const int INF = 0x3f3f3f3f;LL a[maxn], s[maxn];int n;int main() { clock_t start = clock();// freopen("input.txt", "r", stdin); int T; cin >> T; while(T--) { scanf("%d", &n); LL ans = 0; for(int i = 1; i <= n; i++) { scanf("%I64d", &a[i]); s[i] = s[i-1] + a[i]; } for(int k = 1; k <= 34; k++) { int l = 1, r = 0; LL liml = k==1 ? 0 : (1LL<<(k-1)), limr = (1LL<
                    
                     =liml && s[r+1]-s[i-1]<=limr) r++; if(l>r) continue; // if(k==2) cout << l << " " << r << " " << i << endl; ans += (LL)(i+l+i+r)*(r-l+1)/2*k; } // if(k < 5) cout << ans << endl; } cout << ans << endl; } clock_t end = clock();// cout << end-start << endl; return 0;}

你可能感兴趣的文章