noip2012開車旅行
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
set
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;
}