T1

100%

分离出 $X$ 的百位 $a$、十位 $b$、个位 $c$，可以参考以下代码：

a = X / 100;
b = (X - a * 100) / 10;
c = X % 10;

答案为 $a+b\times 10+c\times 100$。

注意：由于前导 $0$ 不输出，所以不能直接输出 $c$,$b$,$a$。

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

T2

100%

输入字符串后逐位判断，如果遇到 D、M、Y 这三种字符就输出。

注意在过程中记录是否出现过这三种字符，如果没出现，最后要输出 $-1$ 作为答案。

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

T3

20%

枚举 $A_1$ 的质因数 $p$，找到后不断将 $A_1$ 除以 $p$，计算出指数 $k$，然后输出 $p$ 和 $k$。

记 $A_i$ 的最大值为 $V=\max\{A_i\}$。

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

40%

将 $A_1$ 与 $A_2$ 相乘计算出 $X=A_1\times A_2$，$X$ 最多只会有一个超过 $\sqrt X$ 的质因数存在，因此我们枚举质因数时只需要枚举到 $\sqrt {X}$ 即可。

注意不要漏掉大于 $\sqrt{X}$ 的那个质因数。

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

100%

对两个或更多个整数的乘积，进行因式分解的结果，等价于对每个整数因式分解后，将相同质因数的指数相加。

所以我们找到 $A_i$ 的质因数 $p$ 并计算出对应指数 $k$ 后，令 $ans[p]+=k$。

都处理完后，按顺序将 $ans[i]\neq0$ 的项输出即可。

时间复杂度 $O(n\sqrt V+V)$。

T4

20%

先枚举哪位同学今天不问问题，再 $O((n-1)!)$ 枚举剩下同学的排队顺序，过程中计算等待的总时间。

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

40%

对于今天问了问题的同学，他们按 $a_i$ 从小到大的顺序排队能让等待时间的总和最小。

将同学按 $a_i$ 从小到大的规则排序。因为输出答案时要按同学的编号输出，所以我们可以将每个同学的所需时间 $a$ 和编号 $no$ 放在结构体 $p$ 里一起排序。

两重循环，第一重循环枚举今天不问问题的是同学 $i$，第二重循环计算剩下 $n-1$ 名同学的等待总时间，计算时跳过第 $i$ 名同学。

计算出的答案可以储存在 $ans[p[i].no]$ 里，这样便于按编号输出。

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

60%

先考虑如果 $n$ 个同学今天都问了问题，这种情况下 $n$ 个同学的等待时间的总和为 $tmp$。

在这个基础上，考虑仅将第 $i$ 名同学从队伍中去掉，那么等待总时间减去 $i$ 的等待时间，并且排他后面的每一位同学的等待时间减去 $a_i$。

用 $cnt[x]$ 表示 $a_i=x$ 的同学数量。维护 $a_i\leq x$ 的同学数量 $S1[x]=\sum_{i=1}^xcnt[i]$，以及 $a_i\leq x$ 的同学的 $a_i$ 之和 $S2[x]=\sum_{i=1}^xcnt[i]\times i$。

预处理 $S1[x]$ 和 $S2[x]$。

可以将 $i$ 的位置视为所需时间相同的同学中的最后一个，那么 $i$ 原本的等待时间 $t=S2[a_i]-a_i$，$i$ 后面的人数 $k=n-S1[x]$。

记 $a_i$ 的最大值为 $V=\max\{a_i\}$。

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

100%

排序后维护属性 $a$ 的前缀和 $sum[i]=\sum_{j=1}^ip[j].a$。

如果同学 $i$ 排序后位于第 $j$ 名，那么他原本的等待时间 $t=sum[j-1]$，他后面的人数 $k=n-j$。

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

T5

20%

三重循环，外层两重循环枚举区间的左右端点 $l$ 和 $r$，内层循环计算区间 $[l,r]$ 的异或和 $XORsum(l,r)$。

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

60%

因为 $a\oplus b\oplus b=a$，所以前缀异或和具有可差分的性质，即 $XORsum(l,r)=XORsum(1,r)\oplus XORsum(1,l-1)$。

因此我们只需要预处理 $A$ 的前缀异或和 $S[i]$，然后用两重循环枚举区间的左右端点，用 $XORsum(l,r)=S[r]\oplus S[l-1]$ 来 $O(1)$ 计算区间的异或和。

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

100%

注意到计算两个数的异或结果 $a\oplus b$ 时，二进制下的每一位是独立的。

这意味着如果只看二进制下第 $i$ 位，$S[r]$ 和 $S[l-1]$ 不一样，那么 $XORsum(l,r)$ 在二进制下第 $i$ 位为 $1$。

因此我们只需要维护 $cnt[i][j]$ 表示 $S[0]、S[1]、\dots S[i]$ 中有多少项在二进制下第 $j$ 位上是 $1$。

枚举右端点 $r$，再枚举二进制下第 $i$ 位，根据 $S[r]$ 在这一位上是 $1$ 还是 $0$，答案增加 $(r-cnt[r-1][i])\times 2^i$ 或 $cnt[r-1][i]\times 2^i$。

记 $A_i$ 的最大值为 $V=\max\{A_i\}$。

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

T6

10%

将 $n^2$ 个路口都保留。

由于路口的转向限制，需要把每个路口拆成 $4$ 个点对应四个方向。

对于两个距离为 $1$ 的相邻路口，在拆出来的对应方向的点之间建边，例如：对于两个相邻路口 $a$ 和 $b$，$b$ 在 $a$ 右侧，那么建一条从 $a$ 拆出的对应右的点出发，到达从 $b$ 拆出的对应右的点的有向边。

对于测试点#1，因为 $k=0$，用 $\text{BFS}$ 求出起点到终点的最短距离即可。对于允许转向的路口，还需要考虑转向问题，例如：对于两个相邻路口 $a$ 和 $b$，$b$ 在 $a$ 右侧且路口 $a$ 可以转向，那么还要再建 $3$ 条有向边，分别从 $a$ 拆出的对应左、上、下的点出发，到达从 $b$ 拆出的对应右的点。

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

40%

将 $n^2$ 个路口都保留。

对于测试点#2~4，因为 $k\neq 0$，所以需要使用 $\text{Dijkstra}$ 等单源最短路算法来求最短路。

对于同一个路口拆出来的四个点，如果这个路口是允许转向的，在它们之间建边权为 $k$ 的双向边。

除了拆点后向四个方向建边，还需要在拆出来的点之间建边，所以边的总数规模约为 $E\approx 4\times n^2+12\times m$。

时间复杂度 $O(E\log(E))$。

结合第一部分可以拿到 $40\%$ 的分数。

60%

对于测试点#5~6，$n$ 的范围达到 $10^9$，所以只留下起点路口、终点路口、和允许转向的路口作为图上的点，在它们之间建边。

因为 $k=0$，所以不需要拆点。

可以用双关键字排序，处理出同一行或同一列的点来建边。注意：每个路口只能和某一方向最近的那个点建边，否则边数有可能达到 $m^2$。

每个点最多向四个方向的最近点各建一条边，所以边的总数规模约为 $E\approx 4\times m$。

时间复杂度 $O(E\log(E))$。

结合第二部分可以拿到 $60\%$ 的分数。

100%

对于 $k\neq 0$ 的情况，要把每个路口拆成 $4$ 个点对应四个方向。

除了拆点后向四个方向建边，还需要在拆出来的点之间建边，所以边的总数规模约为 $E\approx 16\times m$。

时间复杂度 $O(E\log(E))$。