T1

100%

用三个布尔值记录三盏灯的状态，初始都为关闭。每读到一个编号 $P_i$，就将对应状态取反。三次操作结束后，统计状态为开启的灯数即可。

时间复杂度为 $O(1)$，空间复杂度为 $O(1)$。

T2

100%

不难发现采用从 $0$ 开始的下标时，左移后的字符串满足

$$t[i]=s[(i+k)\bmod n].$$

枚举 $0\le i<n$，统计满足 $s[i]=s[(i+k)\bmod n]$ 的位置数量即可。

时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

T3

100%

设第 $i$ 条通道被多少次任务经过为 $c_i$。如果传送门建在通道 $i$ 上，就能为每个经过它的任务节省 $w_i$ 路程，总节省量为 $w_ic_i$。

对任务区间 $[l_j,r_j]$，它经过的通道编号为 $l_j,l_j+1,\ldots,r_j-1$。利用差分和前缀和即可得到每条通道的 $c_i$。没有传送门时，全部任务的总路程为

$$total=\sum_{i=1}^{n-1}w_ic_i.$$

最优传送门应放在 $w_ic_i$ 最大的通道上，所以答案为

$$total-\max_{1\le i<n}(w_ic_i).$$

时间复杂度为 $O(n+q)$，空间复杂度为 $O(n)$。注意答案可以达到 $10^{17}$ 量级，需要使用 long long。

T4

100%

若 $d$ 合法，则每个出现过的余数都恰好对应两个数。先考虑 $a_1$：必然存在某个 $j>1$，使得 $a_j$ 与 $a_1$ 对 $d$ 同余，即

$$a_j\equiv a_1\pmod d.$$

因此

$$d\mid |a_j-a_1|.$$

这说明任意合法的 $d$，一定是某个 $|a_j-a_1|$ 的正因数。候选集合不需要从 $1$ 枚举到 $10^9$，只需枚举 $a_1$ 与其余各数之差的全部正因数。依次检查是否满足条件即可。若没有因子满足条件，输出 $-1$。

设候选因数个数为 $C$（因数大致个数在 $n* 1000$左右），检查候选的时间复杂度为 $O(nC)$。足够通过本题。

T5

15%（特殊性质 A）

当所有 $a_i$ 相等时，从任意起点出发都能启动相邻站点；由于图连通，最终一定能启动全图，答案为 $n$。

25%

当 $n\le200$ 时，可以对每个起点独立模拟。维护当前总功率以及所有与已启动集合相邻的点，并总是选择其中 $a_v$ 最小的点：若最小值也大于当前总功率，就不可能继续；否则启动它并扩展边界。

选择最小的可用点不会使后续更差，因为启动站点不消耗功率，只会让总功率增加。

100%

为每条边 $(u,v)$ 定义边权

$$w(u,v)=\max(a_u,a_v).$$

也就是说一个点当前权值是 $x$ 时，它想走 $(u,v)$ 这条边，至少需要 $w(u,v)$ 的权值。跨过这条边后，权值还会继续增加。利用这个思路，我们考虑维护连通块内的信息。

将所有边按照 $w$ 从小到大排序，用 Kruskal 的方式维护连通块。每个初始连通块只含一个点 $i$，维护两个量：

• $sum_i=a_i$：块内所有点的权值总和；
• $f_i=1$：能够从块内出发并启动完整个块的起点数量。

当一条边权为 $w$ 的边连接了两个不同连通块 $X,Y$ 时，将它们合并为 $Z$：

$$sum_Z=sum_X+sum_Y,$$ $$good_Z= [sum_X\ge w]\cdot good_X+ [sum_Y\ge w]\cdot good_Y.$$

这里 $[P]$ 表示命题 $P$ 成立时为 $1$，否则为 $0$。

即：从 $X$ 中的一个好起点出发，可以先启动完整个 $X$。若此时 $sum_X\ge w$，就能跨过当前边。此前合并进 $Y$ 的所有边门槛都不超过 $w$，而当前功率已经至少为 $w$，所以进入 $Y$ 后一定可以启动完整个 $Y$。若 $sum_X<w$，则连门槛为 $w$ 的第一条跨块边都无法通过。来自 $Y$ 的起点同理。

时间复杂度为 $O(m\log m+(n+m)\alpha(n))$，空间复杂度为 $O(n+m)$。

T6

25%

固定第一次只采用一种放法，之后枚举其余 $n-1$ 个音符放左还是放右，共有 $2^{n-1}$ 种不同结果。逐个检查最终排列是否相邻大小关系交替即可。

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

100%

依次插入元素时，新元素只会出现在当前序列的最左端或最右端。一次插入只会新产生一组相邻关系，序列内部原有的相邻关系不会改变。因此，如果某个中间序列已经不满足大小关系交替，之后无论怎样插入都无法修复。只需在每一步维护当前序列始终合法。

处理完前若干个元素后，最后加入的元素一定处于某个端点。为了继续转移，只需记录下面三类信息：

• 另一个端点的数值；
• 最后加入的元素位于左端还是右端；
• 当前序列最左侧第一组相邻元素的大小关系。

由前两项可以确定当前左右端点。又因为整个序列的大小关系交替，所以知道第一组相邻元素的大小关系以及当前序列长度的奇偶性后，就能确定最右侧最后一组相邻元素的大小关系，不需要记录序列内部的其他信息。

前两个元素可以形成两种不同序列，分别作为动态规划的初始状态。之后加入一个新元素时分两种情况：

1. 放到左端。比较新元素与原左端点，只有新产生的大小关系与原来的第一组大小关系相反时，序列才仍然合法。转移后，新元素成为左端点，第一组大小关系也随之更新。
2. 放到右端。先根据第一组大小关系和当前长度的奇偶性推出最后一组大小关系。只有新产生的大小关系与它相反时，才允许转移。此时第一组大小关系保持不变。

每次转移都对方案数取模。处理完全部元素后，将所有状态的方案数相加即可。$n=1$ 时只有一个最终排列，答案为 $1$。

这里按插入方式计数不会造成重复。对于任意一个能够得到的最终排列，数值 $p_n$ 一定在某个端点；删去它后，$p_{n-1}$ 也一定在剩余序列的某个端点。不断逆序删除即可唯一还原每一步放在左端还是右端。因此不同的转移过程对应不同的最终排列。

另一个端点有 $O(n)$ 种可能，其余两项都只有常数种取值，所以每一层有 $O(n)$ 个状态，共进行 $n$ 层转移。时间复杂度为 $O(n^2)$，使用滚动数组后空间复杂度为 $O(n)$。