【NOIP2012】开车旅行
纪念一下这个大毒瘤
先用multiset处理一下在每个城市时小A和小B的下一个到达的。
一个一个地跳肯定会超时，所以考虑倍增。
f[i][A/B][k]表示从城市i出发，A/B先开车，走(2^k)天所到达的城市。
fa[i][A/B][k]表示从城市i出发，A/B先开车，走(2^k)天小A走的路程。
fb[i][A/B][k]表示从城市i出发，A/B先开车，走(2^k)天小B走的路程。
初始化：
//0表示小A, 1表示小B higha表示小A到达的下一个城市，highb同理
f[i][0][0] = higha; f[i][1][0] = highb;
fa[i][0][0] = abs(h[i] - h[higha]);
fb[i][1][0] = abs(h[i] - h[highb]);
转移
//这里j表示天数的幂，即2^j天，k表示小A或小B
for(int j = 1;j <= 23; j++) {
for(int k = 0; k < 2; k++) {
if(j == 1) {//走两天时单独处理
f[i][k][1] = f[f[i][k][0]][1 - k][0];
fa[i][k][1] = fa[i][k][0] + fa[f[i][k][0]][1 - k][0];
fb[i][k][1] = fb[i][k][0] + fb[f[i][k][0]][1 - k][0];
} else {
f[i][k][j] = f[f[i][k][j - 1]][k][j - 1];
fa[i][k][j] = fa[i][k][j - 1] + fa[f[i][k][j - 1]][k][j - 1];
fb[i][k][j] = fb[i][k][j - 1] + fb[f[i][k][j - 1]][k][j - 1];
}
}
}
完整代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
using namespace std;
typedef long long lld;
const int N = 100100;
const int inf = 2e9;
int a[N], n, h[N];
int f[N][2][25], fa[N][2][25], fb[N][2][25];//0 : A, 1 : B
//A 次近 B 最近
struct node {
int id, high;
friend bool operator < (node a, node b) {//重载运算符由小到大排序
return a.high < b.high;
}
};
multiset<node> s;
void get_next() {
h[0] = inf; h[n + 1] = -inf;
node st;
st.id = 0, st.high = inf;
s.insert(st); s.insert(st);
st.id = n + 1, st.high = -inf;
s.insert(st); s.insert(st);
set<node>::iterator q;
for(int i = n; i >= 1; i--) {
int higha, highb;
node city; city.high = h[i], city.id = i;
s.insert(city);
q = s.lower_bound(city);
q--;
int per = (*q).id, perh = (*q).high;
q++, q++;
int nxt = (*q).id, nxth = (*q).high;
q--;
if(abs(perh - h[i]) <= abs(nxth - h[i])) { //per min
highb = per;
q--, q--;
if(abs(nxth - h[i]) < abs(h[i] - (*q).high)) {
higha = nxt;
} else higha = (*q).id;
} else { //nxt min
highb = nxt;
q++, q++;
if(abs(perh - h[i]) <= abs(h[i] - (*q).high)) {
higha = per;
} else higha = (*q).id;
}
f[i][0][0] = higha; f[i][1][0] = highb;
fa[i][0][0] = abs(h[i] - h[higha]);
fb[i][1][0] = abs(h[i] - h[highb]);
for(int j = 1;j <= 23; j++) {
for(int k = 0; k < 2; k++) {
if(j == 1) {
f[i][k][1] = f[f[i][k][0]][1 - k][0];
fa[i][k][1] = fa[i][k][0] + fa[f[i][k][0]][1 - k][0];
fb[i][k][1] = fb[i][k][0] + fb[f[i][k][0]][1 - k][0];
} else {
f[i][k][j] = f[f[i][k][j - 1]][k][j - 1];
fa[i][k][j] = fa[i][k][j - 1] + fa[f[i][k][j - 1]][k][j - 1];
fb[i][k][j] = fb[i][k][j - 1] + fb[f[i][k][j - 1]][k][j - 1];
}
}
}
}
}
int xa, xb;
void calc(int start, int x) {
int st = start;
xa = 0, xb = 0;
for(int i = 23; i >= 0; i--) {
if(f[st][0][i] && xa + xb + fa[st][0][i] + fb[st][0][i] <= x) {
xa += fa[st][0][i]; xb += fb[st][0][i];
st = f[st][0][i];
}
}
return ;
}
void solve1() {
int x0; scanf("%d", &x0);
double ratio = inf * 1.0; int ans = 0;
for(int i = 1; i <= n; i++) {
calc(i, x0);
if(xb == 0) {
xb = 1; xa = inf;
}
if((1.0 * double(xa) / double(xb)) < ratio) {
ratio = double(xa) / double(xb); ans = i;
} else if(double(xa) / double(xb) == ratio) {
if(h[i] > h[ans]) ans = i;
}
}
printf("%d
", ans);
}
void solve2() {
int m; scanf("%d", &m);
for(int i = 1, x0, st; i <= m; i++) {
scanf("%d%d", &st, &x0);
calc(st, x0);
printf("%d %d
", xa, xb);
}
}
int main() {
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &h[i]);
}
get_next();
solve1();
solve2();
return 0;
}