倍增题

发表于 | 分类于

牛客 区间的连续段

题意

​ 给你一个长为n的序列a和一个常数k ，有m次询问，每次查询一个区间[l,r]内所有数最少分成多少个连续段，使得每段的和都 <= k ，如果这一次查询无解，输出”Chtholly”。

思路

​ 求前缀和，然后先预处理出走一步所能到达得最远的位置，然后用dp[i][j]表示从i点出发分成1<<j段的最远所到达的位置

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
long long a[maxn];
int dp[maxn][37];
int main(){
	int n,k,m;
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++) {
		scanf("%lld",&a[i]);
		a[i]+=a[i-1];
	}
	a[n+1]=a[n]+k;
	for(int i=1;i<=n;i++){
		int p=lower_bound(a+1,a+n+1,a[i-1]+k+1)-a;
		dp[i][0]=p;
	}
	for(int i=0;i<=31;i++) dp[n+1][i]=n+1;
	for(int j=1;j<=31;j++){
		for(int i=1;i<=n;i++){
			dp[i][j]=dp[dp[i][j-1]][j-1];
		}
	}
	while(m--){
		int l,r;
		scanf("%d%d",&l,&r);
		int ans=0;
		for(int i=31;i>=0;i--){
			if(dp[l][i]<=r){
				l=dp[l][i];
				ans+=(1<<i);
			}
		}
		if(dp[l][0]<=r) printf("Chtholly\n");
		else printf("%d\n",ans+1);
		 
	}
	//system("pause");
}

Educational Codeforces Round 66 (Rated for Div. 2)

题意

​ 求覆盖目标区域至少需要多少个区间

思路

​ dp[i][j]表示从i点出发需要最少需要1<<j的区间覆盖。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
int a[maxn];
int dp[maxn][33];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		int l,r;
		scanf("%d%d",&l,&r);
		dp[l][0]=max(dp[l][0],r);
	}
	for(int i=1;i<maxn;i++) dp[i][0]=max({dp[i-1][0],dp[i][0]});
	for(int j=1;j<=31;j++){
		for(int i=0;i<maxn;i++){
			dp[i][j]=dp[dp[i][j-1]][j-1];
		}
	}
	for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            printf("%d ",dp[i][j]);
        }
        puts("");
    }
	while(m--){
		int l,r;
		scanf("%d%d",&l,&r);
		int ans=0;
		if(dp[l][31]<r){
			printf("-1\n");
			continue;
		}
		for(int i=31;i>=0;i--){
			if(dp[l][i]<r){
				ans+=(1<<i);
				l=dp[l][i];
			}
		}
		printf("%d\n",ans+1);
	}
	//system("pause");
}