T1

100%

直接判断 $a+b$ 是否小于等于 $10$ 即可，若满足则输出 Yes，否则输出 No。

时间复杂度 $O(1)$ 。

T2

100%

用 $0,1,2,3$ 分别表示北（N）、东（E）、南（S）、西（W）四个方向。初始方向由输入字符确定对应编号。

对于每一步操作：

• 若为 L（向左转），则方向编号更新为 $(now + 3) \bmod 4$（逆时针 $90°$）；
• 若为 R（向右转），则方向编号更新为 $(now + 1) \bmod 4$（顺时针 $90°$）。

每转一次就输出当前对应的方向字符即可。

时间复杂度 $O(n)$ 。

T3

100%

由于 $n,x,y$ 的范围较小（不超过 $5000$），可以直接模拟，求出矩阵 $a$ 每一行的元素，依次计算矩阵 $a$ 的每一行，直到计算出第 $\max(x,y)$ 行：

1. 第一行为初始排列，即 $a_{1,i} =p_i$；
2. 遍历 $k=2,3,\cdots$，利用 $a_{k,i}=a_{k-1,p_{i}}$ 依次计算第 $k$ 行的结果；
3. 在计算过程中，若当前次数等于 $x$ 或 $y$，则将结果分别记录到 $vx$ 和 $vy$；
4. 最后逐位比较 $vx$ 与 $vy$ 的字典序，输出 <、> 或 =。

时间复杂度 $O(n \cdot \max(x,y))$ ，空间复杂度 $O(n \cdot \max(x,y))$，空间可以通过滚动数组优化至 $O(n)$。

T4

40%

当 $n \leq 3000$ 时，直接 $O(n^2)$ 枚举所有数对 $(i,j)$ 然后计算答案即可。

100%

当 $n \leq 10^6$ 时，我们需要寻找更快速的方法计算。

首先，观察表达式：

$$|a_i-a_j| \times (a_i+a_j)$$

如果 $a_i \ge a_j$，则 $|a_i-a_j|=(a_i-a_j)$，表达式变为：

$$(a_i-a_j)(a_i+a_j)=a_i^2-a_j^2$$

如果 $a_i < a_j$，则 $|a_i-a_j|=(a_j-a_i)$，表达式变为：

$$(a_j-a_i)(a_i+a_j)=a_j^2-a_i^2$$

我们发现，无论 $a_i$ 和 $a_j$ 的大小关系如何，结果总是较大数的平方减去较小数的平方：

因此我们可以将数组排序，使大小关系明确。设排序后的数组为 $b_1 \leq b_2 \leq \cdots \leq b_n$，对于任意 $i<j$，有 $b_i \leq b_j$，有趣值为：

$$b_j^2-b_i^2$$

总和为：

$$\sum_{i=1}^n \sum_{j=i+1}^n (b_j^2-b_i^2)$$

接下来，考虑每个元素 $b_k$ 的贡献：

• 当 $b_k$ 作为较大值（即与前面较小或相等元素配对）时，次数为 $k-1$，贡献 $+ b_k^2$
• 当 $b_k$ 作为较小值（即与后面较大或相等元素配对）时，次数为 $n-k$，贡献 $- b_k^2$

因此 $b_k$ 的总贡献系数为（相同元素的贡献会互相抵消，因此不需要特殊考虑）：

$$(k-1)-(n-k)=2k-n-1$$

总和即为：

$$\sum_{k=1}^n (2k-n-1) \cdot b_k^2$$

计算答案时需要累加并取模，注意不要漏取模，特别是 $(2k-n-1) \cdot b_k^2$ 的部分。

时间复杂度 $O(n \log n)$，空间复杂度 $O(n)$。

T5

100%

本题存在 $O(n3^n)$ 与 $O(3^n)$ 的做法。

解法 1 （$O(n3^n)$）

题目要求将 $n$ 个同学划分为恰好 $k$ 个非空小组，每个小组 $t$（用二进制位掩码表示）有权值 $a[t]$，且至少有一个小组只包含 $1$ 位同学。在所有满足条件的划分方案中，求各小组合作效果之和的最大值。

观察到 $n \leq 15$，可以用状压 DP 枚举所有分组方式。“至少有一个大小为 $1$ 的小组”这一限制，可以在 DP 中额外记录是否已经出现过大小为 $1$ 的小组（也可以不记录这一维，最后计算答案时再处理）。

设 $dp[st][k][0/1]$ 表示：

• 已经分配好的同学集合为 $st$；
• 这些同学被分成了 $k$ 个集合；
• 第三维为 $0$ 表示目前还没有大小为 $1$ 的小组，为 $1$ 表示已经出现。

初始化 $dp[0][0][0]=0$，其余状态为负无穷。目标答案：对于每个 $k=2\dots n$，输出 $dp[(1 \ll n)-1][k][1]$。

转移时先从 $1 \sim ((1 \ll n)-1)$枚举当前状态 $st$，然后枚举 $st$ 的非空子集 $t$ 作为最新划分出的子集，之前已分组的集合为 $st \oplus t$（“$\oplus$”表示按位异或）：

• 常态转移：$dp[st][k][0] = max(dp[st][k][0], dp[st \oplus t][k-1][0] + a[t])$ 和 $dp[st][k][1] = max(dp[st][k][1], dp[st \oplus t][k-1][1] + a[t])$
• 若 $t$ 中只包含一个人（即 $t$ 是 $2$ 的幂次，可以用 t & (t - 1) == 0 判断），则可以从 $dp[st \oplus t][k-1][0]$ 转移到 $dp[st][k][1]$

时间复杂度 $O(3^n \cdot n)$，枚举子集 $O(3^n)$，还需 $O(n)$ 枚举 $k$。空间复杂度 $O(2^n n)$。

PS：可以不记录是否出现过大小为 $1$ 的小组，而是在最后统计答案时，强制最后一组为 $1$ 人小组，记状态为 $t$（$t$ 为 $2$ 的幂次），然后从 $dp[((1 \ll n)-1) \oplus t][k-1]$ 累加答案即可。

解法 2 （$O(3^n)$）

与解法 $1$ 类似，我们考虑优化枚举的状态。

回忆一下 $dp[st][k][0/1]$ 的状态：

• 已经分配好的同学集合为 $st$；
• 这些同学被分成了 $k$ 个集合；
• 第三维为 $0$ 表示目前还没有大小为 $1$ 的小组，为 $1$ 表示已经出现。

那么我们可以发现，假设我们每次都去枚举最小的不在 $st$ 中的元素，那么 $st$ 的从低到高的前 $k$ 位一定都是 $1$，所以我们可以钦定转移时状态的前 $k$ 位均是 $1$，用解法 $1$ 的方式进行转移。这样不会漏掉需要转移的状态。

时间复杂度怎么计算？可以发现对于 $dp[st][k][0/1]$，当 $k$ 固定时我们只用枚举高位的 $n - k$ 位。故每一层的枚举状态是 $O(3^{n - k})$，总的枚举状态个数大致为： $\sum_{k = 1}^{n} 3^{n - k} = \frac{(3^{n} - 1)}{2} = O(3^n)$。

故时间复杂度为 $O(3^n)$。

T6

40%

第 $i$ 个人参加活动的条件是区间 $[l_i,r_i]$ 内的所有人都参加了活动。

首先，我们可以将条件转化为逆否命题：如果存在某个人 $j$ 无法参加活动，那么对于所有满足 $j \in [l_i,r_i]$ 的人 $i$，也不能参加活动。

这就形成了一个连锁反应（推导关系）：已知 $1$ 号不参加，所有区间包含 $1$ 的人都不能参加；这些不能参加的人又会进一步导致包含他们的人不能参加，以此类推。

这个过程可以通过 BFS（或 DFS）来求解，初始将 $1$ 号加入“不参加”队列。每次从队列中取出一个不参加的人 $x$，然后枚举 $i$ ，我们需要找到所有满足 $l_i \leq x \leq r_i$ 的人 $i$，如果 $i$ 尚未被标记为不参加，则将其标记并入队。

如果每次取出 $x$ 时都暴力扫描所有人的区间，时间复杂度为 $O(n^2)$，仅可以通过 $40\%$ 的数据。

100%

解法 1

接下来我们需要快速地找到所有包含点 $x$ 的区间。

首先我们还需要对问题进一步转化：

对于第 $i$ 个人的区间 $[l_i,r_i]$，将 $[l_i,r_i]$ 中的每个点向 $i$ 连一条指向 $i$ 的有向边，当该区间中的某个点无法参加活动时，可以通过这条有向边传播，使得 $i$ 也无法参加活动。

于是我们可以在图上 BFS 求出有多少人无法参加活动：

1. 初始将 $1$ 号加入“不参加”队列。
2. 每次从队列中取出一个不参加的人 $x$，枚举 $x$ 的邻居 $v$，如果 $v$ 尚未被标记为不参加，则将其标记并入队。
3. 最终答案为总人数减去无法参加的人数。

最坏情况下会有 $O(n^2)$ 条边，因此时间复杂度还是 $O(n^2)$，但由于连边时是 $[l_i,r_i]$ 中的所有点连向 $i$，该操作类似于区间修改，于是便有了线段树优化建图的技巧。

利用线段树优化建图：

1. 建立一棵覆盖 $[1,n]$ 的线段树，树上每个节点代表一个区间，每个叶子节点对应原图中的一个点；
2. 对于每个人 $i$ 对应的区间 $[l_i, r_i]$，将其拆分为 $O(\log n)$ 个线段树节点，并在这些线段树节点向 $i$ 对应的叶子节点连边；
3. 线段树中所有子节点向父节点连有向边。当某个叶子节点 $x$ 被标记为不参加时，可以通过线段树向上传递到所有覆盖 $x$ 的区间节点，进而通过这些区间节点连向其他叶子节点 $i$ 的边，使得 $i$ 也无法参加活动。

建完图后只需要从 $1$ 号叶子开始 BFS，统计所有可达的叶子数量，最终答案为 $n$ 减去可达叶子数。

时间复杂度：建图和 BFS 都是 $O(n \log n)$，因此总体 $O(n \log n)$。空间复杂度 $O(n \log n)$。

解法 2

对于每个人 $i$，有一个区间 $[l_i,r_i]$。如果当前是 $x$ 要离开，那么需要找所有满足 $l_i\le x\le r_i$ 的区间。

故我们按照左端点 $l_i$ 分桶。对于每个左端点 $L$，维护所有 $l_i=L$ 的区间，并按照 $r_i$ 从大到小排序。

然后建一棵线段树。线段树的第 $L$ 个位置维护当前还没有被删掉的、左端点为 $L$ 的区间中，最大的右端点 $r_i$。

当处理坏点 $x$ 时，只需要在线段树中查询前缀 $[1,x]$ 的最大右端点。

1. 如果最大右端点 $<x$，说明不存在满足 $l_i\le x\le r_i$ 的区间；
2. 如果最大右端点 $\ge x$，说明找到了一个包含 $x$ 的区间，对应的人 $i$ 就不能参加这个活动，并从数据结构中删除这个区间。

不断重复这个过程，直到找不到新的区间为止。

每个区间最多被删除一次，所以总复杂度是 $O(n\log n)$，空间复杂度是 $O(n)$。