【NOIP2012提高组】开车旅行
2024-10-20 07:47:31
题目
到处都有
闲话
碰巧考场上出了 \(Noip\) 原题
然后这题自然而然想到
预处理一个点开始分别由 \(A，B\) 驾驶会走到的下一个点
然后用预处理的数组求答案
当然你会发现 \(X=X0\) 这一问和后面的问的解法没什么区别
这都不是重点
\(ccf\) 很良心给暴力 \(70\) 分
然后 \(100\) 分码得非常开心
解法一
没错，就是按闲话的思路
求下一个点 \(O(n^2)\) 可以做到，往后扫一遍依题算即可
然后对于每个询问暴力一步一步走知道无路可走
竟然给 \(70\) !
\(Code\)
#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
const int N = 1e5 + 5;
int n, m, h[N], nxt[N][2];
struct node{int a, b;};
void getNext()
{
h[0] = 0x3f3f3f3f;
for(register int i = 1; i <= n; i++)
{
int k1 = 0, k2 = 0;
for(register int j = i + 1; j <= n; j++)
{
int z = abs(h[i] - h[j]);
if (z < abs(h[i] - h[k1]) || (z == abs(h[i] - h[k1]) && h[j] < h[k1])) k2 = k1, k1 = j;
else if (z == abs(h[i] - h[k1]) || z < abs(h[i] - h[k2]) || (z == abs(h[i] - h[k2]) && h[j] < h[k2])) k2 = j;
}
nxt[i][1] = k1, nxt[i][0] = k2;
}
}
inline node solve(int S, int X)
{
int p = 0, x = 0;
node ret = {0, 0};
while (nxt[S][p] != 0 && x + abs(h[S] - h[nxt[S][p]]) <= X)
{
if (!p) ret.a += abs(h[S] - h[nxt[S][p]]);
else ret.b += abs(h[S] - h[nxt[S][p]]);
x += abs(h[S] - h[nxt[S][p]]), S = nxt[S][p], p ^= 1;
}
return ret;
}
inline double calc(int x, int y)
{
if (!y) return 0x3f3f3f3f;
return 1.0 * x / y;
}
int main()
{
scanf("%d", &n);
for(register int i = 1; i <= n; i++) scanf("%d", &h[i]);
getNext();
LL S, X;
scanf("%d", &X);
int k = 0; double ans = 0x3f3f3f3f;
for(register int i = 1; i <= n; i++)
{
node t = solve(i, X);
if (calc(t.a, t.b) < ans || (calc(t.a, t.b) == ans && h[i] > h[k]))
ans = calc(t.a, t.b), k = i;
}
printf("%d\n", k);
scanf("%d", &m);
for(; m; m--)
{
scanf("%lld%lld", &S, &X);
node t = solve(S, X);
printf("%d %d\n", t.a, t.b);
}
}
解法二
没错，就是按照解法一的思路
首先我们发现一步一步跳太低效
也太给人灵感
一步一步跳？好熟悉？！
那就倍增啊
\(2\) 的幂次跳就是快！！
然后这不是最关键的地方
因为预处理还卡在 \(O(n^2)\)
相当于什么都没干
所以我们总得干点什么
是的
预处理实际上非常好玩
你可以用排序+链表非常常规地搞出来
当然，你可以更常规用平衡树来搞搞
我选择了后者（当然不可能手打平衡树，\(set\) 就是好）
这东西比较繁琐，要慢慢讨论
收获
用 \(set\) 如果涉及多个关键字怎么办？
这样定义
#include<set>
using namespace std;
struct nod{int h, id;};
struct cmp{bool operator()(const nod &a, const nod &b){return a.h < b.h;}};
set<nod, cmp> s;
于是我们申明了一个节点为 \(nod\) 类型的平衡树
那么各类使用参数也相应的改变
你会发现 \(h\) 是第一关键字
那它在比较时会先比较第一关键字，再比较第二关键字
学会了！
哦，\(AC\) 代码记录一波
#include<cstdio>
#include<algorithm>
#include<set>
#define LL long long
using namespace std;
const int N = 1e5 + 5;
int n, m, h[N], nxt[N][2];
LL F[N][20], A[N][20], B[N][20];
struct node{LL a, b;};
struct nod{int h, id;};
struct cmp{bool operator()(const nod &a, const nod &b){return a.h < b.h;}};
set<nod, cmp> tr;
set<nod, cmp>::iterator it, itt;
inline void swap(nod &x, nod &y){nod t; t = x, x = y, y = t;}
void getNext()
{
tr.insert(nod{h[n], n});
for(register int i = n - 1; i; i--)
{
nod k1 = {0x3f3f3f3f, 0}, k2 = {0x3f3f3f3f, 0};
it = tr.lower_bound(nod{h[i], i});
if (it == tr.begin())
{
k1 = *it;
if (++it != tr.end()) k2 = *it;
}
else if (it == tr.end())
{
k1 = *(--it);
if (it != tr.begin()) k2 = *(--it);
}
else{
itt = it, --it;
int count = 0; nod l = *it, r = *itt;
while (1)
{
if (abs(h[i] - l.h) < abs(h[i] - r.h) || (abs(h[i] - l.h) == abs(h[i] - r.h) && l.h < r.h))
{
if (!count)
{
k1 = l, ++count;
if (it == tr.begin()){l = {0x3f3f3f3f, 0}; continue;}
l = *(--it);
}
else{k2 = l; break;}
}
else{
if (!count)
{
k1 = r, ++count, r = *(++itt);
if (itt == tr.end()) r = {0x3f3f3f3f, 0};
}
else{k2 = r; break;}
}
}
}
if (abs(h[i] - k1.h) > abs(h[i] - k2.h) || (abs(h[i] - k1.h) == abs(h[i] - k2.h) && k1.h > k2.h)) swap(k1, k2);
nxt[i][1] = k1.id, nxt[i][0] = k2.id;
tr.insert(nod{h[i], i});
}
}
void getF()
{
for(register int i = 1; i <= n; i++)
F[i][0] = nxt[nxt[i][0]][1],
A[i][0] = abs(h[i] - h[nxt[i][0]]),
B[i][0] = abs(h[nxt[i][0]] - h[nxt[nxt[i][0]][1]]);
for(register int j = 1; j <= 17; j++)
for(register int i = 1; i <= n; i++)
F[i][j] = F[F[i][j - 1]][j - 1],
A[i][j] = A[i][j - 1] + A[F[i][j - 1]][j - 1],
B[i][j] = B[i][j - 1] + B[F[i][j - 1]][j - 1];
}
inline node solve(int S, LL X)
{
int p = 0; LL x = 0;
node ret = {0, 0};
for(register int i = 17; i >= 0; i--)
if (F[S][i] && x + A[S][i] + B[S][i] <= X)
{
ret.a += A[S][i], ret.b += B[S][i];
x += A[S][i] + B[S][i], S = F[S][i];
}
while (nxt[S][p] && x + abs(h[S] - h[nxt[S][p]]) <= X)
{
if (!p) ret.a += abs(h[S] - h[nxt[S][p]]);
else ret.b += abs(h[S] - h[nxt[S][p]]);
x += abs(h[S] - h[nxt[S][p]]), S = nxt[S][p], p ^= 1;
}
return ret;
}
inline double calc(int x, int y)
{
if (!y) return 0x3f3f3f3f;
return 1.0 * x / y;
}
int main()
{
scanf("%d", &n);
for(register int i = 1; i <= n; i++) scanf("%d", &h[i]);
getNext(), getF();
int S; LL X;
scanf("%lld", &X);
int k = 0; double ans = 0x3f3f3f3f;
for(register int i = 1; i <= n; i++)
{
node t = solve(i, X);
if (calc(t.a, t.b) < ans || (calc(t.a, t.b) == ans && h[i] > h[k]))
ans = calc(t.a, t.b), k = i;
}
printf("%d\n", k);
scanf("%d", &m);
for(; m; m--)
{
scanf("%d%lld", &S, &X);
node t = solve(S, X);
printf("%lld %lld\n", t.a, t.b);
}
}
最新文章
- 前端MVC框架Backbone 1.1.0源码分析(一)
- Sql Server函数全解(一)字符串函数
- Html.DropDownList
- 第一天的作业，登录接口脚本 login.py
- 2014款Macbook Air安装单独X64 Win7系统
- iOS使用keychain存储密码
- bzoj1036: [ZJOI2008]树的统计Count 树链剖分+线段树
- java之认识基本数据类型及其封装类装箱和拆箱总结
- opencv分水岭算法对图像进行切割
- C#通过模板导出Word(文字,表格,图片)
- git 关联远程库（https协议）
- jsp四大作用域
- 迁移python project
- zookeeper频繁异常问题分析
- 2019-04-08-day027-网络编程基础
- 动态设置所有string字段不分词
- crontab 安装与配置
- English Pronunciation Analysis | Advanced English Conversation
- django之创建第8-3个项目-数据库数据提取之高级操作
- python webdriver api-操作日期元素的方法