题解：P10801 [CEOI2024] 海战
pldzy
·
·
题解
提供一篇码风友好，码量友好，题解语言友好易读的题解。
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]。具体每个碰撞情况的排序关键字就自己画图看看吧，这里不多说。
实现还有一个细节。当我们从优先队列取出碰撞删除时，要先把碰撞时间相同的全部取出来，再一起删，因为可能存在三艘船同时相撞的情况（样例二）。
````cpp
#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;
}
````