本文主要是介绍hdu5358--First One（双指针），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：点击打开链接
题目大意：给出一个序列，其中S(i,j)代表a[i]到a[j]的和，然后计算的和。
其中包含了向下取整，所以我们可以想到，log(2,S(i,j))向下取整后最大也就是33，所以我们可以寻找log值相同的段，
对于以每一个数为起点，都有可能存在一段连续的序列，他们的log值是相同的，，，一开始的做法是枚举起点i，然后对每一段log值计算一个区间(r1,r2)，通过二分找到这个区间，计算出和，那么时间复杂度是n*log(n)*log(n)，妥妥超时了，，，，
时间一定要是严格的n*log(n)
所以可以枚举log的值0～33，对于每一个log的值，枚举开始的起点，用双指针（尺取法）找到那一段连续的序列，以j为枚举的累加位置，r1记录序列的开始的位置，r2记录刚超出序列的位置，那么从j累加到[r1,r2-1]这一段的log值就是相同的。
注意：r1要>=j，r2可以为n+1。保证[r1,r2-1]区间的r2-1可以到n
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
#define LL __int64
LL a[100010] , sum[100010] ;
LL s[40] ;
int main() {int t , n , i , j , r1 , r2 ;LL ans , cnt1 , cnt2 , k ;s[0] = 0 ;s[1] = 2 ;for(i = 2 ; i <= 35 ; i++)s[i] = s[i-1]*2 ;scanf("%d", &t) ;while( t-- ) {scanf("%d", &n) ;a[0] = sum[0] = 0 ;for(i = 1 ; i <= n ; i++) {scanf("%I64d", &a[i]) ;sum[i] = sum[i-1] + a[i] ;}a[n+1] = 0 ;ans = 0 ;for(i = 0 ; i < 35 ; i++) {if( s[i] > sum[n] ) break ;r1 = r2 = 1 ;cnt1 = cnt2 = a[1] ;for(j = 1 ; j <= n ; j++) {while( (r1 < j )|| r1 <= n && cnt1 < s[i] ) {r1++ ;cnt1 += a[r1] ;}if( r1 > n ) break ;while( r2 <= n && cnt2 < s[i+1] ) {r2++ ;cnt2 += a[r2] ;}if( r1 <= r2-1 ) {k = r2-r1 ;ans += k*(i+1)*j + ( k*r1+k*(k-1)/2 )*(i+1) ;}cnt1 -= a[j] ;cnt2 -= a[j] ;}}printf("%I64d\n", ans) ;}return 0 ;
}
这篇关于hdu5358--First One（双指针）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
