自动搬运

查看原文

来自洛谷，原作者为

	pldzy 就像我一直听香夭从未沾湿眼角。

搬运于2025-08-24 23:01:24，当前版本为作者最后更新于2024-12-24 21:12:39，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

提供一篇码风友好，码量友好，题解语言友好易读的题解。

Solution

考虑一下碰撞情况，$6$ 种碰撞方式。判断是否相撞（不考虑是否消失）的条件也很显然，例如南北方向就是横坐标相同，例如北东方向就是横纵坐标之和相同。具体的话可以参考 Code 部分的具体说明。

对于每种碰撞方式，维护它的所有可能情况。题目的难点在于碰撞完后船的消失会影响后面的碰撞情况。

以北东方向的碰撞为例，我们把所有北方向和东方向的船丢到一个 vector<int>() 中，按照横纵坐标之和为第一关键字，按照横坐标为第二关键字，从小到大排序。发现我们目前需要考虑的碰撞，是满足一下条件的船对：

• 第一关键字相同（否则它们永不相撞）；
• 两艘船的方向不同（方向相同的船不会相撞）；
• 两艘船在 vector<int>() 中相邻（不相邻的船对一定没有相邻的船对优，因为我们已经排序了）；
• 排在前面的那艘船一定是北船，排在后面的一定是东船（否则它们永不相撞）；
• 两艘船都还存活。

其他方向的碰撞（南北、东西、北西、南东、南西）是同理的。

抓住可能产生真实碰撞的只在相邻的船对之间，所以考虑用链表动态维护碰撞序列（六种情况）。每次把可能产生贡献的碰撞丢到优先队列，然后不断取队头，删掉相撞的船即可。

补充一下时间复杂度方面的分析。初始我们会往优先队列里面放入 $O(n)$ 个船对贡献。每次删除一艘船时，会产生至多一个新的船对贡献，依旧是 $O(n)$。所以本题复杂度是 $O(n\log n)$，但是至少带 $6$ 倍常数。

实现方面的细节，参考下文。

Code

$\begin{array}{|c|c|c|c|}N(0)&S(1)&E(2)&W(3)\\NS(0)&NS(0)&NE(1)&NW(2)\\NE(1)&SE(3)&SE(3)&SW(4)\\NW(2)&SW(4)&EW(5)&EW(5)\end{array}$

约定标号参考上表格。方向标号 $[0,3]$，碰撞种类标号 $[0,5]$。具体每个碰撞情况的排序关键字就自己画图看看吧，这里不多说。

实现还有一个细节。当我们从优先队列取出碰撞删除时，要先把碰撞时间相同的全部取出来，再一起删，因为可能存在三艘船同时相撞的情况（样例二）。

$3\text{ KB}$，真的写的很良心了。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define per(i, a, b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pip pair<int, pii>
#define fi first
#define se second
#define mkp make_pair

const int maxn = 2e5 + 5;

int n, vis[maxn];
struct node{
    int tp; pii p, v[6];
    pii dir[6];
}a[maxn];
vector<int> b[6];
int tr[4][3] = {{0, 1, 2}, {0, 3, 4}, {1, 3, 5}, {2, 4, 5}};

int NOW;
inline bool cmp(int x, int y){ 
    return a[x].v[NOW] < a[y].v[NOW];
}

priority_queue<pip, vector<pip>, greater<pip> > pq;

inline void calc(int o, int x, int y){
    if(!x or !y or x > n or y > n or vis[x] or vis[y]) return;

    int X = a[x].v[o].se, Y = a[y].v[o].se; 
    pii p = mkp(a[x].tp, a[y].tp);
    if(p.fi == p.se or a[x].v[o].fi != a[y].v[o].fi) return;
    
    if(p == mkp(1, 0) or p == mkp(3, 2)) 
        pq.push(mkp((Y - X) >> 1, mkp(x, y)));
    if(p == mkp(0, 2) or p == mkp(3, 0) or p == mkp(1, 2) or p == mkp(3, 1))
        pq.push(mkp(Y - X, mkp(x, y)));
}

inline void dlt(int x){
    if(vis[x]) return; vis[x] = 1;
    rep(oo, 0, 2){
        int o = tr[a[x].tp][oo];
        int pre = a[x].dir[o].fi, suf = a[x].dir[o].se;
        a[pre].dir[o].se = suf, a[suf].dir[o].fi = pre;
        calc(o, pre, suf);
    }
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    
    cin >> n;
    rep(i, 1, n){
        char ch; int x, y;
        cin >> x >> y >> ch; x = 1e9 - x; 
        if(ch == 'S') a[i].tp = 1; if(ch == 'E') a[i].tp = 2; if(ch == 'W') a[i].tp = 3;
        
        a[i].p = mkp(x, y);
        if(!a[i].tp){
            a[i].v[0] = mkp(x, y), a[i].v[1] = mkp(x + y, x), a[i].v[2] = mkp(x - y, x);
        } else if(a[i].tp == 1){
            a[i].v[0] = mkp(x, y), a[i].v[3] = mkp(x - y, x), a[i].v[4] = mkp(x + y, x);
        } else if(a[i].tp == 2){
            a[i].v[1] = mkp(x + y, x), a[i].v[3] = mkp(x - y, x), a[i].v[5] = mkp(y, x);
        } else{
            a[i].v[2] = mkp(x - y, x), a[i].v[4] = mkp(x + y, x), a[i].v[5] = mkp(y, x);
        }
        
        rep(o, 0, 2) b[tr[a[i].tp][o]].push_back(i);
    }
    
    rep(o, 0, 5) NOW = o, sort(b[o].begin(), b[o].end(), cmp);
    
    rep(o, 0, 5){
        int lst = -1;
        for(auto it = b[o].begin(); it != b[o].end(); ++it){
            int x = *it;
            if(~lst) calc(o, lst, x); lst = x;
            
            if(it == b[o].begin()) a[x].dir[o].fi = 0;
            else a[x].dir[o].fi = *prev(it);
            
            if(next(it) == b[o].end()) a[x].dir[o].se = n + 1;
            else a[x].dir[o].se = *next(it);
        }
    }
    
    while(pq.size()){
        vector<int> tmp; pip ss = pq.top(); tmp.clear();
        while(pq.size() and pq.top().fi == ss.fi){
            pip nw = pq.top(); pq.pop();
            if(vis[nw.se.fi] or vis[nw.se.se]) continue;
            tmp.push_back(nw.se.fi), tmp.push_back(nw.se.se);
        }
        for(int x : tmp) dlt(x);
    }
    
    rep(i, 1, n) if(!vis[i]) cout << i << '\n';
    return 0;
}