Luogu1081 开车旅行

旅行"/>

Luogu1081 开车旅行

代码巨长的倍增题...

显然这是没有什么决策的，选择方案都是固定的

这可以考虑倍增跳，每个位置上跳到的位置是可以通过查前驱后继解决的

有两种方式：

　　一种是平衡树搞法，倒着做查完了插入

　　另一种是先排序建一个链表，查完了删除

都是可以通过加哨兵节点来搞的，
结果我只想到了 set 乱搞，就写了很长

预处理完就可做了

第一问对于每个点倍增一遍，其实就是照题意模拟，倍增优化一下

第二问还是照题意模拟，倍增优化一下

暴力有 70pts ？

代码：

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cstdio>
#include <locale>
#include <cmath>
#include <set>
using namespace std;typedef long long ll;
const int MAX_N = 100005;
const double INF = 100000000000001.0;struct Node {int len, id;Node(int L = 0, int ID = 0) {len = L; id = ID;}bool operator < (const Node& b) const {return len < b.len;}
};
struct PAIR {ll fir, sec;PAIR(ll x = 0, ll y = 0) {fir = x; sec = y;}friend PAIR operator + (PAIR a, PAIR b) {return PAIR(a.fir + b.fir, a.sec + b.sec);}
}d[MAX_N][20][2];
int n, lg, x0, m, ans;int h[MAX_N], f[MAX_N][20][2];
double ans_rat;
set<Node> st;inline int rd() {register int x = 0, c = getchar();register bool f = false;while (!isdigit(c)) {f = (c == '-');c = getchar();}while (isdigit(c)) {x = x * 10 + (c ^ 48);c = getchar();}return f ? -x : x;
}
inline void get_for(int pos, set<Node>::iterator iter) {auto lef = iter, rig = iter;if (iter == st.begin()) {f[pos][0][0] = iter->id;d[pos][0][0].fir = abs(h[pos] - h[iter->id]);++iter;if (st.size() == 1) return;f[pos][0][1] = iter->id;d[pos][0][1].sec = abs(h[pos] - h[iter->id]);return;} else if (iter == st.end()) {--iter;f[pos][0][0] = iter->id;d[pos][0][0].fir = abs(h[pos] - h[iter->id]);if (iter == st.begin()) return;--iter;f[pos][0][1] = iter->id;d[pos][0][1].sec = abs(h[pos] - h[iter->id]);return;}++rig;if (rig == st.end()) {--lef;if (lef == st.begin()) {if (abs(h[pos] - h[lef->id]) <= abs(h[pos] - h[iter->id])) {f[pos][0][0] = lef->id;d[pos][0][0].fir = abs(h[pos] - h[lef->id]);f[pos][0][1] = iter->id;d[pos][0][1].sec = abs(h[pos] - h[iter->id]);} else {f[pos][0][0] = iter->id;d[pos][0][0].fir = abs(h[pos] - h[iter->id]);f[pos][0][1] = lef->id;d[pos][0][1].sec = abs(h[pos] - h[lef->id]);}return;}if (abs(h[pos] - h[lef->id]) <= abs(h[pos] - h[iter->id])) {f[pos][0][0] = lef->id;d[pos][0][0].fir = abs(h[pos] - h[lef->id]);--lef;if (abs(h[pos] - h[lef->id]) <= abs(h[pos] - h[iter->id])) {f[pos][0][1] = lef->id;d[pos][0][1].sec = abs(h[pos] - h[lef->id]);} else {f[pos][0][1] = iter->id;d[pos][0][1].sec = abs(h[pos] - h[iter->id]);}return;}f[pos][0][0] = iter->id;d[pos][0][0].fir = abs(h[pos] - h[iter->id]);f[pos][0][1] = lef->id;d[pos][0][1].sec = abs(h[pos] - h[lef->id]);return;}--lef;if (abs(h[pos] - h[lef->id]) == abs(h[pos] - h[iter->id])) {f[pos][0][0] = lef->id;d[pos][0][0].fir = abs(h[pos] - h[lef->id]);f[pos][0][1] = iter->id;d[pos][0][1].sec = abs(h[pos] - h[iter->id]);} else if (abs(h[pos] - h[lef->id]) < abs(h[pos] - h[iter->id])) {f[pos][0][0] = lef->id;d[pos][0][0].fir = abs(h[pos] - h[lef->id]);if (lef == st.begin()) {f[pos][0][1] = iter->id;d[pos][0][1].sec = abs(h[pos] - h[iter->id]);} else {--lef;if (abs(h[pos] - h[lef->id]) <= abs(h[pos] - h[iter->id])) {f[pos][0][1] = lef->id;d[pos][0][1].sec = abs(h[pos] - h[lef->id]);} else {f[pos][0][1] = iter->id;d[pos][0][1].sec = abs(h[pos] - h[iter->id]);}}} else {f[pos][0][0] = iter->id;d[pos][0][0].fir = abs(h[pos] - h[iter->id]);if (abs(h[pos] - h[lef->id]) <= abs(h[pos] - h[rig->id])) {f[pos][0][1] = lef->id;d[pos][0][1].sec = abs(h[pos] - h[lef->id]);} else {f[pos][0][1] = rig->id;d[pos][0][1].sec = abs(h[pos] - h[rig->id]);}}
}
inline void DBL_init() {for (int i = n; i >= 1; --i) {if (!st.empty()) {auto dst = st.lower_bound(h[i]);get_for(i, dst);}st.insert(Node(h[i], i));}for (int i = 1; i <= n && 2 + i <= n; ++i) {f[i][1][0] = f[f[i][0][0]][0][1];f[i][1][1] = f[f[i][0][1]][0][0];d[i][1][0] = d[i][0][0] + d[f[i][0][0]][0][1];d[i][1][1] = d[i][0][1] + d[f[i][0][1]][0][0];}for (int j = 2; j <= lg; ++j) {for (int i = 1; i <= n && (1 << j) + i <= n; ++i) {f[i][j][0] = f[f[i][j - 1][0]][j - 1][0];f[i][j][1] = f[f[i][j - 1][1]][j - 1][1];d[i][j][0] = d[i][j - 1][0] + d[f[i][j - 1][0]][j - 1][0];d[i][j][1] = d[i][j - 1][1] + d[f[i][j - 1][1]][j - 1][1];}}
}
inline void get_ans(int bgn) {register int pos = bgn;register ll dst_a = 0, dst_b = 0;register bool got_bgn = false;register double rat;for (int i = lg; i >= 0; --i) {if (!f[pos][i][1] || dst_a + dst_b + d[pos][i][1].fir + d[pos][i][1].sec > x0 || (i == 0 && !f[pos][0][0])) continue;got_bgn = true;dst_b += d[pos][i][1].fir;dst_a += d[pos][i][1].sec;pos = f[pos][i][1];}if (!got_bgn) return;if (dst_b == 0) {if (dst_a == 0) rat = 1.0;else rat = INF;} else {rat = double(dst_a) / double(dst_b);}if (fabs(0.0 - ans_rat) < 1e-7 || rat < ans_rat || (fabs(rat - ans_rat) < 1e-7 && h[bgn] > h[ans])) {ans_rat = rat;ans = bgn;}
}int main() {n = rd();lg = int(ceil(log2(n)));for (int i = 1; i <= n; ++i) h[i] = rd();DBL_init();x0 = rd();for (int i = 1; i <= n; ++i)get_ans(i);printf("%d\n", ans);m = rd();register int s = 0, x = 0;register ll tot_a = 0, tot_b = 0;while (m--) {tot_a = tot_b = 0;s = rd(); x = rd();for (int i = lg; i >= 0; --i) {if (!f[s][i][1] || (tot_a + tot_b + d[s][i][1].fir + d[s][i][1].sec > x)) continue;tot_b += d[s][i][1].fir;tot_a += d[s][i][1].sec;s = f[s][i][1];}printf("%lld %lld\n", tot_a, tot_b);}return 0;
}

转载于:.html