[NOIP2012] 开车旅行

摘要

倍增优化 DP

小 A 和小 B 决定旅行,城市从 1 到 N 编号,编号较小的城市在编号较大的城市的西边,各个城市的海拔高度互不相同,记城市 i 的海拔高度为 ,城市 i 和城市 j 之间的距离

旅行过程中,小 A 和小 B 轮流开车,第一天小 A 开车,之后每天轮换一次。他们计划选择一个城市 S 作为起点,一直向东行驶,并且最多行驶 X 公里就结束旅行。小 B 总是沿着前进方向选择一个最近的城市作为目的地,而小 A 总是沿着前进方向选择第二近的城市作为目的地(注意:本题中如果当前城市到两个城市的距离相同,则认为离海拔低的那个城市更近)。如果其中任何一人无法按照自己的原则选择目的城市,或者到达目的地会使行驶的总距离超出 X 公里,他们就会结束旅行。

在启程之前,小 A 想知道两个问题:

  1. 对于一个给定的 ,从哪一个城市出发,小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小(如果小 B 的行驶路程为 0,此时的比值可视为无穷大,且两个无穷大视为相等)。如果从多个城市出发,小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值都最小,则输出海拔最高的那个城市。
  2. 对任意给定的 和出发城市 ,小 A 开车行驶的路程总数以及小 B 行驶的路程总数。

.

题面长,复杂,懒得概括 emmm

好的这种题一看就是 DP。路程的范围太大显然不做为状态,于是 表示从城市 i 出发走 j 次,0/1 分别表示小 A/ 小 B 第一天开车,小 A 行驶的路程。同理 表示小 B 行驶的路程。这个 DP 的结果显然是单调的,因为走得多路程越多嘛。于是在查询的时侯可以二分查找。这样的复杂度是 ,显然无法接受。

经典套路, 表示从城市 i 出发走 次,0/1 分别表示小 A/ 小 B 第一天开车,小 A 行驶的路程。同理 表示小 B 行驶的路程。于是倍增优化后 DP 的复杂度就能降下来了。不过还需要维护一个 表示从城市 i 出发走 次,0/1 分别表示小 A/ 小 B 第一天开车,到达的城市。方程如下

由于 稍微有区别,因此要单独拿出来转移。 分别表示到达的最近的,第二近的城市编号,A,B 的转移同理

B 的就不写了,看代码

#include<cstdio>
#include<vector>
#include<algorithm>
#define fi first
#define se second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N=1e5+5;
int n,x0;
int h[N];

struct data{int pre,nex,idx,h;};
data e[N];
int le;
bool cmp(data x,data y){return x.h<y.h;}
bool cmp2(data x,data y){return x.idx<y.idx;}

int n1[N],n2[N];
int d(int x,int y){return abs(h[x]-h[y]);}

int nex[N][18][2],A[N][18][2],B[N][18][2];
void prework(){
    for(int i=1;i<=n;i++)nex[i][0][0]=n2[i], nex[i][0][1]=n1[i];
    for(int i=1;i<=n;i++)nex[i][1][0]=n1[n2[i]],nex[i][1][1]=n2[n1[i]];
    for(int j=2;(1<<j)<=n;j++){
        for(int i=1;i+(1<<j)<=n;i++){
            nex[i][j][0]=nex[nex[i][j-1][0]][j-1][0];
            nex[i][j][1]=nex[nex[i][j-1][1]][j-1][1];
        }
    }
    for(int i=1;i<=n;i++)A[i][0][0]=d(i,n2[i]);
    for(int i=1;i<=n;i++)A[i][1][0]=A[i][0][0], A[i][1][1]=A[n1[i]][0][0];
    for(int j=2;(1<<j)<=n;j++){
        for(int i=1;i+(1<<j)<=n;i++){
            A[i][j][0]=A[i][j-1][0]+A[nex[i][j-1][0]][j-1][0];
            A[i][j][1]=A[i][j-1][1]+A[nex[i][j-1][1]][j-1][1];
        }
    }
    for(int i=1;i<=n;i++)B[i][0][1]=d(i,n1[i]);
    for(int i=1;i<=n;i++)B[i][1][0]=B[n2[i]][0][1], B[i][1][1]=B[i][0][1];
    for(int j=2;(1<<j)<=n;j++){
        for(int i=1;i+(1<<j)<=n;i++){
            B[i][j][0]=B[i][j-1][0]+B[nex[i][j-1][0]][j-1][0];
            B[i][j][1]=B[i][j-1][1]+B[nex[i][j-1][1]][j-1][1];
        }
    }
}
pii query(int x,int u){
    // 从 u 出发行驶不超过 x 的 AB 路程
    int a=0,b=0;
    for(int j=17;j>=1;j--){
        if(!u)break;// 相当于已经走到尽头
        if(!nex[u][j][0])continue;
        int dis=A[u][j][0]+B[u][j][0];
        if(dis>x)continue;
        a+=A[u][j][0],b+=B[u][j][0],x-=dis;
        u=nex[u][j][0];
    }
    if(u)if(nex[u][0][0]&&A[u][0][0]<=x)a+=A[u][0][0];
    return make_pair(a,b);
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&h[i]);
        e[++le]=(data){0,0,i,h[i]};
    }
    sort(e+1,e+le+1,cmp);
    for(int i=1;i<=n;i++){
        e[i].pre=e[i-1].idx,e[i].nex=e[i+1].idx;
    }
    sort(e+1,e+le+1,cmp2);
    for(int i=1;i<=n;i++){
        int p=e[i].pre,pp=e[p].pre;
        int q=e[i].nex,qq=e[q].nex;
        int m=0x7fffffff,m2=0x7fffffff;
        if(p&&d(p,i)<m)n1[i]=p,m=d(p,i);
        if(q&&d(q,i)<m)n1[i]=q,m=d(p,i);
        if(p&&p!=n1[i]&&d(p,i)<m2)n2[i]=p,m2=d(p,i);
        if(pp&&pp!=n1[i]&&d(pp,i)<m2)n2[i]=pp,m2=d(pp,i);
        if(q&&q!=n1[i]&&d(q,i)<m2)n2[i]=q,m2=d(q,i);
        if(qq&&qq!=n1[i]&&d(qq,i)<m2)n2[i]=qq,m2=d(qq,i);
        if(p)e[p].nex=q;
        if(q)e[q].pre=p;
    }
    prework();
    scanf("%lld",&x0);
    pii a1=make_pair(1,0);
    int ans1=0;
    for(int i=1;i<=n;i++){
        pii p=query(x0,i);
        if(p.se==0&&p.fi==0)p.fi=1;// 无穷大处理
        if(a1.fi*p.se>a1.se*p.fi)a1=p,ans1=i;
        else if(a1.fi*p.se==a1.se*p.fi)ans1=h[ans1]>h[i]?ans1:i;
    }
    printf("%lld\n",ans1);
    int m;
    scanf("%lld",&m);
    for(int i=1;i<=m;i++){
        int x,s;
        scanf("%lld%lld",&s,&x);
        pii p=query(x,s);
        printf("%lld %lld\n",p.fi,p.se);
    }
    return 0;
}
/* 
 * BUG#1:L71 没有用 idx
 * BUG#2:L60L54 没有判断 nex 的存在性
 * BUG#3:L81L82 pp 和 q 的顺序问题
 */

  转载请注明: Sshwy's Blog [NOIP2012] 开车旅行

 上一篇
博客转型计划 博客转型计划
摘要 再小的星星也有光芒 没错!你现在看到的是 Sshwy 大菜鸡的一个计划! 心的起始每个人都是有故事的,也是有追求的。在 OI 这条路上,学习知识的时侯大多数人估计直接奔 OIWIKI 了,包括我。那么,为什么我要写这个博客?并不是单
2019.06.14
下一篇 
原根与模算术 原根与模算术
摘要 啃课件的时侯遇到的数论题,于是来填坑 阶与原根如果 (a,m)=1,记 x 为最小的正整数使得 . 那么 x 称为 的阶。记为 。 可以把阶理解为模意
2019.06.08
  目录