「CEOI2024」海战 题解

算法思路

本题需要模拟多艘战舰在网格上的移动和碰撞过程。由于坐标范围很大（$0 \leq x_i, y_i \leq 10^9$），不能直接模拟每一时间步。我们采用事件驱动模拟的方法，只关注可能发生碰撞的时刻。

关键观察

1. 运动轨迹：每艘船沿固定方向移动

   • N: $(x, y-t)$
   • S: $(x, y+t)$
   • E: $(x+t, y)$
   • W: $(x-t, y)$

2. 碰撞条件：两艘船在时间$t$相撞当且仅当：

   • 它们在某个整数时间$t \geq 1$到达同一位置
   • 曼哈顿距离$|x_i-x_j| + |y_i-y_j|$为偶数且时间$t = \frac{|x_i-x_j| + |y_i-y_j|}{2}$

3. 数据结构：使用多个map来维护不同方向上的船只位置关系，便于快速查找可能碰撞的船只对。

代码实现详解

1. 方向编码与初始化

int mp[256];
mp['S'] = 1;  // 南方向
mp['W'] = 2;  // 西方向  
mp['E'] = 3;  // 东方向
// 注：北方向默认为0

2. 数据结构设计

使用12个map来维护船只信息：

vector<map<int, set<array<int, 2>>>> s(12);

这12个容器的用途：

• 索引 0-3：按$x-y$坐标分组，用于检测45°对角线上的碰撞
• 索引 4-7：按$x+y$坐标分组，用于检测135°对角线上的碰撞
• 索引 8-11：按$x$或$y$坐标分组，用于检测水平/垂直方向的碰撞

3. 核心函数解析

(1) 碰撞检测函数 chk

auto chk = [&](int i, int j) {
    q.push({-abs(x[i] - x[j]) - abs(y[i] - y[j]), i, j});
};

计算两船曼哈顿距离的负值作为优先级，使用最大堆（通过负数实现最小堆效果）来确保最早发生的碰撞先被处理。

(2) 更新函数 upd

这是算法的核心，用于查找可能与船$i$发生碰撞的其他船只：

function<void(int, int)> upd = [&](int i, int o) {
    // 获取三个方向的相关集合
    auto &s0 = s[op[i] ^ 9][op[i] < 2 ? x[i] : y[i]];
    auto &s1 = s[op[i] ^ 3][x[i] - y[i]];
    auto &s2 = s[op[i] ^ 6][x[i] + y[i]];
    
    // 在三个方向上分别查找最近的潜在碰撞目标
    // 使用异或运算快速计算相反方向
};

(3) 删除函数 del

auto del = [&](int i) {
    vis[i] = 1;  // 标记为已沉没
    // 从三个数据结构中移除该船
    s[op[i] + 8][op[i] < 2 ? x[i] : y[i]].erase({op[i] < 2 ? y[i] : x[i], i});
    s[op[i]][x[i] - y[i]].erase({x[i], i});
    s[op[i] + 4][x[i] + y[i]].erase({x[i], i});
};

4. 主算法流程

// 1. 初始化：为每艘船查找可能的碰撞
for (int i = 0; i < n; i++)
    upd(i, 0);

// 2. 事件处理循环
while (1) {
    set<int> id;  // 本轮要沉没的船只
    int mi = -1;  // 当前碰撞时间
    
    // 处理所有同时发生的碰撞
    while (!q.empty()) {
        auto t = q.top();
        if (~mi && -t[0] > mi) break;  // 时间更晚的碰撞留待后续处理
        q.pop();
        if (vis[t[1]] || vis[t[2]]) continue;  // 跳过已沉没的船
        
        mi = -t[0];  // 更新当前碰撞时间
        id.insert(t[1]);
        id.insert(t[2]);
    }
    
    if (mi == -1) break;  // 没有更多碰撞
    
    // 3. 移除沉没船只并更新相关碰撞事件
    for (int i : id) del(i);
    for (int i : id) upd(i, 1);  // 重新检查受影响的船只
}

5. 碰撞检测的几何原理

代码中三个方向的检测对应三种碰撞情形：

1. 水平/垂直方向：相同$x$或$y$坐标，相反运动方向
2. 45°对角线：$x-y$为常数，适合N-E、S-W等方向组合
3. 135°对角线：$x+y$为常数，适合N-W、S-E等方向组合

复杂度分析

• 时间复杂度：$O(N \log N)$，每个船只最多被插入/删除常数次
• 空间复杂度：$O(N)$，存储所有船只信息和事件队列

总结

本题通过巧妙的数据结构设计和事件驱动模拟，避免了暴力模拟的高复杂度。核心在于利用船只运动的几何特性，在三个关键方向上维护有序集合，从而快速检测潜在的碰撞事件。算法保证了在任意大规模坐标范围内都能高效运行。