协议书 > 开车 > 开车旅行 >

noip2012开车旅行

时间: 试工2 开车旅行

noip2012开车旅行

  下面是学习啦小编为大家整理的noip2012开车旅行解题报告

  狠经典的倍增题了(虽然以前没有接触过,NOIP2013的倍增也没搞出来,不过倍增算法很好理解,我看了大概算法后代码都是自己写的)

  先预处理出每个城市的最近与次近,可以用C++STL的set。

  然后令g[i][j]为从i点走2^j个轮回(注意是轮回,不是步)后的位置,f[i][j][0]为从i点走2^j个轮回后A走过的距离,f[i][j][1]为从i点走2^j个轮回后B走过的距离。

  那么很容易推出:

  g[i][j]=g[g[i][j-1]][j-1];

  f[i][j][0]=f[i][j-1][0]+f[g[i][j-1]][j-1][0];

  f[i][j][1]=f[i][j-1][0]+f[g[i][j-1]][j-1][1];

  第一个询问就可以O(n)搞出来了(注意无穷大的情况),第二个询问也是O(m)的。

  询问的具体做法就是将路径从长到短枚举一遍看是否会走(类似于二进制的思想),要特判A走后B无法再走的情况。

  #include

  using namespace std;

  const int maxn=100000+10;

  typedef long long LL;

  struct City

  {

  int h,num;

  bool operator < (const City rhs) const

  {

  return h

  }

  }h[maxn];

  set S;

  set::iterator it;

  int n,x0,m,next[maxn][2],dist[maxn][2],g[maxn][21];

  LL f[maxn][21][2];

  inline void update(City x,City y)

  {

  if(!next[x.num][0])

  {

  next[x.num][0]=y.num;

  dist[x.num][0]=abs(x.h-y.h);

  }

  else if(abs(x.h-y.h)

  {

  next[x.num][1]=next[x.num][0];

  dist[x.num][1]=dist[x.num][0];

  next[x.num][0]=y.num;

  dist[x.num][0]=abs(x.h-y.h);

  }

  else if(abs(x.h-y.h)

  {

  next[x.num][1]=y.num;

  dist[x.num][1]=abs(x.h-y.h);

  }

  else if(!next[x.num][1])

  {

  next[x.num][1]=y.num;

  dist[x.num][1]=abs(x.h-y.h);

  }

  return;

  }

  inline void query(int s,int x,LL& dista,LL& distb)

  {

  for(int i=20;i>=0;i--)

  if(f[s][i][0]+f[s][i][1]<=x&&g[s][i])

  {

  dista+=f[s][i][0];

  distb+=f[s][i][1];

  x-=f[s][i][0]+f[s][i][1];

  s=g[s][i];

  }

  if(next[s][1]&&dist[s][1]<=x)

  dista+=dist[s][1];

  }

  int main()

  {

  scanf("%d",&n);

  for(int i=1;i<=n;i++)

  {

  scanf("%d",&h[i].h);

  h[i].num=i;

  }

  for(int i=n;i;i--)

  {

  S.insert(h[i]);

  it=S.find(h[i]);

  if(it!=S.begin())

  {

  it--;

  update(h[i],*it);

  if(it!=S.begin())

  {

  it--;

  update(h[i],*it);

  it++;

  }

  it++;

  }

  if((++it)!=S.end())

  {

  update(h[i],*it);

  if((++it)!=S.end())

  update(h[i],*it);

  it--;

  }

  it--;

  }

  for(int i=1;i<=n;i++)

  {

  g[i][0]=next[next[i][1]][0];

  f[i][0][0]=dist[i][1];

  f[i][0][1]=dist[next[i][1]][0];

  }

  for(int j=1;j<=20;j++)

  for(int i=1;i<=n;i++)

  {

  g[i][j]=g[g[i][j-1]][j-1];

  f[i][j][0]=f[i][j-1][0]+f[g[i][j-1]][j-1][0];

  f[i][j][1]=f[i][j-1][1]+f[g[i][j-1]][j-1][1];

  }

  scanf("%d",&x0);

  int s0=0;

  LL a=1e15,b=0;

  for(int i=1;i<=n;i++)

  {

  LL dista=0,distb=0;

  query(i,x0,dista,distb);

  if(distb&&(!s0||a*distb>b*dista))

  {

  s0=i;

  a=dista;

  b=distb;

  }

  }

  printf("%d\n",s0);

  scanf("%d",&m);

  while(m--)

  {

  int s,x;

  scanf("%d%d",&s,&x);

  LL dista=0,distb=0;

  query(s,x,dista,distb);

  printf("%lld %lld\n",dista,distb);

  }

  return 0;

  }

5521