专栏首页数据结构与算法洛谷P1081 开车旅行(倍增)

洛谷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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2491 玉蟾宫

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

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

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

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

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

    attack
  • 【校赛小分队之我们有个女生】训练赛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], ...

    韩旭051
  • 为什么有了IndexOf,还要有FindIndex​?

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

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

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

    ACM算法日常
  • BZOJ4259: 残缺的字符串(FFT 字符串匹配)

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

    attack

扫码关注云+社区

领取腾讯云代金券