洛谷P1081 开车旅行(倍增)

题意

题目链接

Sol

咕了一年的题解。。

并不算是很难，只是代码有点毒瘤

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

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

倍增优化一下

注意最后\(a\)可能还会走一次

#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;

inline int read() {

    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);

    N = read();

    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);

    int M = read();

    while(M--) {

        int Si = read(), Mi = read();

        Pair now = Query(Si, Mi);

        printf("%d %d\n", now.fi, now.se);

    }

    return 0;

}

巴特西

洛谷P1081 开车旅行(倍增)

题意

Sol

最新文章

热门文章