# 洛谷P1081 开车旅行(倍增)

## Sol

$$f[i][j]$$表示从$$i$$号节点出发走了$$2^j$$轮后总的距离

$$da[i][j]$$同理表示$$a$$的距离,$$db[i][j]$$与$$da$$同理

#include<bits/stdc++.h>
#define Pair pair<int, int>
#define MP make_pair
#define fi first
#define se second
#define Fin(x) {freopen(#x".in","r",stdin);}
#define pb(x) push_back(x)
#define LL long long
//#define int long long
using namespace std;
const int MAXN = 1e5 + 10;
LL INF = 2e9 + 10, B = 20;
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, jp[MAXN][21], nxa[MAXN], nxb[MAXN], flag[MAXN], h[MAXN];
LL f[MAXN][21], da[MAXN][21], db[MAXN][21];
struct Node {
LL Hi, id;
bool operator < (const Node &rhs) const{
return Hi == rhs.Hi ? h[id] < h[rhs.id] : Hi < rhs.Hi;
}
};
int get(int x, int y) {
return abs(h[x] - h[y]);
}
set<Node> s;
void Pre() {
s.insert((Node) {-INF * 2, 0}); s.insert((Node) {INF * 2, 0});
s.insert((Node) {-INF * 2 + 1, 0}); s.insert((Node) {INF * 2 + 1, 0});
s.insert((Node) {h[N], N});
memset(f, 0x3f, sizeof(f));
for(int i = N - 1; i >= 1; i--) {
set<Node> :: iterator y = s.lower_bound((Node) {h[i], i});
vector<Node> tmp; tmp.clear();
tmp.push_back((Node) {get(y -> id, i), y -> id}); y++;
tmp.push_back((Node) {get(y -> id, i), y -> id}); y--; y--;
tmp.push_back((Node) {get(y -> id, i), y -> id}); y--;
tmp.push_back((Node) {get(y -> id, i), y -> id});
sort(tmp.begin(), tmp.end());
nxa[i] = tmp[1].id;
nxb[i] = tmp[0].id;
s.insert((Node) {h[i], i});
if(tmp[1].id != 0 && tmp[0].id != 0) f[i][0] = tmp[1].Hi + db[tmp[1].id][0];
jp[i][0] = nxb[nxa[i]];
da[i][0] = get(i, nxa[i]);
db[i][0] = get(i, nxb[i]);
}
for(int j = 1; j <= B; j++)
for(int i = 1; i <= N; i++) {
if(jp[i][j - 1])
jp[i][j] = jp[jp[i][j - 1]][j - 1],
f[i][j] = f[i][j - 1] + f[jp[i][j - 1]][j - 1],
da[i][j] = f[i][j] == INF ? 0 : da[i][j - 1] + da[jp[i][j - 1]][j - 1];
}

}
void print() {
for(int i = 1; i <= N; i++) printf("**%d\n", f[i][0]);
}
Pair Query(int pos, int val) {
LL a1 = 0, a2 = 0;
for(int i = B; ~i; i--)
if(f[pos][i] <= val)
val -= f[pos][i], a1 += da[pos][i], a2 += f[pos][i] - da[pos][i], pos = jp[pos][i];
if(da[pos][0] <= val) a1 += da[pos][0];
return MP(a1, a2);
}
signed main() {
// freopen("drive3.in", "r", stdin);
//   freopen("a.out", "w", stdout);
for(int i = 1; i <= N; i++) h[i] = read(); h[0] = INF;

Pre();
// print();
int X0 = read(), ans = N;
double tmp = 1e22;
for(int i = 1; i <= N; i++) {
Pair now = Query(i, X0);
if(now.se == 0) continue;
if((double)now.fi / now.se < tmp) tmp = (double)now.fi / now.se, ans = i;
}
printf("%d\n", ans);
while(M--) {
Pair now = Query(Si, Mi);
printf("%d %d\n", now.fi, now.se);
}
return 0;
}

0 条评论

• ### 2491 玉蟾宫

2491 玉蟾宫 时间限制: 1 s 空间限制: 64000 KB 题目等级 : 大师 Master 题目描述 Description 　　有一天...

• ### LOJ#6277. 数列分块入门 1

内存限制：256 MiB时间限制：100 ms标准输入输出 题目类型：传统评测方式：文本比较 上传者： hzwer 提交提交记录统计讨论 1 测试数据 题...

• ### loj#6031. 「雅礼集训 2017 Day1」字符串(SAM 广义SAM 数据分治)

考虑K比较小的情况，可以直接暴力建SAM， 枚举w的子串算出现次数。询问用个 的vector记录一下每次在vector里二分就好。

• ### 【校赛小分队之我们有个女生】训练赛6

每个manager给数组a的第1到r[i]个数排序，t[i]==1则排升序，2则排降序。求m个manager排序完的序列。

• ### 每天都在用printf，你知道变长参数是怎么实现的吗

变长参数，指的是函数参数数量可变，或者说函数接受参数的数量可以不固定。实际上，我们最开始学C语言的时候，就用到了这样的函数:printf，它接受任意数量的参数，...

• ### 变长参数探究

变长参数，指的是函数参数数量可变，或者说函数接受参数的数量可以不固定。实际上，我们最开始学C语言的时候，就用到了这样的函数:printf，它接受任意数量的参数，...

• ### 46. 全排列【回溯算法】

输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], ...

• ### 为什么有了IndexOf，还要有FindIndex​？

【摘要】对于IndexOf()，相信大家都是很熟悉的，但是，昨天我们提供的List用法中还有一个FindIndex()，看起来功能描述与IndexOf...

• ### 爱彼迎19年社招java面试题 求DAG图中每个点的祖先个数

例如上图, 则H的祖先个数是3个（包括它自己哈），分别是和. 而N的祖先个数是4（）。

• ### BZOJ4259: 残缺的字符串(FFT 字符串匹配)

考虑把B翻转过来，如果$$\sum_{k = 0}^M (B_{i - k} - A_k)^2 * B_{i-k}*A_k = 0$$