Irelia

Irelia

逝去的是刀锋,不变的是意志

题解 P5471 【[NOI2019]弹跳】

posted on 2019-09-12 13:26:45 | under 题解 |

看到各路大佬又是优化建图打标记,又是一次松弛一个矩形,又是树上删点之类的,看不懂,这里提供一个更加简单的思路

基本思路

NOI同步赛我打了个KDTree优化建图,当场MLE爆炸,40分。但是通过最基本的KDTree优化建图思路可以想出正解,我们可以大概了解一下。

  • 首先,KDTree的每个节点维护着一个坐标和一个矩形的信息。所以我们把原图上的点就叫做实点,编号范围为 $[1, n]$ ,KDTree上的节点叫做虚点,编号范围为 $[n + 1, 2n]$

  • 我们对于每一个实点,遍历装在这个位置的所有弹跳机,假设当前弹跳机的时间为 $t$ ,起点为 $u$ ,我们上树查询。

  • 对于在树上的一个节点 $x$

    • 如果 $x$ 管辖的矩形完全在弹跳机的目标矩形外,return

    • 如果 $x$ 管辖的矩形完全在弹跳机的目标矩形内,从 $u$ 向 $x$ 建边,权值为 $t$ ,return

    • 两区间交叉情况

    • 如果 $x$ 上维护的坐标在目标矩形内,从 $u$ 向 $x - n$ 建边,权值为 $t$

    • 递归查询两个儿子

  • 最后对于 $\forall x \in [1, n]$ ,从 $x + n$ 向 $x$ 建边即可

以上为KDTree优化建图的基本思路。代码如下(如果有铁憨憨把这份代码粘上去交了我也拦不住

// luogu-judger-enable-o2
#include <algorithm>
#include <iostream>
#include <cstring>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const int MAXN = 7e4 + 5;
const int INF = 0x3f3f3f3f;

int n, m, W, H;

int ID(int x, int y) {
    if (y == 0) return x;
    else return x + n;
}

struct Edge{
    int to, val;

    Edge(int v, int w) {
        to = v;
        val = w;
    }
};

vector<Edge> g[MAXN << 1];
int vis[MAXN << 1], dis[MAXN << 1];

typedef vector<Edge> :: iterator ITE;
typedef pair<int, int> POI;

void AddEdge(int u, int v, int w) {
    g[u].push_back(Edge(v, w));
}

void Dijkstra(int s) {
    priority_queue<POI> q;
    memset(dis, INF, sizeof(dis));
    dis[s] = 0; vis[s] = true; q.push(make_pair(dis[s], s));
    while (!q.empty()) {
        int u = q.top().second; q.pop(); vis[u] = false;
        for (ITE it = g[u].begin(); it != g[u].end(); it++) {
            int v = it->to;
            if (dis[v] > dis[u] + it->val) {
                dis[v] = dis[u] + it->val;
                if (!vis[v]) {
                    q.push(make_pair(dis[v], v));
                    vis[v] = true;
                }
            }
        }
    }
}

struct Data{
    int pos[2];
    int id;
};

int Cmp0(Data x, Data y) {
    return x.pos[0] != y.pos[0] ? (x.pos[0] < y.pos[0]) : (x.pos[1] < y.pos[1]);
}

int Cmp1(Data x, Data y) {
    return x.pos[1] != y.pos[1] ? (x.pos[1] < y.pos[1]) : (x.pos[0] < y.pos[0]);
}

Data data[MAXN];

struct Node{
    Data data;
    int mn[2], mx[2], d;
    Node *ch[2];

    Node() {}

    Node(Data data, int d) : data(data), d(d) {
        ch[0] = NULL;
        ch[1] = NULL;
        for (int i = 0; i < 2; i++) {
            mn[i] = data.pos[i];
            mx[i] = data.pos[i];
        }
    }
}pool[MAXN << 1];

Node *NewNode(Data data, int d) {
    static int p = 0;
    pool[p] = Node(data, d);
    return pool + p++;
}

Node *rt = NULL;

void Update(Node *now) {
    for (int i = 0; i < 2; i++) {
        if (now->ch[i]) {
            for (int j = 0; j < 2; j++) {
                now->mn[j] = min(now->mn[j], now->ch[i]->mn[j]);
                now->mx[j] = max(now->mx[j], now->ch[i]->mx[j]);
            }
        }
    }
}

void Build(Node *&now, int l, int r, int d) {
    if (l > r) return;
    int mid = l + r >> 1;
    if (d == 0) {
        nth_element(data + l, data + mid, data + r + 1, Cmp0);
        now = NewNode(data[mid], d);
    } else {
        nth_element(data + l, data + mid, data + r + 1, Cmp1);
        now = NewNode(data[mid], d);
    }
    Build(now->ch[0], l, mid - 1, (d + 1) % 2);
    Build(now->ch[1], mid + 1, r, (d + 1) % 2);
    Update(now);
    if (now->ch[0]) AddEdge(ID(now->data.id, 1), ID(now->ch[0]->data.id, 1), 0);
    if (now->ch[1]) AddEdge(ID(now->data.id, 1), ID(now->ch[1]->data.id, 1), 0);
}

void Jump(Node *now, int u, int mn[], int mx[], int w) {
    if (!now) return;
    int allin = true, allout = false, insq = true;
    for (int i = 0; i < 2; i++) {
        if (now->mx[i] < mn[i] || now->mn[i] > mx[i]) allout = true;
        if (now->mx[i] > mx[i] || now->mn[i] < mn[i]) allin = false;
        if (now->data.pos[i] < mn[i] || now->data.pos[i] > mx[i]) insq = false;
    }
    if (allout) return;
    if (allin) {
        AddEdge(ID(u, 0), ID(now->data.id, 1), w);
        //cerr << '#';
        return;
    }
    if (insq) {
        AddEdge(ID(u, 0), ID(now->data.id, 0), w);
        //cerr << '$';
    }
    Jump(now->ch[0], u, mn, mx, w);
    Jump(now->ch[1], u, mn, mx, w);
}

void Init() {
    cin >> n >> m >> W >> H;
    for (int i = 1; i <= n; i++) {
        cin >> data[i].pos[0] >> data[i].pos[1];
        data[i].id = i;
    }
    for (int i = 1; i <= n; i++) AddEdge(ID(i, 1), ID(i, 0), 0);
    Build(rt, 1, n, 0);
    //cerr << '*';
    int mn[2], mx[2], x, y;
    for (int i = 1; i <= m; i++) {
        cin >> x >> y;
        cin >> mn[0] >> mx[0];
        cin >> mn[1] >> mx[1];
        Jump(rt, x, mn, mx, y);
        //cerr << '*';
    }
    //cerr << '*';
}

void Work() {
    Dijkstra(1);
    for (int i = 2; i <= n; i++) cout << dis[ID(i, 0)] << endl;
}

int main() {
    ios :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    //freopen("jump.in", "r", stdin);
    //freopen("jump.out", "w", stdout);
    Init();
    Work();
    return 0;
}

优化

这里提供可以优化的两条锦囊妙计。

  1. 首先,我们可以假装我们把图建了出来,不建边

假装把图建出来?你可能要问了,我们都没有建边,怎么知道从一个点出发,能到达哪些点?

我们当然可以知道!就像在赛场上切掉此题的某位银牌大佬 @龙之吻—水货 所说:

首先你有一棵树

你要把这棵树完全变成你的工具

你建边的目的是要知道从一个点出发能到达哪些点

想通了就OK了,根据刚才建图的思路,我们完全知道从一个节点出发能到达哪些节点。

  • 对于一个虚点 $u$ ,能到达的节点如下

    • 它的两个儿子对应的虚点

    • 它所对应的实点

  • 对于一个实点 $u$

    • 在跑SPFA最短路时,如果从队列中拿出实点,直接遍历从 $x$ 出发的弹跳机,上树查询

    • 对于在树上的一个虚点 $x$

    • 如果 $x$ 管辖的区间完全在目标区间外,return

    • 如果 $x$ 管辖的区间完全在目标区间内,松弛 $x$

    • 对于区间交叉情况

      • 如果 $x$ 对应的坐标在目标区间内,松弛 $x - n$

      • 递归查询两个儿子

    • 松弛时加上的距离为弹跳机用时

你看完这个思路,感觉有点眼熟,返回去看了一眼40分思路

完全一样?是的。

代码如下

// luogu-judger-enable-o2
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int MAXN = 7e4 + 5;
const int MAXM = 15e4 + 5;
const int INF = 0x3f3f3f3f;

int n, m, W, H;

struct Edge{
    Edge *nxt;
    int val;
    int mn[2], mx[2];

    Edge() {}

    Edge(int val, int l[], int r[], Edge *nxt) : val(val), nxt(nxt) {
        memcpy(mn, l, sizeof(mn));
        memcpy(mx, r, sizeof(mx));
    }
}epool[MAXM];

Edge *NewEdge(int val, int l[], int r[], Edge *nxt) {
    static int ecnt = 0;
    epool[ecnt] = Edge(val, l, r, nxt);
    return &epool[ecnt++];
}

Edge *head[MAXN];

void AddEdge(int u, int w, int l[], int r[]) {
    head[u] = NewEdge(w, l, r, head[u]);
}

struct Point{
    int id;
    int x[2];

    Point() {}

    Point(int id, int a, int b) : id(id) {
        x[0] = a;
        x[1] = b;
    }
}data[MAXN];

int Comp0(Point a, Point b) {
    return (a.x[0] == b.x[0]) ? (a.x[1] < b.x[1]) : (a.x[0] < b.x[0]);
}

int Comp1(Point a, Point b) {
    return (a.x[1] == b.x[1]) ? (a.x[0] < b.x[0]) : (a.x[1] < b.x[1]);
}

struct Node{
    Point pos;
    Node *ch[2];
    int mn[2], mx[2];

    Node() {}

    Node(Point pos) : pos(pos) {
        ch[0] = ch[1] = NULL;
        for (int i = 0; i < 2; i++) mn[i] = mx[i] = pos.x[i];
    }
}npool[MAXN];

void Update(Node *now) {
    for (int i = 0; i < 2; i++) {
        if (now->ch[i]) {
            for (int j = 0; j < 2; j++) {
                now->mn[j] = min(now->mn[j], now->ch[i]->mn[j]);
                now->mx[j] = max(now->mx[j], now->ch[i]->mx[j]);
            }
        }
    }
}

Node *NewNode(Point pos) {
    static int ncnt = 0;
    npool[ncnt] = Node(pos);
    return &npool[ncnt++];
}

Node *rt = NULL;
Node *ima[MAXN];

void Build(Node *&now, int l, int r, int d) {
    if (l > r) return;
    int mid = l + r >> 1;
    if (d == 0) nth_element(data + l, data + mid, data + r + 1, Comp0);
    else nth_element(data + l, data + mid, data + r + 1, Comp1);
    now = NewNode(data[mid]);
    ima[now->pos.id] = now;
    Build(now->ch[0], l, mid - 1, d ^ 1);
    Build(now->ch[1], mid + 1, r, d ^ 1);
    Update(now);
}

int q[MAXN << 1], hd, tl, len;
int dis[MAXN << 1];
int vis[MAXN << 1];

void Relax(int v, int w) {
    if (dis[v] > w) {
        dis[v] = w;
        if (!vis[v]) {
            q[++tl % len] = v;
            vis[v] = 1;
        }
    }
}

int AllIn(Node *now, int mn[], int mx[]) {
    for (int i = 0; i < 2; i++) {
        if (now->mn[i] < mn[i] || now->mx[i] > mx[i]) return 0;
    }
    return 1;
}

int AllOut(Node *now, int mn[], int mx[]) {
    for (int i = 0; i < 2; i++) {
        if (now->mn[i] > mx[i] || now->mx[i] < mn[i]) return 1;
    }
    return 0;
}

int Inside(Node *now, int mn[], int mx[]) {
    for (int i = 0; i < 2; i++) {
        if (now->pos.x[i] < mn[i] || now->pos.x[i] > mx[i]) return 0;
    }
    return 1;
}

void Jump(Node *now, int mn[], int mx[], int w) {
    if (!now) return;
    if (AllOut(now, mn, mx)) return;
    if (AllIn(now, mn, mx)) {
        Relax(now->pos.id + n, w);
        return;
    }
    if (Inside(now, mn, mx)) Relax(now->pos.id, w);
    Jump(now->ch[0], mn, mx, w);
    Jump(now->ch[1], mn, mx, w);
}

void Spfa(int s) {
    memset(dis, INF, sizeof(dis));
    dis[s] = 0;
    hd = 1; tl = 0; q[++tl % len] = s; vis[s] = 1;
    while (hd <= tl) {
        int u = q[hd++ % len]; vis[u] = 0;
        if (u > n) {
            Relax(u - n, dis[u]);
            if (ima[u - n]->ch[0]) Relax(ima[u - n]->ch[0]->pos.id + n, dis[u]);
            if (ima[u - n]->ch[1]) Relax(ima[u - n]->ch[1]->pos.id + n, dis[u]);
        } else {
            for (Edge *e = head[u]; e; e = e->nxt) {
                Jump(rt, e->mn, e->mx, dis[u] + e->val);
            }
        }
    }
}

void Init() {
    cin >> n >> m >> W >> H;
    len = n * 2;
    for (int i = 1; i <= n; i++) {
        data[i].id = i;
        cin >> data[i].x[0] >> data[i].x[1];
    }
    Build(rt, 1, n, 0);
    int l[2], r[2], u, t;
    for (int i = 1; i <= m; i++) {
        cin >> u >> t >> l[0] >> r[0] >> l[1] >> r[1];
        AddEdge(u, t, l, r);
    }
}

void Work() {
    Spfa(1);
//  for (int i = 1; i <= n * 2; i++) cerr << dis[i] << " ";
//  cerr << "\n";
    for (int i = 2; i <= n; i++) cout << dis[i] << "\n";
}

int main() {
    Init();
    Work();
    return 0;
}

88分到手,(如果有铁憨憨抄上去我也没啥说的

我们可以使用第二条锦囊妙计:

  1. 关于SPFA,它死了

van♂van♂没想到,NOI2018卡了SPFA,NOI2019竟然还要卡

行了不墨迹了,直接换Dijkstra,以下为AC代码

// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <utility>

using namespace std;
typedef pair<int, int> POI;
const int MAXN = 7e4 + 5;
const int MAXM = 15e4 + 5;
const int INF = 0x3f3f3f3f;

int n, m, W, H;

struct Edge{
    Edge *nxt;
    int val;
    int mn[2], mx[2];

    Edge() {}

    Edge(int val, int l[], int r[], Edge *nxt) : val(val), nxt(nxt) {
        memcpy(mn, l, sizeof(mn));
        memcpy(mx, r, sizeof(mx));
    }
}epool[MAXM];

Edge *NewEdge(int val, int l[], int r[], Edge *nxt) {
    static int ecnt = 0;
    epool[ecnt] = Edge(val, l, r, nxt);
    return &epool[ecnt++];
}

Edge *head[MAXN];

void AddEdge(int u, int w, int l[], int r[]) {
    head[u] = NewEdge(w, l, r, head[u]);
}

struct Point{
    int id;
    int x[2];

    Point() {}

    Point(int id, int a, int b) : id(id) {
        x[0] = a;
        x[1] = b;
    }
}data[MAXN];

int Comp0(Point a, Point b) {
    return (a.x[0] == b.x[0]) ? (a.x[1] < b.x[1]) : (a.x[0] < b.x[0]);
}

int Comp1(Point a, Point b) {
    return (a.x[1] == b.x[1]) ? (a.x[0] < b.x[0]) : (a.x[1] < b.x[1]);
}

struct Node{
    Point pos;
    Node *ch[2];
    int mn[2], mx[2];

    Node() {}

    Node(Point pos) : pos(pos) {
        ch[0] = ch[1] = NULL;
        for (int i = 0; i < 2; i++) mn[i] = mx[i] = pos.x[i];
    }
}npool[MAXN];

void Update(Node *now) {
    for (int i = 0; i < 2; i++) {
        if (now->ch[i]) {
            for (int j = 0; j < 2; j++) {
                now->mn[j] = min(now->mn[j], now->ch[i]->mn[j]);
                now->mx[j] = max(now->mx[j], now->ch[i]->mx[j]);
            }
        }
    }
}

Node *NewNode(Point pos) {
    static int ncnt = 0;
    npool[ncnt] = Node(pos);
    return &npool[ncnt++];
}

Node *rt = NULL;
Node *ima[MAXN];

void Build(Node *&now, int l, int r, int d) {
    if (l > r) return;
    int mid = l + r >> 1;
    if (d == 0) nth_element(data + l, data + mid, data + r + 1, Comp0);
    else nth_element(data + l, data + mid, data + r + 1, Comp1);
    now = NewNode(data[mid]);
    ima[now->pos.id] = now;
    Build(now->ch[0], l, mid - 1, d ^ 1);
    Build(now->ch[1], mid + 1, r, d ^ 1);
    Update(now);
}

//int q[MAXN << 1], hd, tl, len;
priority_queue<POI, vector<POI>, greater<POI> > q;
int dis[MAXN << 1];
int vis[MAXN << 1];

void Relax(int v, int w) {
    if (dis[v] > w) {
        q.push(make_pair(dis[v] = w, v));
    }
}

int AllIn(Node *now, int mn[], int mx[]) {
    for (int i = 0; i < 2; i++) {
        if (now->mn[i] < mn[i] || now->mx[i] > mx[i]) return 0;
    }
    return 1;
}

int AllOut(Node *now, int mn[], int mx[]) {
    for (int i = 0; i < 2; i++) {
        if (now->mn[i] > mx[i] || now->mx[i] < mn[i]) return 1;
    }
    return 0;
}

int Inside(Node *now, int mn[], int mx[]) {
    for (int i = 0; i < 2; i++) {
        if (now->pos.x[i] < mn[i] || now->pos.x[i] > mx[i]) return 0;
    }
    return 1;
}

void Jump(Node *now, int mn[], int mx[], int w) {
    if (!now) return;
    if (AllOut(now, mn, mx)) return;
    if (AllIn(now, mn, mx)) {
        Relax(now->pos.id + n, w);
        return;
    }
    if (Inside(now, mn, mx)) Relax(now->pos.id, w);
    Jump(now->ch[0], mn, mx, w);
    Jump(now->ch[1], mn, mx, w);
}

void Dijkstra(int s) {
    memset(dis, INF, sizeof(dis));
    dis[s] = 0;
    //  hd = 1; tl = 0; q[++tl % len] = s; vis[s] = 1;
    q.push(make_pair(dis[s], s));
    int cnt = 0;
    while (!q.empty()) {
        if (q.top().first != dis[q.top().second]) {
            q.pop();
            continue;
        }
        int u = q.top().second; q.pop();
        if (u > n) {
            Relax(u - n, dis[u]);
            if (ima[u - n]->ch[0]) Relax(ima[u - n]->ch[0]->pos.id + n, dis[u]);
            if (ima[u - n]->ch[1]) Relax(ima[u - n]->ch[1]->pos.id + n, dis[u]);
        } else {
            for (Edge *e = head[u]; e; e = e->nxt) {
                Jump(rt, e->mn, e->mx, dis[u] + e->val);
            }
        }
    }
}

void Init() {
    ios :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m >> W >> H;
    //  len = n * 2;
    for (int i = 1; i <= n; i++) {
        data[i].id = i;
        cin >> data[i].x[0] >> data[i].x[1];
    }
    Build(rt, 1, n, 0);
    int l[2], r[2], u, t;
    for (int i = 1; i <= m; i++) {
        cin >> u >> t >> l[0] >> r[0] >> l[1] >> r[1];
        AddEdge(u, t, l, r);
    }
}

void Work() {
    Dijkstra(1);
    //  for (int i = 1; i <= n * 2; i++) cerr << dis[i] << " ";
    //  cerr << "\n";
    for (int i = 2; i <= n; i++) cout << dis[i] << "\n";
}

int main() {
    Init();
    Work();
    return 0;
}