开车旅行-白红宇

开车旅行

阅读量：4332 次

发布时间：2019-06-06

本文共 5833 字，大约阅读时间需要 19 分钟。

真真一道倍增好题。

先说70分思路

我的：

从后边的城市往前跑，这样就能\(n^2\)时间内得到从城市\(i\)到城市\(j\)的路程了。........反正超级麻烦，最后也没写出来。后来想想最直接的暴力好像是\(n*m\)，70分也能过。

代码估计以后也看不懂了。。。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        using namespace std;const int N = 1005;const int inf = 2147483647;map
         
          
            >mp;int n,h[N],m,s[N],x[N],x0,dis[1005][1005],dist[N],dis1[N][2];int head[N],tot,maxx[N][21],min1,min2,id1[N],id2[N];int head1[N],tot1,disa[1005][1005][2],disb[1005][1005][2],ansxo;struct edge{ int node,next,data;}e[N<<1],e1[N<<1];struct node{ int tmp[N];}a[N];void add(int x,int y){ e[++tot].node=y; e[tot].next=head[x]; head[x]=tot; }void add1(int x,int y){ e1[++tot1].node=y; e1[tot1].next=head1[x]; head1[x]=tot1; }inline int read(){ char c=getchar(); int ans=0,w=1; while((c<'0'||c>'9')&&c!='-') c=getchar(); if(c=='-') { w=-1;c=getchar(); } while(c>='0'&&c<='9') { ans=ans*10+c-'0'; c=getchar(); } return ans*w; }void dfs(int t,int u,int ft,int flag,int lena,int lenb){// if(u==1) return ; if(flag) { for(int i=head[u];i;i=e[i].next) { int v=e[i].node; disa[v][t][ft]=lena+e[i].data; disb[v][t][ft]=lenb; a[v].tmp[t]=disa[v][t][ft]+disb[v][t][ft]; mp[v][a[v].tmp[t]]=t; dfs(t,v,ft,0,lena+e[i].data,lenb); } } else { for(int i=head1[u];i;i=e1[i].next) { int v=e1[i].node; dfs(t,v,ft,1,lena,lenb+e1[i].data); } }} double chu(int a,int b){ if(b==0) return 2e9; return a/b;}int main(){// memset(min1,0x3f,sizeof(min1));// memset(min2,0x3f,sizeof(min2)); n=read(); for(int i=1;i<=n;i++) h[i]=read(); x0=read(); m=read(); for(int i=1;i<=m;i++) s[i]=read(),x[i]=read(); for(int i=1;i<=n;i++) { min1=min2=inf;// id1=n+1,id2=n+1; for(int j=i+1;j<=n;j++) { dis[i][j]=abs(h[i]-h[j]); if(dis[i][j]==min1&&) { if(h[j]
           
            >1; if(a[i].tmp[mid]<=x0) l=mid+1,ansp=mid; else r=mid-1; } int tt=mp[i][a[i].tmp[ansp]]; if(chu(disa[i][tt],disb[i][tt])

\(llfz\)的：

最最暴力的解法。以每个点为起点，进行\(dfs\)。但是这么简单的思路在调试时还是出现了很多错误。导致第一次提交只有15分。

错点：

初始化漏掉情况（\(min1\)表示最近\(min2\)表示次近，\(id1\)和\(id2\)分别记录最近和次近的编号，\(dis[i][j]\)暂且表示城市\(i\)到城市\(j\)的距离）

1.有相等的情况

与\(min1\)相等
分海拔与\(id1\)比较的两种情况
如果海拔比\(id1\)高，还要与\(id2\)比较海拔，不能直接赋值。万一\(min1==min2\)且\(id2\)的海拔更低呢。

2.没有相等的情况

这个比较简单，先比较\(min1\)再比较\(min2\)就行了。

更新答案时漏掉情况。

如果小B走的距离是0,也有可能更新答案。注意，这次是选海拔高的城市。

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;const int N = 1005;const int inf = 2e9;int n,h[N],x0,m,s[10*N],x[10*N],st;int min1=inf,min2=inf,id1[N],id2[N];double ans=2e9;bool book;void dfs1(int u,int flag,int s1,int s2,int xp){    if(book) return ;    if(u==n)    {        book=1;        printf("%d %d\n",s1,s2);        return ;    }    if(u==n-1&&flag)    {        book=1;        printf("%d %d\n",s1,s2);        return ;    }    if(flag)    {        if(abs(h[u]-h[id2[u]])+s1+s2>xp)        {            book=1;            printf("%d %d\n",s1,s2);            return ;        }        dfs1(id2[u],0,s1+abs(h[u]-h[id2[u]]),s2,xp);    }    else    {        if(abs(h[u]-h[id1[u]])+s1+s2>xp)        {            book=1;            printf("%d %d\n",s1,s2);            return ;        }        dfs1(id1[u],1,s1,s2+abs(h[u]-h[id1[u]]),xp);    }}double dfs(int begin,int u,int flag,int s1,int s2,int xp){    if(u==n)    {        if(s2==0) return 2e9;        else return (double)s1/s2;/*      if(s2==0) return ;//      if(s2==0&&h[begin]>h[st]&&ans==(double)2e9) { st=begin; return ;}        if((double)(s1/s2)==ans&&h[begin]>h[st])          st=begin;        if((double)(s1/s2)
        
         h[st]&&ans==(double)2e9) { st=begin; return ;}        if((double)(s1/s2)==ans&&h[begin]>h[st])          st=begin;        if((double)(s1/s2)
         
          xp) { if(s2==0) return 2e9; else return (double)s1/s2;/* if(s2==0) return ;// if(s2==0&&h[begin]>h[st]&&ans==(double)2e9) { st=begin; return ;} if((double)(s1/s2)==ans&&h[begin]>h[st]) st=begin; if((double)(s1/s2)
          
           xp) { if(s2==0) return 2e9; else return (double)s1/s2;/* if(s2==0) return ;// if(s2==0&&h[begin]>h[st]&&ans==(double)2e9) { st=begin; return ;} if((double)(s1/s2)==ans&&h[begin]>h[st]) st=begin; if((double)(s1/s2)
           
            abs(h[i]-h[j])) min2=abs(h[i]-h[j]),id2[i]=j; } continue; } if(min2==abs(h[i]-h[j])) { if(h[j]
            
             abs(h[i]-h[j])) { min2=min1; id2[i]=id1[i]; min1=abs(h[i]-h[j]); id1[i]=j; } else if(min2>abs(h[i]-h[j])) min2=abs(h[i]-h[j]),id2[i]=j; } } for(int i=1;i<=n;i++) { double t=dfs(i,i,1,0,0,x0); if(t
             
              h[st]) { ans=t,st=i;} } printf("%d\n",st); for(int i=1;i<=m;i++) { book=0; dfs1(s[i],1,0,0,x[i]); } return 0;}

果然还是\(llfz\)强。

正解

对于每个点来说，以它为起点的路径是唯一的。用\(f[i][j]\)表示从第\(i\)点开始向后\(2*2^j\)步到达的点，同样\(sta[i][j]\)和\(stb[i][j]\)记录小A和小B走的路径长度。

看的大佬的这篇

以后好好复习代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define LL long longusing namespace std;const int N = 100005;int n,m,l,r,j;struct node{    int i,v,l,r;    bool friend operator < (const node& a,const node& b){        return a.v
         
          =0;i--) { if(f[p][i]&&(LL)(a+b+sta[p][i]+stb[p][i])<=x) { a+=sta[p][i]; b+=stb[p][i]; p=f[p][i]; } } if(na[p]&&a+b+sta[p][0]<=x) a+=sta[p][0];} int main(){ LL x; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&d[i].v); for(int i=1;i<=n;i++) d[i].i=i; sort(d+1,d+n+1); for(int i=1;i<=n;i++) p[d[i].i]=i;//p[i]表示编号为i的城市当前在的位置 for(int i=1;i<=n;i++) d[i].l=i-1,d[i].r=i+1; d[1].l=d[n].r=0; for(int i=1;i<=n;i++) { j=p[i]; l=d[j].l; r=d[j].r; if(zuo()) nb[i]=d[l].i,na[i]=pd(d[l].l,r); else nb[i]=d[r].i,na[i]=pd(l,d[r].r); if(l) d[l].r=r; if(r) d[r].l=l; } for(int i=1;i<=n;i++) { f[i][0]=nb[na[i]];//小A先走，走到na[i]，然后小B再走，走到nb[na[i]] sta[i][0]=abs(d[p[i]].v-d[p[na[i]]].v); stb[i][0]=abs(d[p[f[i][0]]].v-d[p[na[i]]].v); } make_st(); scanf("%lld%d",&x,&m); for(int i=1;i<=n;i++) { getab(x,i); if(b&&1.0*a/b

全靠代码占长度。。。

转载于:https://www.cnblogs.com/karryW/p/11405774.html

你可能感兴趣的文章