T1

问题分析

我们需要处理两种操作：

1. 合并操作（M i j）：将第i号魔法阵中的所有魔法师合并到第j号魔法阵的末尾。
2. 查询操作（C i j）：查询第i号和第j号魔法师是否在同一魔法阵中，如果是，计算他们之间的距离（间隔的魔法师数目）。

数据结构选择

这类动态合并和查询问题通常可以使用**并查集来解决。但普通的并查集只能处理合并和查询是否在同一集合的问题，无法直接计算集合内元素之间的距离。因此，我们需要对并查集进行扩展，以支持距离计算。

带权并查集

我们可以使用带权并查集，其中每个节点维护到其父节点的距离。通过路径压缩和按秩合并，可以高效地处理合并和查询操作。

具体来说：

• 父数组（fa）：记录每个节点的父节点。
• 距离数组（d）：记录每个节点到其父节点的距离。
• 大小数组（s）：记录每个集合的大小。

操作实现

1. 合并操作（M i j）：

   • 找到i和j的根节点（root_i和root_j）。
   • 将root_i的父节点设为root_j。
   • 更新root_i到root_j的距离为root_j的当前大小（因为i的魔法师会接在j的末尾）。
   • 更新root_j的大小（增加root_i的大小）。

2. 查询操作（C i j）：

   • 检查i和j是否在同一集合（根节点相同）。
   • 如果不在同一集合，返回-1。
   • 否则，计算i和j到根节点的距离，然后他们之间的距离为 |d[i] - d[j]| - 1。

路径压缩

在查找根节点时，进行路径压缩以优化后续查询。同时需要更新距离：

• 递归找到根节点。
• 在回溯时，累加父节点的距离到当前节点。

T2

题目分析

这道题目是一个经典的并查集应用问题，通常被称为"食物链"问题。我们需要处理三种类型的生物（或法师学派）之间的环形克制关系，并判断给定的K条陈述中有多少是谎言。

解题思路

1. 并查集扩展：使用带权并查集来维护每个节点与根节点之间的关系。这里的"权"表示当前节点与父节点之间的关系类型。
2. 关系定义：
   • 0：和根节点同类
   • 1：克制根节点
   • 2：被根节点克制
3. 路径压缩：在查找过程中维护节点与根节点的关系。
4. 合并判断：在合并两个集合时，根据给定的关系类型计算是否冲突。

T3

题目理解

题目要求我们计算从城市1到城市N的最短路径的数量。由于道路是无向的且每条道路耗时相同（1小时），我们可以使用广度优先搜索（BFS）来找到最短路径，并在过程中统计最短路径的数量。

方法思路

1. BFS遍历：使用BFS来分层遍历城市，确保我们首先找到最短路径。
2. 动态统计路径数：在BFS过程中，维护两个数组：
   • dist[i]：记录城市i到城市1的最短距离。
   • cnt[i]：记录从城市1到城市i的最短路径数量。
3. 分层处理：对于每一层的城市，我们只处理那些未被访问过的城市，或者距离等于当前层数的城市（表示这是另一条最短路径）。

T4

题目大意

有一个有 N 级台阶的楼梯，编号从 1 到 N。你从第 0 级开始，每次可以向上迈 1 级或 2 级台阶。但是有 M 个台阶是坏的（a_1, a_2, ..., a_M），不能踏上去。求到达第 N 级台阶的不同走法数量，结果对 1e9+7 取模。

解题思路

这是一个典型的动态规划问题。我们可以定义 dp[i] 表示到达第 i 级台阶的走法数量。

状态转移方程：

• 如果第 i 级台阶是坏的，dp[i] = 0
• 否则，dp[i] = dp[i-1] + dp[i-2]（因为可以从 i-1 或 i-2 级台阶迈上来）

初始条件：

• dp[0] = 1（起点）
• dp[1] = 0 或 1，取决于第1级台阶是否坏掉

注意事项

1. 需要处理模数 1e9+7
2. 坏掉的台阶需要特殊处理
3. 数组下标不要越界

T5

题意

给定一个无向图（$n$个顶点，$m$条边），每个顶点有权值$a_i$。求从顶点$1$到顶点$n$的简单路径，满足路径上顶点权值非递减，且路径的美丽值为路径中不同权值的数量。输出美丽值的最大值，若不存在合法路径则输出$0$。

---

算法思路

1. 权值约束处理：
   仅保留满足$a_u \leq a_v$的边，舍弃$a_u > a_v$的边，确保路径权值非递减。

2. 并查集缩点：
   将权值相同的连通顶点合并为超级节点，缩点后图变为DAG（有向无环图）。

3. 动态规划（DP）：

   • 状态定义：$dp[u]$表示从顶点$1$到超级节点$u$的最大美丽值。
   • 转移方程：
     • 若$a_u = a_v$，则$dp[v] = \max(dp[v], dp[u])$（权值相同不增加美丽值）。
     • 若$a_u < a_v$，则$dp[v] = \max(dp[v], dp[u] + 1)$（权值增加时美丽值+1）。

4. 排序优化：
   按超级节点的权值升序处理，保证DP转移的顺序性。