11
1
2015
0

【map预处理+倍增优化傻逼模拟】

CODEVS 1199: 开车旅行

Time Limit: 1 Sec  Memory Limit: 128 MB

Description

小A和小B决定利用假期外出旅行,他们将想去的城市从1到N 编号,且编号较小的城市在编号较大的城市的西边,已知各个城市的海拔高度互不相同, 记城市 i的海拔高度为Hi,城市 i 和城市 j 之间的距离 d[i,j]恰好是这两个城市海拔高度之差的绝对值,即 d[i, j] = |Hi − Hj|。

旅行过程中,小A 和小B轮流开车,第一天小A 开车,之后每天轮换一次。他们计划选择一个城市 S 作为起点,一直向东行驶,并且最多行 驶 X 公里就结束旅行。小 A 和小B的驾驶风格不同,小 B 总是沿着前进方向选择一个最近的城市作为目的地,而小 A 总是沿着前进方向选择第二近 的城市作为目的地(注意:本题中如果当前城市到两个城市的距离相同,则认为离海拔低的那个城市更近)。如果其中任何一人无法按照自己的原则选择目的城市, 或者到达目的地会使行驶的总距离超出X公里,他们就会结束旅行。

在启程之前,小A 想知道两个问题:

1.对于一个给定的 X=X0,从哪一个城市出发,小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小(如果小 B的行驶路程为0,此 时的比值可视为无穷大,且两个无穷大视为相等)。如果从多个城市出发,小A 开车行驶的路程总数与小B行驶的路程总数的比值都最小,则输出海拔最高的那个 城市。

2.对任意给定的 X=Xi和出发城市 Si,小 A 开车行驶的路程总数以及小 B 行驶的路程总数。

Input

第一行包含一个整数 N,表示城市的数目。

第二行有 N 个整数,每两个整数之间用一个空格隔开,依次表示城市 1 到城市 N 的海拔高度,即H1,H2,……,Hn,且每个Hi都是不同的。

第三行包含一个整数 X0。

第四行为一个整数 M,表示给定M组Si和 Xi。

接下来的M行,每行包含2个整数Si和Xi,表示从城市 Si出发,最多行驶Xi公里。

Output

输出共M+1 行。

第一行包含一个整数S0,表示对于给定的X0,从编号为S0的城市出发,小A开车行驶的路程总数与小B行驶的路程总数的比值最小。

接下来的 M 行,每行包含 2 个整数,之间用一个空格隔开,依次表示在给定的 Si和Xi下小A行驶的里程总数和小B 行驶的里程总数。

 

先黑一个:开军旅行

大概因为两个人轮流艹做,很难想到倍增处理吧

但是说白了移动就是在一棵固定的树上跑罢了。

然后就能随手写了对不对w

倒是预处理不会机智的写法,map乱搞求指导:

SBCode:

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#define INF 5000000000LL
#define maxn 100010
using namespace std;
typedef long long LL;
LL H[maxn];
int n,TO[maxn][2],m;
int lca[maxn][19];
LL SA[maxn][19],SB[maxn][19];
map <int,LL>mp;
set <LL> S;
typedef set <LL> ::iterator ITER;
LL K[4];
LL Abs(LL a){return a<0?-a:a;}
int cmp(int a,int b)
{
	return abs(a)<abs(b);
}
double GG(int s,LL x,LL &sa,LL &sb)
{
	sa=sb=0;
	for (int j=18;j>=0;j--)
		if (lca[s][j]&&sa+sb+SA[s][j]+SB[s][j]<=x) sa+=SA[s][j],sb+=SB[s][j],s=lca[s][j];
	if (sb==0) return INF;
	return (double)sa/(double)sb;
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%lld",&H[i]),mp[H[i]]=i;
	S.insert(H[n]);
	for (int i=n-1;i>=1;i--)
	{
		int l=0;
		ITER a=S.lower_bound(H[i]),b=S.upper_bound(H[i]);
		if (a!=S.begin()) a--,K[l++]=H[i]-(*a);
		if (a!=S.begin()) a--,K[l++]=H[i]-(*a);
		if (b!=S.end()) K[l++]=H[i]-(*b),b++;
		if (b!=S.end()) K[l++]=H[i]-(*b),b++;
		stable_sort(K,K+l,cmp);
		TO[i][1]=mp[H[i]-K[0]];
		if (l>1) TO[i][0]=mp[H[i]-K[1]];
		S.insert(H[i]);
	}
	for (int i=1;i<=n;i++) 
		lca[i][0]=TO[i][0],SA[i][0]=Abs(H[i]-H[TO[i][0]]);
	for (int i=1;i<=n;i++) 
		lca[i][1]=TO[lca[i][0]][1],SA[i][1]=SA[i][0],SB[i][1]=Abs(H[lca[i][0]]-H[lca[i][1]]);
	for (int j=2;j<=18;j++)
		for (int i=1;i<=n;i++)
			if (lca[lca[i][j-1]][j-1]) 
				lca[i][j]=lca[lca[i][j-1]][j-1],
				SA[i][j]=SA[i][j-1]+SA[lca[i][j-1]][j-1],
				SB[i][j]=SB[i][j-1]+SB[lca[i][j-1]][j-1];
	LL x0,sa,sb,ans;
	double mn=1e60;
	scanf("%lld",&x0);
	for (int i=1;i<=n;i++)
	{
		double t=GG(i,x0,sa,sb);
		if (t<mn||(t==mn&&H[i]>H[ans]))mn=t,ans=i;
	}
	printf("%lld\n",ans);
	scanf("%d",&m);
	for (int i=1;i<=m;i++)
	{
		int s;LL x;
		scanf("%d%lld",&s,&x);
		GG(s,x,sa,sb);
		printf("%lld %lld\n",sa,sb);
	}
	return 0;
}
Category: NOIP | Tags: map 倍增 NOIP 模拟 | Read Count: 244

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com