11
1
2015
1

【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: 498
AP 10th Telugu Model 说:
2022年9月14日 21:39

We advised contacting your Telugu teacher to get a chapter-wise practice model question paper for both levels of exams held under the school or board level and follow the link to download All AP SSC 10th Class Telugu Model Question Papers 2023 with Solutions. Every student everyone can download AP 10th Telugu Model Paper 2023 chapter-wise for paper-1, paper-2 exam theory, objective, AP 10th Telugu Model Paper multiple-choice questions (MCQ), Bit Question Bank with practice study material with IMP Question paper pdf with old scheme suggestions for AP 10th Class students 2023 to the Telugu Subject.


登录 *


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