「ROI 2025 Day2 T2」沼泽青蛙 题解

题目分析

我们有 $n$ 个坐标点（土丘），青蛙可以在距离不超过 $r$ 的点之间跳跃，每次跳跃颜色反转。对于每个起点，需要判断是否存在一条回路，使得：

• 回到起点
• 跳跃次数为奇数（从而颜色与初始相反）

关键观察

1. 图论建模

将土丘视为无向图的顶点，如果两点间欧几里得距离 $\le r$，则在它们之间连一条无向边。

2. 奇偶性与二分图

• 每次跳跃颜色反转 ⇒ 跳跃次数对应颜色变化
• 回到起点时颜色相反 ⇔ 跳跃次数为奇数
• 问题转化为：图中是否存在包含该点的奇环（长度为奇数的环）

3. 二分图性质

• 如果一个连通分量是二分图，则所有环的长度都是偶数
• 如果一个连通分量不是二分图，则存在奇环
• 关键结论：对于非二分图的连通分量，所有顶点都能满足条件（输出 1）；对于二分图连通分量，所有顶点都不满足条件（输出 0）

算法思路

步骤1：构建图结构

由于 $n \le 10^5$，不能直接 $O(n^2)$ 建边。需要优化：

• 使用网格划分或KD树等空间数据结构
• 将点分配到 $r \times r$ 的网格中，只需检查相邻网格的点
• 对于每个点，只检查周围 $3 \times 3$ 网格内的点

步骤2：连通分量与二分图检测

对每个连通分量进行 BFS/DFS：

• 尝试进行二分图着色（二染色）
• 如果着色过程中发现冲突 ⇒ 存在奇环 ⇒ 该分量所有点答案为 1
• 如果成功着色 ⇒ 是二分图 ⇒ 该分量所有点答案为 0

步骤3：输出结果

根据每个点所在连通分量的性质，输出对应的 0 或 1。

算法细节

网格划分优化

// 将点分配到网格
int get_grid_id(int x, int y) {
    return (x / r) * GRID_SIZE + (y / r);
}

// 检查相邻网格的点
for (int dx = -1; dx <= 1; dx++)
    for (int dy = -1; dy <= 1; dy++)
        check_grid(current_grid_x + dx, current_grid_y + dy);

二分图检测

bool is_bipartite = true;
vector<int> color(n, -1);
queue<int> q;

color[start] = 0;
q.push(start);

while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : adj[u]) {
        if (color[v] == -1) {
            color[v] = color[u] ^ 1;
            q.push(v);
        } else if (color[v] == color[u]) {
            is_bipartite = false;
        }
    }
}

复杂度分析

• 建图：使用网格划分，每个点平均检查 $O(1)$ 个相邻网格，期望 $O(n)$
• 连通分量分析：BFS/DFS 遍历，$O(n + m)$，其中 $m$ 是边数
• 总复杂度：期望 $O(n)$，最坏 $O(n^2)$（当点分布极密集时）

特殊情况处理

子任务5：所有点在x轴上（$y_i = 0$）

• 简化为一维问题
• 可以使用滑动窗口或排序后扫描线优化

子任务6-8：$r$ 很小

• 可以直接暴力建图，复杂度可接受

子任务9：点间距离 ≥ $r/2$

• 保证每个点的度数不会太大
• 简化了图的稀疏性

样例验证

样例输入

6 5
4 1
4 4
1 5
5 9
9 6
10 2

输出：111000

分析：

• 前3个点形成一个连通分量且包含奇环 ⇒ 输出 111
• 后3个点可能形成二分图或无环 ⇒ 输出 000

总结

本题的核心是将几何问题转化为图论问题，利用二分图的奇环性质来判定可行性。通过空间划分优化建图过程，使得算法能够处理大规模数据。

算法标签：图论 二分图 连通分量 几何优化 BFS/DFS 网格划分