当前位置:首页 >> 学科竞赛 >>

noip2012 开车旅行 题解


noip2012开车旅行 题解
题目大意:
给出 n 个排成一行的城市, 每个城市有一个不同的海拔。 定义两个城市间的距离等于他 们的高度差的绝对值,且绝对值相等的时候海拔低的距离近。有两个人轮流开车,从左往右 走。 每次都选最近的, 每次都选次近的。 A B 旅行时有一个总路程 x, 如果两个人的总路程>x 或 有一个人无法按照自己的原则选择目的城市,

旅行就终止。 有两个问: 1.给出 x0,求从哪一个城市出发,使得 A 走的路程/B 走的路程最小。如果 B 走的路程 =0,则比值视为无穷大。如果有多个城市满足要求,则输出海拔最高的那个城市。 2.给出 x 和 s(出发城市) ,求旅行终止是 A 的路程和 B 的路程。

题解:
【数据范围】 对于30%的数据,有1≤N≤20,1≤M≤20; 对于40%的数据,有1≤N≤100,1≤M≤100; 对于50%的数据,有1≤N≤100,1≤M≤1,000; 对于70%的数据,有1≤N≤1,000,1≤M≤10,000; 对于100%的数据,有1≤N≤100,000,1≤M≤10,000,-1,000,000,000≤Hi≤1,000,000,000, 0≤X0≤1,000,000,000,1≤S i≤N,0≤Xi≤1,000,000,000,数据保证 Hi 互不相同。

先想骗分。。 。

50分
对于50%的数据还是很好骗的。每次旅行都直接模拟行走,每次找一个最近或次近,时间 O(N*N)。 对于第一问直接枚举起点。时间复杂度为 O(N*N*M + N*N*N)

70分
发现50分算法主要是 每次都要找下一个城市 耗费了太多时间,于是干脆直接预处理, O(N*N),总时间 O(N*M + N*N)

满分
还是想想改进。。70分算法的预处理太傻逼了。 。 。其实我们是要每次找到一个海拔与当前城

市相差最少的城市。所以算法就有很多种了……比如离散化+链表,双向链表,平衡树(其 实用 set 的话程序比双向链表还好打,因为二分 stl 都给你弄好了。) 。 这里主要介绍下双向链表的做法:就是按高度排序,然后链起来。按城市原始位置从左到右 处理接下来的城市是哪个, 然后将自己删掉 (因为接下来就没用了) 如何找接下来的那个? 。 就是往链表的左右两边找两层,记一个最近和次近。 然后预处理就可以优化到 O(N) then??? 发现其实这是一棵树。。 。 于是倍增 预处理已经处理出2^0的情况了。接下来直接动规就好了,就可以预处理出每个点的2^i 的 父亲是谁,以及 A 走了多少,B 走了多少。 then??? 现在问题就是给定总路程要怎么求出 AB 走的路程。 问题可以转化成给定总路程求走了几次。然后就可以用上先前的预处理。假设走了 t 次,则 t 肯定可以表示成二进制,而且只有 logn 位的二进制数。于是可以枚举这一位取0还是1。 调用先前处理的数组,看加上所增加的路程后会不会超出 x,不会就是1,会就是0。 于是问题就完美解决了!

代码(巨丑无比)

//看完后麻烦帮忙下下来棒忙加点财富。。 。。大家也可以加点人品。。 。。

#include <cstdio> #include <algorithm> #include <cstdlib> #include <cmath> #include <map> const int N = 100000 + 9;

struct Link { int nxt,pre; }link[N]; int TOT,n,idx[N]; struct CITY { int h,idx; }city[N]; struct info { int u; long long dis1,dis2; info(const int a = 0,const long long b = 0,const long long c = 0):u(a),dis1(b),dis2(c){} }f[20][N][2]; //0: B //1: A inline bool cmp(const CITY &lhs,const CITY &rhs){return lhs.h < rhs.h;} inline int getnext(const int i,const int t){return i?t:(t^1);} void update(const int i,const int j,const int t) { const int nxt = f[i - 1][j][t].u; const long long dis1 = f[i - 1][j][t].dis1,dis2 = f[i - 1][j][t].dis2; if (nxt) { info tmp; if ((tmp = f[i - 1][nxt][getnext(i - 1,t)]).u) f[i][j][t] = info(tmp.u,dis1 + tmp.dis1,dis2 + tmp.dis2); } } std::pair<int,int> go(int s,long long x) { std::pair<int,int>tmp(0,0); int turn = 1; // A for (int i = TOT; i >= 0; --i) { if (!f[i][s][turn].u) continue; if (x - f[i][s][turn].dis1 - f[i][s][turn].dis2 < 0) continue; x -= f[i][s][turn].dis1 + f[i][s][turn].dis2; tmp.first += f[i][s][turn].dis2; tmp.second += f[i][s][turn].dis1; turn = getnext(i,turn); s = f[i][s][turn].u; } return tmp;

} inline void check(const int id_p,const int id_n,int &Min_h1,int &Min_i1,int &Min_h2,int &Min_i2) { if (!id_n) return; const int dis = std::abs(city[id_p].h - city[id_n].h); if (dis < Min_h1 || dis == Min_h1 && city[id_n].h < city[Min_i1].h) { Min_h2 = Min_h1; Min_i2 = Min_i1; Min_h1 = dis; Min_i1 = id_n; }else if (dis < Min_h2 || dis == Min_h2 && city[id_n].h < city[Min_i2].h) { Min_h2 = dis; Min_i2 = id_n; } } inline long long cmp2(const std::pair<int,int>lhs,const std::pair<int,int>rhs) { if (!lhs.second && !rhs.second) return 0; else if (!lhs.second) return 1; else if (!rhs.second) return -1; else return 1ll * lhs.first * rhs.second - 1ll * rhs.first * lhs.second; } int main() { #ifndef ONLINE_JUDGE freopen("drive.in","r",stdin); freopen("drive.out","w",stdout); #endif scanf("%d",&n); for (int i = 1; i <= n; ++i) { scanf("%d",&city[i].h); city[i].idx = i; } std::sort(city + 1,city + 1 + n,cmp); for (int i = 1; i < n; ++i) { link[i].nxt = i + 1; link[i + 1].pre = i ; idx[city[i].idx] = i; } idx[city[n].idx] = n; for (int i = 1; i <= n; ++i) { int id = idx[i],Min_h1 = 0x7fffffff,Min_i1 = 0,Min_h2 =

0x7fffffff,Min_i2 = 0; check(id,link[id].pre, check(id,link[id].nxt, Min_h1, Min_i1, Min_h2, Min_i2); Min_h1, Min_i1, Min_h2, Min_i2);

check(id,link[link[id].pre].pre, Min_h1, Min_i1, Min_h2, Min_i2); check(id,link[link[id].nxt].nxt, Min_h1, Min_i1, Min_h2, Min_i2); f[0][i][0] = info(city[Min_i1].idx,Min_h1,0); f[0][i][1] = info(city[Min_i2].idx,0,Min_h2); if (link[id].nxt) link[link[id].nxt].pre = link[id].pre; if (link[id].pre) link[link[id].pre].nxt = link[id].nxt; } TOT = static_cast<int>(ceil(log2((double)n))); for (int i = 1; i <= TOT; ++i) for (int j = 1; j <= n; ++j) { update(i,j,0); update(i,j,1); } int x; scanf("%d",&x); std::pair<int,int>ans; int ans_pos = 0; ans.first = 1; ans.second = 0; for (int i = 1; i <= n; ++i) { std::pair<int,int>tmp = go(i,x); if (cmp2(tmp,ans) < 0) { ans = tmp; ans_pos = i; }else if (cmp2(tmp,ans) == 0 && city[idx[ans_pos]].h < city[idx[i]].h) { ans = tmp; ans_pos = i; } } printf("%d\n",ans_pos); int m; scanf("%d",&m); for (int i = 1,x,s; i <= m; ++i) { scanf("%d%d",&s,&x); std::pair<int,int> tmp = go(s,x); printf("%d %d\n",tmp.first,tmp.second); } }


相关文章:
noip2012 开车旅行 题解
noip2012 开车旅行 题解_学科竞赛_高中教育_教育专区。noip2012开车旅行 题解题目大意:给出 n 个排成一行的城市, 每个城市有一个不同的海拔。 定义两个城市间...
Noip2012普及组题解
Noip2012普及组题解_学科竞赛_初中教育_教育专区。noip的题解 质因数分解 (prime.cpp/c/pas) 【问题描述】 已知正整数n是两个不同的质数的乘积,试求出较大...
noip 2012 提高组 解题报告
noip 2012 提高组 解题报告_学科竞赛_高中教育_教育专区。noip 2012 提高组 ...开车旅行链表+倍增按城市高度递增顺序排序,放到链表中 从第一个城市起,找离它...
noip2012疫情控制题解
noip2012疫情控制题解_学科竞赛_高中教育_教育专区。noip2012疫情控制 题解题目大意...noip2012 开车旅行 题解 5页 免费 疾病控制大计划 暂无评价 6页 免费 疾病...
NOIP2012问题求解题目
[i]) 如果根节点不选,则与根节点无关,直接为左右儿子的相乘,有 g(i)...(计算的时候是从下往上算,这里设树的节点总数为 根节点编号),显然该就是...
2012全国信息学奥林匹克联赛提高第一天试题
全国信息学奥林匹克联赛(NOIP2012) 提高组第一天...9 3.开车旅行 (drive.cpp/c/pas) 【问题描述】...(注意:本题中如果当前城市到两个城市的距离相同,则...
NOIP2012普及组初赛试题和参考答案
NOIP2012普及组初赛试题和参考答案_IT认证_资格考试/...而原问题的解就是子问题解的并。 A.动态规划 B....(共 4 题,每题 8 分,共计 32 分) 1. var ...
NOIp06-15题解分析
(但是考场上可以猜、试 出贪心规则) 3.开车旅行:倍增+递推。 4.同余方程:...。其实搜索也能过吧 noip2012 day1 题 1:字符串模拟 题 2:数学推导能力+...
NOIP2012普及组复赛解题报告
NOIP2012普及组复赛解题报告_学科竞赛_初中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 NOIP2012普及组复赛解题报告_学科竞赛_初中教育_教育专区。第一题:...
冲刺CCF NOIP2012模拟试题与解析(普及组)
冲刺CCF NOIP2012模拟试题与解析(普及组)_电脑基础知识_IT/计算机_专业资料。冲刺...Noip2012普及组题解 5页 免费 NOIP2012普及组初赛及答... 9页 免费 CCF NO...
更多相关标签:
noip2012开车旅行 | 开车旅行 noip | 观光旅行 noip | noip2012提高组复赛 | noip2012普及组复赛 | noip2012疫情控制 | noip2012提高组初赛 | noip2012 |