首页 > 代码库 > AtCoder Tak and Hotels

AtCoder Tak and Hotels

题目链接:传送门

题目大意:有 n 个点排成一条直线,每次行动可以移动不超过 L 的距离,每次行动完成必须停在点上,

     数据保证有解,有 m 组询问,问从 x 到 y 最少需要几次行动?

题目思路:倍增

     dp[i][j] 表示从 j 出发用 (1<<i)次行动可达的最靠左的端点。

#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <cstring>#include <stack>#include <cctype> #include <queue>#include <string>#include <vector>#include <set>#include <map>#include <climits>#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r   ///ºê#define fi first#define se second#define ping(x,y) ((x-y)*(x-y))#define mst(x,y) memset(x,y,sizeof(x))#define mcp(x,y) memcpy(x,y,sizeof(y))using namespace std;#define gamma 0.5772156649015328606065120#define MOD 1000000007#define inf 0x3f3f3f3f#define N 1000005#define maxn 100005typedef pair<int,int> PII;typedef long long LL;int n,m,k,cnt,L,R,now,last;int a[maxn];int dp[20][maxn];int main(){    int i,j,x,y,last=1;    scanf("%d",&n);    for(i=1;i<=n;++i)scanf("%d",&a[i]);    scanf("%d",&k);    for(i=1;i<=n;++i){        while(a[i]-a[last]>k)++last;        dp[0][i]=last;    }    for(i=1;i<20;++i)    for(j=1;j<=n;++j)    dp[i][j]=dp[i-1][dp[i-1][j]];    scanf("%d",&m);    while(m--){        int ans=0;        scanf("%d%d",&x,&y);        if(x>y)swap(x,y);        for(i=16;i>=0;--i){            if(dp[i][y]>x){                ans+=(1<<i);                y=dp[i][y];            }        }        printf("%d\n",ans+1);    }    return 0;}

 

AtCoder Tak and Hotels