Educational Codeforces Round 66 (Rated for Div. 2)-E. Minimal Segment Cover
程序员文章站
2023-12-25 18:30:57
...
地址:https://codeforces.com/contest/1175/problem/E
思路:倍增DP
dp[i][j]表示以i为起点走 2^j 条线段能够到达的最远位置,那么
dp[i][j]=dp[dp[i][j-1]][j-1]
对于每次询问,j由大到小判断即可
Code:
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int MAX_S=5e5+5;
int n,m,lm;
int dp[MAX_S][20];
int Query(int l,int r);
int main()
{
scanf("%d%d",&n,&m);
int l,r,mr=0;
for(int i=0;i<n;++i)
{
scanf("%d%d",&l,&r);
dp[l][0]=max(dp[l][0],r);
mr=max(mr,r);
}
lm=log2(mr);
for(int i=1;i<=mr;++i)
dp[i][0]=max(dp[i][0],max(i,dp[i-1][0]));
for(int j=1;(1<<j)<=mr;++j)
for(int i=0;i<=mr;++i)
dp[i][j]=dp[dp[i][j-1]][j-1];
for(int i=0;i<m;++i)
{
scanf("%d%d",&l,&r);
printf("%d\n",Query(l,r));
}
return 0;
}
int Query(int l,int r)
{
int res=0;
for(int j=lm;j>=0;--j)
if(dp[l][j]!=l&&dp[l][j]<r){
l=dp[l][j]; res+=(1<<j);
}
l=dp[l][0]; ++res;
if(l<r) res=-1;
return res;
}
推荐阅读
-
Educational Codeforces Round 37 (Rated for Div. 2) E. Connected Components?(图论+连通块+bfs)
-
Educational Codeforces Round 66 (Rated for Div. 2)-E. Minimal Segment Cover
-
Educational Codeforces Round 65 (Rated for Div. 2) E. Range Deleting(双指针+思维)
-
Educational Codeforces Round 66 (Rated for Div. 2) E. Minimal Segment Cover 倍增
-
Educational Codeforces Round 71 (Rated for Div. 2)E. XOR Guessing
-
Educational Codeforces Round 97 (Rated for Div. 2) D. Minimal Height Tree
-
Educational Codeforces Round 67 (Rated for Div. 2) E. Tree Painting(树形dp)
-
Educational Codeforces Round 44 (Rated for Div. 2) E. Pencils and Boxes
-
Educational Codeforces Round 77 (Rated for Div. 2) E. Tournament (DP)
-
Educational Codeforces Round 66 (Rated for Div. 2) 题解