AtCoder-ABC-409 题解

比赛速览

• A. 模拟
• B. 枚举
• C. 枚举
• D. 贪心
• E. DFS
• F. 优先队列 + 并查集

A - Conflict

有 $N$ 个物品。给定两个长度为 $N$ 的字符串 $T$ 和 $A$ ，分别表示 Takahashi 和 Aoki 对物品的需求。其中：

• $T_i$ 表示第 $i$ 个物品的 Takahashi 需求状态：
• 当 $T_i=$ o 时，Takahashi 想要该物品；
• 当 $T_i=$ x 时，Takahashi 不想要该物品。
• $A_i$ 表示第 $i$ 个物品的 Aoki 需求状态：
• 当 $A_i=$ o 时，Aoki 想要该物品；
• 当 $A_i=$ x 时，Aoki 不想要该物品。

请判断是否存在至少一个物品，使得 Takahashi 和 Aoki 同时想要该物品。即，是否存在满足以下条件的索引 $i$ $(1\le i\le N)$：

• $T_i=$ o 且 $A_i=$ o 。

B - Citation

给定一个长度为 $N$ 的非负整数序列 $A=(A_1,A_2,\dots ,A_N)$，请找到满足以下条件的最大非负整数 $x$ ：

条件
在序列 $A$ 中，大于或等于 $x$ 的元素（包括重复项）至少出现 $x$ 次。

示例解释

例如，若存在某个 $x=3$ ，则序列中需有至少 3 个元素（可重复）的值 $\ge 3$ 。若同时满足 $x=4$ 时仅有 3 个元素 $\ge 4$，则最大有效 $x$ 为 3。

而A序列最多只有100个数字，也就是数字最多只能出现100次，所以x最大就是100， 从0开始枚举到100， 然后暴力检查是否符合条件即可。

C - Equilateral Triangle

定一个周长为 $L$ 的圆，圆周上按顺时针方向依次放置了 $N$ 个点，编号为 $1,2,\dots ,N$ 。对于每个 $i=1,2,\dots ,N-1$ ，点 $i+1$ 位于点 $i$ 顺时针方向 $d_i$ 距离的位置。

请找出满足以下两个条件的整数三元组 $(a,b,c)(1\le a<b<c\le N)$ 的数量：

1. 位置不同
   三个点 $a$、$b$、$c$ 必须位于圆周上的不同位置。
2. 等边三角形
   以这三个点为顶点的三角形必须是等边三角形。

在圆环上的等边三角形，要求就是三个点之间的弧一样长，可以直接把圆环展开成一条直线，如图。

1. 如果L不是3的倍数，则无解，因为点都在整数位上。
2. 一旦我们选定一个位置$x_i$作为等边三角形的一个顶点，另外两个顶点的位置直接可以计算出来：$x_i+L/3,x+i+L/3+L/3$。
3. 然后三个位置上的点数之积统计进入答案（组合数学，乘法原理）

D - String Rotation

给定一个长度为 $N$ 的由小写字母组成的字符串 $S=S_1{S}_2\dots S_N$。你需要对 $S$ 执行一次如下操作：

操作定义
选择一个长度至少为 1 的连续子串，将其循环左移一位。具体步骤为：

1. 选择区间 $[l,r]$（满足 $1\le l\le r\le N$）；
2. 将子串的第一个字符 $S_l$ 移动到该子串的末尾（即插入到 $r$ 的右侧）；
3. 删除原 $S_l$ 字符。

示例
若子串为 abc，操作后变为 bca。

目标
通过一次上述操作，找到能得到的所有可能字符串中字典序最小的字符串。

字符串贪心。

考虑如下的几个Case：

1. aattaa 和 aattxx。对于第一个，t可以挪到最后面。对于第二个，无法挪动。
2. aattaabcdeaettaxyz, 需要把t一直向后挪动，直到遇到x。

找到第一组相邻的字符满足前大后小的特征，然后一直向后查找，直到找到比这个字符更大的位置。

代码实现即可。

E - Pair Annihilation

给定一棵包含 $N$ 个顶点的树，顶点编号为 $1,2,\dots ,N$ ，边编号为 $1,2,\dots ,N-1$ 。每条边 $j$ 双向连接顶点 $u_j$ 和 $v_j$ ，并具有权重 $w_j$ 。每个顶点 $i$ 被赋予一个整数 $x_i$ ，其含义如下：

• 若 $x_i>0$ ，表示顶点 $i$ 上有 $x_i$ 个正电子；
• 若 $x_i<0$ ，表示顶点 $i$ 上有 $-x_i$ 个电子；
• 若 $x_i=0$ ，表示顶点 $i$ 无粒子。
  保证：所有顶点粒子数之和为 ${\sum }_{i=1}^N{x}_i=0$ 。

粒子移动规则

• 沿边 $j$ 移动一个正电子或电子需消耗 $w_j$ 能量；
• 当正电子与电子处于同一顶点时，会以相等数量成对湮灭。

目标
计算湮灭所有粒子所需的最小总能量。

示例说明

例如，若顶点 $A$ 有 2 个正电子，顶点 $B$ 有 2 个电子，将它们沿权重为 3 的边移动到同一顶点后湮灭，总能耗为 $2\times 3+2\times 3=12$ （需考虑最优路径）。

首先我们可以看出来移动的等价性，无论是正电荷向负电子移动还是负电子向正电荷移动都是等价的。这里的等价性，无论是移动后的终态还是移动产生的代价都是等价的。

其实我们考虑对于一个节点，我们需要知道他具体向不同的邻居分多少去移动，但是这个问题我们不好解决，所以我们考虑将这棵树拎起来以后从叶节点开始考虑。

对于一个业界点节点上的电荷，如果想被中和，那么除非是从父亲移动过来或者向父亲移动，我们又证明了移动的等价性，所以我们将业节点的电荷全部移动到父节点身上，那么所有儿子都移动到父节点身上之后，电荷在父节点会产生一些中和，剩余的电荷，继续向上移动给祖父即可。

综上，我们只需要写一个DFS，实现这个过程就可以了。

F - Connecting Points

给定一个二维平面上的图 $G$ ，包含 $N$ 个顶点和 0 条边。顶点编号为 $1$ 到 $N$ ，其中顶点 $i$ 的坐标为 $(x_i,y_i)$ 。

距离定义

1. 顶点间距离：顶点 $u$ 与 $v$ 的曼哈顿距离为
   $d(u,v)=|x_u-x_v|+|y_u-y_v|$ 。
2. 连通块间距离：对于图的两个连通块 $A$ 和 $B$ （顶点集分别为 $V(A)$ 和 $V(B)$ ），定义其距离为
   $d(A,B)={\min }_{a\in V(A),b\in V(B)}d(a,b)$ 。

需处理 $Q$ 个操作，每个操作属于以下三种类型之一：

1. 添加顶点 1 a b

• 参数
  • a: 新顶点的横坐标
  • b: 新顶点的纵坐标
• 操作
  • 若当前图 $G$ 有 $n$ 个顶点，则添加编号为 $n+1$ 的新顶点，坐标为 $(a,b)$ 。

2. 合并连通分量 2

• 前置条件
• 当前图 $G$ 有 $n$ 个顶点， $m$ 个连通分量。
• 处理逻辑
• 若 $m=1$ （图已连通）：
  • 输出 -1 。
• 若 $m\ge 2$ ：

1. 计算最小距离
   • 对所有连通分量对 $A_i,A_j$ ，计算 $d(A_i,A_j)$ 。
   • 取最小值 $k={\min }_{1\le i<j\le m}d(A_i,A_j)$ 。
2. 添加边
   • 对所有顶点对 $(u,v)$ ，若满足：
     • $u$ 和 $v$ 属于不同连通分量；
     • $d(u,v)=k$ 。
   • 添加边 $u\leftrightarrow v$ 。
3. 输出结果
   • 输出 $k$ 。
4. 查询连通性 3 u v

• 参数
  • u: 顶点编号
  • v: 顶点编号
• 操作
  • 若顶点 $u$ 和 $v$ 属于同一连通分量：输出 Yes 。
  • 否则：输出 No 。

本题其实是一个简单题，只要分析清楚复杂度就可以了。

三种操作中，第二种操作需要我们快速查找距离最近的点对；第三种操作需要我们使用并查集来查询联通块关系，那只剩第一种操作比较难处理。

考虑数据的范围只有1500，所以我们可以预处理除所有点对的距离放入优先队列中，并且当新增一个点的时候，我们也将这个点所产生的所有新点对全部加入优先队列中。这样对于第二个操作，我们只需要从优先对待中取出最小的点对即可。

剩余的部分就是常规操作了。

---

赛后交流
微信号：jikecheng11，赛后大家可以一起交流做题思路，分享做题技巧，欢迎大家的加入！