本文共 2353 字，大约阅读时间需要 7 分钟。
考虑到题目中给出了路径的生成方式，也就是说，从一个固定的点出发，路径是已知的，就可以想到了倍增的思想
计算ga[i]表示i出发次近的点,也就是A开一次车到的地方；
gb[i]表示i之后最近的点,也就是B开一次车到的地方
然后处理f[i,j,k]表示k先出发，从i走j天的到达城市
f[0,j,0]=ga[j], f[0,j,1]=gb[j]i=1 -> f[1,j,k]=f[0,f[0,j,k],1-k]i>1 -> f[i,j,k]=f[i-1,f[i-1,j,k],k]
然后处理一个da[i,j,k]，db[i,j,k]表示k先出发，从j走2^i天后A/B走的距离
具体计算方式和f相似，不再赘述，详见代码
代码
#include #define rint register int#define MAXN 100010using namespace std;typedef long long ll;int X,S,num[MAXN],m,n,nextA[MAXN],nextB[MAXN],f[MAXN][21],stA[MAXN][21],stB[MAXN][21],ans;ll ansA,ansB;double minn=1e9;const int inf=1e9;struct town{ int h,id,L,R;}a[MAXN];inline ll read(){ register char c=getchar(); register ll x=0; short f=1; while(c>'9'||c<'0') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=(x<<3)+(x<<1)+c-'0'; c=getchar(); } return x*f;}inline bool cml(town a,town b){ return a.h =0;--i) { if(f[star][i]&&(ll)(ansA+ansB+stA[star][i]+stB[star][i])<=x) { ansA+=stA[star][i]; ansB+=stB[star][i]; star=f[star][i]; } } if(nextA[star]&&ansA+ansB+stA[star][0]<=x) ansA+=stA[star][0]; return ;} int main(void){ //freopen("a.in","r",stdin); n=read(); for(rint i=1;i<=n;++i) { a[i].h=read(); a[i].id=i; } sort(a+1,a+n+1,cml); for(rint i=1;i<=n;++i) num[a[i].id]=i; for(rint i=1;i<=n;++i) { a[i].L=i-1; a[i].R=i+1; } a[1].L=a[n].R=0; for(rint i=1;i<=n;++i) { int now=num[i],l=a[now].L,r=a[now].R; if(check(now,l,r)) { nextB[i]=a[l].id; nextA[i]=judge(now,a[l].L,r); } else { nextB[i]=a[r].id; nextA[i]=judge(now,l,a[r].R); } if(l) a[l].R=r; if(r) a[r].L=l; } for(rint i=1;i<=n;++i) { f[i][0]=nextB[nextA[i]]; stA[i][0]=abs(a[num[i]].h - a[num[nextA[i]]].h); stB[i][0]=abs(a[num[f[i][0]]].h - a[num[nextA[i]]].h); } for(rint j=1;j<=19;++j) { for(rint i=1;i<=n;++i) { f[i][j]=f[f[i][j-1]][j-1]; //倍增 stA[i][j]=stA[i][j-1]+stA[f[i][j-1]][j-1]; stB[i][j]=stB[i][j-1]+stB[f[i][j-1]][j-1]; } } X=read(); m=read(); for(rint i=1;i<=n;++i) { solve(X,i); if(ansB&&1.0*ansA/ansB
转载地址：http://ndwm.baihongyu.com/