noip 2012 开车旅行-白红宇

noip 2012 开车旅行

阅读量：5327 次

发布时间：2019-06-14

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

/*考场上写的暴力 40分钟70分*/#include
     
      #include
      
       #include
       
        #define base 1000000000#define maxn 100010#define ll long long using namespace std;ll n,m,h[maxn],X,A[maxn],B[maxn],st,ans;bool falg;double mii=base;ll init(){    ll x=0,f=1;char s=getchar();    while(s<'0'||s>'9'){
   if(s=='-')f=-1;s=getchar();}    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}    return x*f;}ll Abs(ll a){    return a<0?-a:a;}void Get_AB(){    for(int i=1;i<=n;i++)      {          ll mxx,mx,mxxh,mxh,kxx=0,kx=0;mxx=mx=0x7fffffff;          for(int j=i+1;j<=n;j++)            {                ll C=Abs(h[i]-h[j]);                if(C
        
         
          =mxxh)||C
          
           
            limit||(!who&&A[now]==0)||(who&&B[now]==0)) { if(!Bs)tmp=base; else tmp=double(As)/double(Bs); if(tmp
            
             h[ans])) ans=st,mii=tmp; falg=1;return ; } if(!who&&s1<=limit)Dfs(A[now],!who,s1,Bs,limit,S);if(falg)return; if(who&&s2<=limit)Dfs(B[now],!who,As,s2,limit,S);if(falg)return; if(!Bs)tmp=base; else tmp=double(As)/double(Bs); if(tmp
             
              h[ans])) ans=st,mii=tmp; falg=1;return ;}void dfs(ll now,ll who,ll As,ll Bs,ll limit,ll S){ if(falg)return;ll s1=0,s2=0; if(!who)s1=As+Abs(h[now]-h[A[now]]),S+=Abs(h[now]-h[A[now]]); if(who)s2=Bs+Abs(h[now]-h[B[now]]),S+=Abs(h[now]-h[B[now]]); if(S>limit||(!who&&A[now]==0)||(who&&B[now]==0)) { cout<
              
               <<" "<
               
                <

/*暴力的复杂度是n*n的首先预处理每个点的最短次短距离就Tle了这里我们借助set O n 的解决这个问题然后对于每个询问 利用倍增 logn的实现就不超时了 */#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define base 100000000000//大大大大大#define maxn 100010#define ll long long using namespace std;ll n,m,X,A[maxn],B[maxn],As[maxn],Bs[maxn],ans;ll d[maxn][25],f[maxn][25][2];double mii=base;struct point{    ll o,hi;    bool operator < (const point & a) const      {          return hi
          
           s;set
           
            ::iterator pi;ll init(){ ll x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){ if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f;}ll abs(ll a){ return a<0?-a:a;}void Add(point x,point y) { if(!B[x.o]) { B[x.o]=y.o; Bs[x.o]=abs(x.hi-y.hi); } else if(abs(x.hi-y.hi)
            
             
              =1;i--) { s.insert(p[i]); pi=s.find(p[i]); if(pi!=s.begin()) { pi--;Add(p[i],*pi); if(pi!=s.begin()) { pi--;Add(p[i],*pi);pi++; } pi++; } if((++pi)!=s.end()) { Add(p[i],*pi); if((++pi)!=s.end()) Add(p[i],*pi); pi--; } pi--; }}void Query(int st,ll limit,ll & sa,ll & sb){ for(int i=20;i>=0;i--) if(f[st][i][1]+f[st][i][0]<=limit&&d[st][i]) { sa+=f[st][i][0];sb+=f[st][i][1]; limit-=(f[st][i][1]+f[st][i][0]);st=d[st][i]; } if(A[st]&&As[st]<=limit) sa+=As[st];}int main(){ n=init(); for(int i=1;i<=n;i++) { p[i].hi=init();p[i].o=i; } Get_AB(); for(int i=1;i<=n;i++) { d[i][0]=B[A[i]]; f[i][0][0]=As[i]; f[i][0][1]=Bs[A[i]]; } for(int j=1;j<=20;j++) for(int i=1;i<=n;i++) { d[i][j]=d[d[i][j-1]][j-1]; f[i][j][0]=f[i][j-1][0]+f[d[i][j-1]][j-1][0]; f[i][j][1]=f[i][j-1][1]+f[d[i][j-1]][j-1][1]; } X=init(); for(int i=1;i<=n;i++) { ll sa=0,sb=0;double tmp; Query(i,X,sa,sb); if(!sb)tmp=base; else tmp=double(sa)/double(sb); if(tmp
              
               p[ans].hi)) ans=i,mii=tmp; } cout<
               
                <