生活随笔
收集整理的這篇文章主要介紹了
nowcoder 河 我 车 题 错 天 乐 赛 倍增处理
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
傳送門
文章目錄
題意：
思路：
倍增經典題了，考慮維護一個前綴和sum[i]sum[i]sum[i]，對于iii位置我們肯定是貪心的選能到的最遠位置，即第一個>sum[i?1]+k>sum[i-1]+k>sum[i?1]+k的位置，讓后讓f[i][0]=posf[i][0]=posf[i][0]=pos即可。
之后預處理倍增數組，讓后對于每組詢問不斷倍增，最后f[l][0]<=rf[l][0]<=rf[l][0]<=r的話說明無解。
注意處理倍增數組的一些細節，比如需要將n+1n+1n+1的倍增數組跳的位置置為n+1n+1n+1，不然會跳到000位置?；蛘咛嘏幸幌?span id="ze8trgl8bvbq" class="katex--inline">000不能跳也可以。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#include<random>
#include<cassert>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].l+tr[u].r)>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=1000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const LL inf
=0x3f3f3f3f3f3f3f3f;
const double eps
=1e-6;int n
,m
,k
;
int a
[N
];
int f
[N
][22],st
[N
];
LL sum
[N
];int main()
{
scanf("%d%d%d",&n
,&m
,&k
);for(int i
=1;i
<=n
;i
++) {scanf("%d",&a
[i
]),sum
[i
]=sum
[i
-1]+a
[i
];st
[i
]=st
[i
-1]+(a
[i
]>k
);}for(int i
=1;i
<=n
;i
++) {int pos
=upper_bound(sum
+i
,sum
+1+n
,sum
[i
-1]+k
)-sum
;f
[i
][0]=pos
;}for(int i
=0;i
<=20;i
++) f
[n
+1][i
]=n
+1;for(int j
=1;j
<=20;j
++) for(int i
=1;i
<=n
;i
++) {f
[i
][j
]=f
[f
[i
][j
-1]][j
-1];}while(m
--) {int l
,r
; scanf("%d%d",&l
,&r
);int ans
=0;for(int i
=20;i
>=0;i
--) {if(f
[l
][i
]<=r
) l
=f
[l
][i
],ans
+=1<<i
;}if(f
[l
][0]<=r
) puts("Chtholly");else printf("%d\n",ans
+1);}return 0;
}
創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎
總結
以上是生活随笔為你收集整理的nowcoder 河 我 车 题 错 天 乐 赛 倍增处理的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
