NOIP2012 开车旅行 (倍增)

2024-06-11 13:32
文章标签 倍增 旅行 noip2012 开车

本文主要是介绍NOIP2012 开车旅行 (倍增),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题意:一行N个城市,有各自不同的海拔,定义两个城市之间的距离为海拔之差的绝对值,小a和小b轮流开车,开车方向从左往右,小a总是开到第二近的城市,小b开到最近的城市(如有两个城市和当前城市海拔之差相等,海拔低的更近)。当其中任一人无法按照自己的方案前进或前进后总路程超过一个上限,旅行结束。一,给定一个路程上限x0,求从哪个城市出发A和B路程比值最小,这里规定任意数比零等于无穷大,比值相等输出海拔最高的。二,给出M组询问,每组给出出发城市s和路程上限x,求A和B的路程。N<=100000,M<=10000.

最直观的思路应该是先N^2预处理在每个城市,a和b的目标是哪里,然后再O(NM)地回答询问。看一下数据范围,70分N<1000, 这个暴力的得分是相当可观的。在考场上最好不管三七二十一先写出来,因为很明显这道题并不是针对某一个成型的算法出的,正解肯定是在这个暴力基础上优化。

先观察一下这个暴力的复杂度O(N^2+MN),如果要过这道题,显然两项都要优化。对于第一项,优化比较好办,倒序扫描,将每个城市压入平衡树,对于每个海拔求一下前驱后继就行了,降为nlogn(在下无能,实在想不出类似于排序扫描之类的更优的方法)。

然后第二个环节,不难发现在每个城市,每个人的目标都各自是固定的,实现时就可以将两个人一起开一轮绑定在一起,这样一来每个城市的后两个,三个等等的目标城市都是固定的,这提示我们可以处理每个城市后面相距多个轮回的城市以加速算法。对于这种问题,比较经典的想法就是倍增(logn)或者分块(sqrt(n))。

个人感觉分块是更好写的,假设N=100000,sqrt(N)约等于350,我们就处理出每个点之后第350个城市是哪个,然后就是经典的两行代码:while(x>350)x-=350,city=next350[city],a+=..., b+=...; while(x>0)x--,city=next1[city],x+=..., b+=...;(当然实际操作中还要处理是a开车还是b开车,是否城市走完了路程限制还没消耗完这些细节)两个循环次数都在350以内,足以过最大数据了。当然,这个350只是个例子,实际操作中取根号n即可(就取350当然也不会超时。。)。

当然,分块的目的只是为了多得点分甚至水过这道题,最正统的当然还是倍增了,处理每个城市第2^k个目标点,循环的时候,指数从大到小枚举即可保证二进制位能够凑成原来的整数。但是如果实现得不是很好(向我这种),倍增完了往往到不了目标点,还需要特判并且手动往后走一下。

这题虽然理论上路程之和完全会超int,然而实践int可以过,不需要开long long,CCF真是良心数据。但是考场上一定要开long long,不能被NOIP的数据惯坏了(永远不会忘记CQOI2015送分裸题爆零的经历)。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
using namespace std;
#define dis(i,j) (h[i]>h[j] ? h[i]-h[j] : h[j]-h[i])
const int MAXN = 100010;
int N, M, LG;
int h[MAXN];
int nextb[MAXN], nexta[MAXN];
#define _next(t) nextb[nexta[t]]
int ans[MAXN][2];struct City {int h, id;City(){}City(int x,int y){h=x; id=y;}bool operator < (const City&t1) const {return h < t1.h;}
};set<City> S;
set<City>::iterator it1, it2, bst;
void FindNear()//用set很容易RE,一定要多对拍一下
{nextb[N-1] = N;S.insert(City(h[N], N));S.insert(City(h[N-1], N-1));for (int i = N-2; i>0; --i){City tmp = City(h[i], i), tmp2;it1 = S.lower_bound(tmp);if (it1 == S.end()) {--it1; nextb[i] = it1->id;--it1; nexta[i] = it1->id;S.insert(tmp);continue;}if (it1 != S.begin()) {it2 = it1; --it1;if (it2->h - h[i] < h[i] - it1->h) nextb[i] = it2->id, bst = it2;else nextb[i] = it1->id, bst = it1;}else {nextb[i] = it1->id;++it1; nexta[i] = it1->id;S.insert(tmp); continue;}tmp2 = *bst;S.erase(bst);it1 = S.lower_bound(tmp);if (it1 == S.end()) { --it1; nexta[i] = it1->id; }else {if (it1 != S.begin()) {it2 = it1; --it1;if (it2->h - h[i] < h[i] - it1->h) nexta[i] = it2->id;else nexta[i] = it1->id;}else nexta[i] = it1->id;}S.insert(tmp2);S.insert(tmp);}
}int adis[MAXN][20], bdis[MAXN][20];
int dest[MAXN][20];
void Prepare()
{int i, j;for (LG=1; 2*(1<<LG)<=N; ++LG) ;for (i = 1; i<=N; ++i) {adis[i][0] = nexta[i] ? dis(i, nexta[i]) : 0;bdis[i][0] = _next(i) ? dis(nexta[i], _next(i)) : 0;dest[i][0] = _next(i);}for (i = 1; i<=LG; ++i)for (j = 1; j<=N; ++j) {dest[j][i] = dest[ dest[j][i-1] ][i-1];adis[j][i] = adis[j][i-1] + adis[ dest[j][i-1] ][i-1];bdis[j][i] = bdis[j][i-1] + bdis[ dest[j][i-1] ][i-1];}
}void drive(int s, int len, int& xa, int& xb)
{xa = xb = 0;int cur = s;for (int i = LG; i>=0; --i)if (dest[cur][i] && adis[cur][i]+bdis[cur][i]<=len) {xa += adis[cur][i];xb += bdis[cur][i];len -= adis[cur][i] + bdis[cur][i];cur = dest[cur][i];}while (1) {if (dis(nexta[cur], cur)>len || !nexta[cur]) break;xa += dis(nexta[cur], cur);len -= dis(nexta[cur], cur);cur = nexta[cur];if (dis(nextb[cur], cur)>len || !nextb[cur]) break;xb += dis(nextb[cur], cur);len -= dis(nextb[cur], cur);cur = nextb[cur];}
}int X0;
const double eps = 1e-6, DINF = 1e12;//不卡精度,double可水过
int task1()
{double best = DINF, cur;int res=0, i, xa, xb;for (i = 1; i<=N; ++i) {drive(i, X0, xa, xb);if (xb == 0 && best>=DINF-eps) {if (h[i] > h[res]) res = i;continue;}cur = (double)xa / (double)xb;if (cur < best-eps) best=cur, res=i;else if (cur>=best-eps && cur<=best+eps && h[i]>h[res])best = cur, res = i;}return res;
}int main()
{int i, s, len, xa, xb;scanf("%d", &N);for (i = 1; i<=N; ++i)scanf("%d", &h[i]);FindNear();Prepare();scanf("%d%d", &X0, &M);for (i = 1; i<=M; ++i){scanf("%d%d", &s, &len);drive(s, len, xa, xb);ans[i][0] = xa;ans[i][1] = xb;}printf("%d\n", task1());for (i = 1; i<=M; ++i)printf("%d %d\n", ans[i][0], ans[i][1]);return 0;
}


这篇关于NOIP2012 开车旅行 (倍增)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1051304

相关文章

如何限制与管控员工上网行为?四个方法让员工效率倍增!【企业员工上网行为管理】

在信息化时代,员工的上网行为直接影响着工作效率和企业的安全性。不当的网络使用,如浏览与工作无关的网站、下载不安全的文件,可能导致工作效率低下,甚至引发安全风险。因此,许多企业正在积极寻找有效的措施来管控员工的上网行为,以确保工作效率的提升。 以下是四个常见且有效的员工上网行为管理方法,帮助企业实现更高效的网络管理。 方法一:配置网络防火墙进行访问限制 最基础的员工上网行为管理方法是通过配置防

社交平台找旅游搭子一起旅行靠谱吗?答案是不要太爽!

哈喽小伙伴们,今天要跟大家分享一个超级棒的小程序——咕哇找搭子!作为一个热爱自由行的人,最头疼的就是找不到志同道合的小伙伴。但自从用了这个咕哇小程序后,一切都变得简单又充满乐趣啦!🎉 上个月,我计划去云南旅行,就试着在咕哇上发布了我的行程信息。没想到很快就收到了几位朋友的回应,其中一位叫小莲的朋友特别投缘。我们不仅目的地一样,就连兴趣爱好都出奇地相似,于是我们就决定一起出发啦!👭

旅行商问题 | Matlab基于混合粒子群算法GA-PSO的旅行商问题TSP

目录 效果一览基本介绍建模步骤程序设计参考资料 效果一览 基本介绍 混合粒子群算法GA-PSO是一种结合了遗传算法(Genetic Algorithm, GA)和粒子群优化算法(Particle Swarm Optimization, PSO)的优化算法。在解决旅行商问题(Traveling Salesman Problem, TSP)时,这种混合算法可以结合两种算法的优点

P4842 城市旅行(拆贡献 + LCT)

https://www.luogu.com.cn/problem/P4842 发现题目就是要维护一个LCT,然后我们只要把pushup写成功了就行。 那我们现在就不管LCT了,就单纯想用一棵二叉查找树怎么维护。分母是好搞的,分子我们要想点办法。 考虑右子树对左子树的贡献,我们假设处理出一个 L [ k ] L[k] L[k] 表示左子树中每个值乘以左边界的可选数量,我们现在再乘上右子树的大

P3313 [SDOI2014] 旅行(分块做法)

~~~~~      P3313 [SDOI2014] 旅行 ~~~~~      总题单链接 思路 ~~~~~      遇到这种树上路径问题,就考虑用重链剖分转为区间问题。 ~~~~~      问题转换为了:给定一个区间和 k k k,求这个区间内信仰为 k k k 的城市的 权值和 或 最大权值。 ~~~~~      这个问题也可以用动态开点线段树解决(现在不会,以后

双轨直销模式:团队互助与业绩倍增的商业策略

双轨直销模式因其操作简单、业绩压力较小、管理方便以及初期爆发力强等特点,受到许多直销公司的喜爱,并促进了多家大型企业的成长。 一、双轨直销模式简介 双轨直销是一种独特的组织架构,其核心在于每个销售代表仅需构建两个独立的销售线,分别用A和B来表示。随着销售网络的不断扩展,形成一个庞大的销售网络体系。 当第三位销售代表C加入时,他或她必须选择加入A或B的销售线,而不是创建新的线。这种机制

旅行追踪和行程规划工具AdventureLog

什么是 AdventureLog ? AdventureLog 是一种记录您的旅行并与世界分享的简单方法。您可以在日志中添加照片、笔记等。跟踪您访问过的国家、探索去过的地区和地方。您还可以查看您的旅行统计数据和里程碑。AdventureLog 旨在成为您终极的旅行伴侣,帮助您记录您的冒险经历并轻松规划新的冒险经历。 主要功能: 使用姓名、日期、地点、描述和评级等字段记录过去的冒险经

BZOJ 3732: Network(最小生成树+倍增)

题目链接 题意:给出一个图,每个询问的格式是:A B,表示询问从A点走到B点的所有路径中,最长的边最小值是多少 很明显最终查询的边一定是在最小生成树里面的,先跑出最小生成树,然后,可以树链剖分,也可以使用倍增来计算 #include<bits/stdc++.h>using namespace std;#define cl(a,b) memset(a,b,sizeof(a))#define

PHP指尖上的旅行管家手边酒店民宿预订系统小程序源码

指尖上的旅行管家——手边酒店民宿预订系统🌟🛫 🚀 开篇:旅行新伴侣,轻松启程 每次计划旅行,是不是都曾为找酒店、订民宿而头疼不已?🤔 繁琐的搜索、对比、预订流程,让美好的旅程还没开始就有点疲惫了呢。但现在,有了“手边酒店民宿预订系统”,一切都变得不一样了!🎉 它就像是你指尖上的旅行管家,随时待命,为你打造无忧的出行体验。 📱 一键操作,全球住宿尽在掌握 只需轻轻一点,手

1570C 旅行

题目描述 Tom和Alice结婚一段时间了,感情非常好,一天他们相约去旅行,终点在遥远的地方。        地形是非常复杂的,路途是非常曲折的。但我们简化一下是一个矩阵。起点也就是他们家在矩阵的左下角,终点也就是他们要去的遥远的地方在右上角,矩阵行列的交点是他们可以驻足的地方,但是有的却是陷阱,他们是不能从那里通过的。Tom要听Alice的,只会往上或往右走,不往回走,直到终点。