1 条题解

  • 0
    @ 2025-8-24 22:11:07

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar Ireliaღ
    逝去的是刀锋，不变的是意志

    搬运于2025-08-24 22:11:07，当前版本为作者最后更新于2019-09-12 13:26:45，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

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

    基本思路

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

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

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

    • 对于在树上的一个节点xx

      • 如果xx管辖的矩形完全在弹跳机的目标矩形外，return

      • 如果xx管辖的矩形完全在弹跳机的目标矩形内，从uu向xx建边，权值为tt，return

      • 两区间交叉情况

        • 如果xx上维护的坐标在目标矩形内，从uu向x−nx - n建边，权值为tt

        • 递归查询两个儿子

    • 最后对于∀x∈[1,n]\forall x \in [1, n]，从x+nx + n向xx建边即可

    以上为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了，根据刚才建图的思路，我们完全知道从一个节点出发能到达哪些节点。

    • 对于一个虚点uu，能到达的节点如下

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

      • 它所对应的实点

    • 对于一个实点uu

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

      • 对于在树上的一个虚点xx

        • 如果xx管辖的区间完全在目标区间外，return

        • 如果xx管辖的区间完全在目标区间内，松弛xx

        • 对于区间交叉情况

          • 如果xx对应的坐标在目标区间内，松弛x−nx - 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;
}
    • 1

    [NOI2019] 弹跳

    信息

    ID
    4462
    时间
    2200ms
    内存
    125MiB
    难度
    6
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 25ms