### NEERC 2015 – 东北欧区域赛概览与问题解析
#### 概述
NEERC 2015（东北欧区域赛）是ACM ICPC（国际大学生程序设计竞赛）2015-2016赛季的一部分，由Roman Elizarov在2015年12月6日撰写的赛后总结。本次比赛吸引了224支队伍参加，共设12个题目，在5小时内进行。作为第20届赛事，它具有里程碑意义。本文将基于给出的信息，详细介绍部分题目及其解决方案。
#### Problem A: Adjustment Office
**题目概述**：
- 一个$n \times n$的网格，每个单元格$(x, y)$的值为$x + y$。
- 对于任意一行或一列$k$，其初始总和等于$n \cdot k + \frac{n(n+1)}{2}$。
- 维护两组数据：被清除的行集合$S_r$和被清除的列集合$S_c$，初始时均为空集。
- 维护两个总和$s_r$和$s_c$，分别表示未被清除的行和列的总和，初始值均为$\frac{n(n+1)}{2}$。
- 行查询“R r”结果为：
- 若$r \notin S_r$，则结果为$\left(\binom{n-|S_c|}{r} + s_c\right)$；否则，结果为0。
- 若$r \notin S_r$，则更新$S_r \leftarrow S_r \cup \{r\}$和$s_r \leftarrow s_r - r$。
- 列查询处理方式类似。
**解决思路**：
- 使用哈希表存储$S_r$和$S_c$，以及维护$s_r$和$s_c$。
- 查询操作需判断行或列是否已被清除，并相应地计算结果。
- 更新操作时，只需简单地修改哈希表中的状态和对应的总和值。
#### Problem B: Binary vs Decimal
**题目概述**：
- 输入一系列整数，每个整数可能用二进制或十进制表示。
- 需要确定每个整数的表示形式，并转换成另一种形式。
- 输出所有转换后的整数列表。
**解决思路**：
- 对于每个输入数字，检查其是否包含非0、1字符，如果有，则认为该数字是十进制表示。
- 如果没有非0、1字符，则通过比较数字的大小来区分二进制和十进制。例如，如果数字大于等于2，则一定是十进制；否则，可能是二进制。
- 转换操作可以通过标准库函数实现，如Python中的`int(str, base)`函数。
#### Problem C: Cactus Jubilee
**题目概述**：
- 给定一棵树形结构，其中某些节点被标记为特殊节点（称为“仙人掌”节点），这些节点形成了一个仙人掌形状的子图。
- 需要找到一个最小的节点集合，使得删除这些节点后，所有的仙人掌节点不再连接。
- 即求解最小顶点覆盖问题。
**解决思路**：
- 构建图的数据结构，使用DFS或BFS遍历树形结构，寻找所有仙人掌节点之间的连接关系。
- 应用贪心算法或图论中的最小顶点覆盖算法（例如，二分图匹配算法），找到最小顶点覆盖集。
- 可以通过优化搜索算法来提高效率，避免不必要的遍历。
#### Problem D: Distance on Triangulation
**题目概述**：
- 给定一个三角剖分的多边形，其中每个三角形都已标号。
- 需要计算两点之间的最短距离，两点之间的路径必须经过三角形的边界。
- 特别注意，多边形可以自相交。
**解决思路**：
- 使用图论中的最短路径算法（如Dijkstra算法）。
- 首先构建一个图，其中每个节点代表一个三角形，边表示相邻三角形之间的连接。
- 计算两点之间经过的三角形序列，然后应用最短路径算法找到最短路径。
- 处理自相交情况时，需要额外考虑三角形的顺序和方向。
#### 总结
NEERC 2015提供了多个具有挑战性的题目，涵盖了数据结构、图论、搜索算法等多个方面。通过对这些问题的研究，不仅能提升参赛者在算法设计和编程实现方面的能力，还能加深对计算机科学基础理论的理解。希望本篇文章能帮助读者更好地理解这些题目及解决方案。
