NOIP2012 开车旅行：SET+倍增

68 阅读 0 评论 45 点赞

我是靠谱客的博主鲜艳裙子，最近开发中收集的这篇文章主要介绍NOIP2012 开车旅行：SET+倍增，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

啊，看到题：字好多。
然后就直接开始码暴力模拟了，觉得可以预处理一下每个点可以到达的最近点和次近点，这样大概就有50分了（然而实际有70分。。我忽略了只能往后走这一点带来的便利，于是每一次都要找一次最近点&次近点= =果然弱啊(。・・)ノ）
暴力的过程写的蛮。。。第一次只骗到15分= =，后来发现了BUG调到35.。就开始在精度这里卡。。。换了几种最后终于有50了。。。【我还存了一次余数除数hh.。。。】
去看了大牛的暴力，突然发现自己忽略了预处理。。。
暴力【50】如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#define ll long long
#define maxn 100010
using namespace std;
const ll inf=1e18;
int n,m;
ll x0;
ll h[maxn];
int vis[maxn];
ll sum[2];
int find(int x,int typ){
    ll minn=inf;int y=0;
    for(int j=1;j<=n;j++){
        if(j<=x || vis[j])continue;
        ll tp=abs(h[j]-h[x]);
        if(minn>tp){
            y=j;minn=tp;
        }
        else if(tp==minn){
            if(h[j]<h[y])y=j;
        }
    }
    if(typ==1)return y;
    int z=0;minn=inf;
    for(int j=1;j<=n;j++){
        if(j<=x || vis[j] || y==j)continue;
        ll tp=abs(h[j]-h[x]);
        if(minn>tp){
            z=j;minn=tp;
        }
        else if(tp==minn){
            if(h[j]<h[z])z=j;
        }
    }
    if(typ==0)return z;
}
void solve(int st,ll limit){
    vis[st]=1;
    int now=0;
    ll tot=0;
    int j=st;vis[st]=1;
    while(1){
        if(now==0){//a
            int k=find(j,0);
            if(k && !vis[k]){
                ll tp=abs(h[k]-h[j]);
                if((tot+tp)>limit)return ;
                j=k;
                sum[0]+=tp;
                tot+=tp;
                vis[j]=1;
                now^=1;//printf("%lld %lld a.[%d]n",tp,tot,j);
            }
            else return ;
        }
        else if(now==1){
            int k=find(j,1);
            if(k && !vis[k]){
                ll tp=abs(h[k]-h[j]);
                if((tot+tp)>limit)return ;
                j=k;
                sum[1]+=tp;
                tot+=tp;
                vis[j]=1;
                now^=1;//printf("%lld %lld b.[%d]n",tp,tot,j);
            }
            else return ;
        }
    }
}
void solve1(ll x0,int ty,int hh){
    if(ty==1){
        ll res=inf;
        int ans;
        ll ans0=1,ans1=0;
        for(int i=1;i<=n;i++){
            memset(vis,0,sizeof vis);
            sum[0]=sum[1]=0;
            solve(i,x0);
            ll tp;
            if(sum[1]==0)continue;
            if(ans1==0 && h[ans]<h[i]){
                ans0=sum[0];ans1=sum[1];
                ans=i;
            }
            else if(sum[1] && ((double)ans0/ans1>(double)sum[0]/sum[1] || ((double)sum[1]*ans0==(double)ans1*sum[0] && h[ans]<h[i]))){
                        ans0=sum[0];ans1=sum[1];ans=i;
                    }
        }
        printf("%dn",ans);
    }
    else if(ty==2){
        memset(vis,0,sizeof vis);
        sum[0]=sum[1]=0;
        solve(hh,x0);
        printf("%lld %lldn",sum[0],sum[1]);
    }
}
void file(){
    freopen("drive.in","r",stdin);
    freopen("drive.out","w",stdout);
}
int main(){
//  file();
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&h[i]);
    }
    scanf("%lld",&x0);
    solve1(x0,1,0);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int s;
        ll x;
        scanf("%d%lld",&s,&x);
        solve1(x,2,s);
    }
    return 0;
}

70分就不管了，此时已经。。。
然后开始写正解。
顺道学了一下set
怎样的呢？
我们可以把A,B分别走的两步看成一步，就可以用ST了。tt[i][j]表示i节点向后走2^j步到达的点，va[i][j],vb[i][j]分别表示此时a,b走的距离。
用set存每个点，注意是倒着存。把每个点最近点和次近点的标号和距离存下来
之后两个询问直接模拟就好。然后就A了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define ll long long
#define maxn 100010
using namespace std;
const ll inf=1e18;
int n,m;
ll x0;
ll h[maxn];
int vis[maxn];
struct node{
    ll key,h;
}t[5];
int tt[maxn][21];
ll va[maxn][21],vb[maxn][21];
set<ll>q;
map<ll,int>mp;
ll a[maxn],b[maxn];
int fa[maxn],fb[maxn];
bool cmp(node u,node v){
    return (u.key<v.key ||(u.key==v.key && u.h<v.h));
}
void pre(){
    for(int i=n;i>=1;i--){
        q.insert(h[i]);
        t[1].h=*--q.lower_bound(h[i]);
        t[2].h=*q.upper_bound(h[i]);
        if(t[1].h!=-inf)t[3].h=*--q.lower_bound(t[1].h);
        else t[3].h=-inf;
        if(t[2].h!=inf)t[4].h=*q.upper_bound(t[2].h);
        else t[4].h=inf;
        for(int k=1;k<=4;k++){
            t[k].key=abs(t[k].h-h[i]);
        }
        sort(t+1,t+5,cmp);
        a[i]=t[2].key;b[i]=t[1].key;
        fa[i]=mp[t[2].h];fb[i]=mp[t[1].h];//system("pause");
    //  for(int j=1;j<=n;j++){
    //      printf("(%d %d %d %lld %lld)n",i,fa[i],fb[i],a[i],b[i]);
    //  }
        for(int j=0;j<=20;j++){
            if(!j){
                if(fa[i]){
                    tt[i][0]=fa[i];va[i][0]=a[i];
                }
            }
            else if(j==1){
                if(fb[fa[i]]){
                    tt[i][1]=fb[fa[i]];
                    vb[i][1]=b[fa[i]];va[i][1]=a[i];
                }
            }
            else if(tt[tt[i][j-1]][j-1]){
                va[i][j]=va[i][j-1]+va[tt[i][j-1]][j-1];
                vb[i][j]=vb[i][j-1]+vb[tt[i][j-1]][j-1];
                tt[i][j]=tt[tt[i][j-1]][j-1];
            }
            else break;
        }
    }
}
double calc1(int s,ll limit,int typ){
    ll suma=0;ll sumb=0;
    if(typ==1){
        for(int i=20;i>=0;i--){
            if(tt[s][i] && (suma+sumb+va[s][i]+vb[s][i])<=limit){
                suma+=va[s][i];sumb+=vb[s][i];
                s=tt[s][i];
            //  printf("[%d %lld %lld]n",s,suma,sumb);
            }
        }//system("pause");
        if(sumb==0)return inf;
        return (double)suma/(double)sumb;
    }
    else if(typ==2){
        for(int i=20;i>=0;i--){
            if(tt[s][i] && (suma+sumb+va[s][i]+vb[s][i])<=limit){
                suma+=va[s][i];sumb+=vb[s][i];
                s=tt[s][i];
            //  printf("[%d %lld %lld]n",s,suma,sumb);
            }
        }//system("pause");     
        printf("%lld %lldn",suma,sumb);
        return 0;
    }
}
void solve1(ll x0){
    double minn=1e18;int ans;//printf("&n");
    for(int i=1;i<=n;i++){
        double tp=calc1(i,x0,1);
        if(minn>tp ||(minn==tp && h[ans]<h[i])){
            minn=tp;ans=i;
        }
        //printf("*n");
    //  system("pause");
    }
    printf("%dn",ans);
}
void solve2(int s,ll x0){
    calc1(s,x0,2);
}
void file(){
    freopen("drive.in","r",stdin);
    freopen("drive.out","w",stdout);
}
int main(){
    //file();
    scanf("%d",&n);
    q.insert(-inf);q.insert(inf);
    for(int i=1;i<=n;i++){
        scanf("%lld",&h[i]);
        mp[h[i]]=i;
    }
    pre();//system("pause");
    scanf("%lld",&x0);
    solve1(x0);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int s;ll x;
        scanf("%d%lld",&s,&x);
        solve2(s,x);
    }
    return 0;
}