T1

100%

箭头可分为上半部分的等腰三角形和下半部分的长方形。

等腰三角形部分有 $n$ 行，其中第 $i$ 行先输出 $n - i$ 个空格，再输出 $2\times i-1$ 个 #。

长方形部分有 $n$ 行，每一行先输出 $n-1$ 个空格，在输出一个 #。

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

T2

100%

用 $\text{while}$ 循环模拟游戏过程：

• 如果 $a=b$ 那么游戏结束；
• 否则，判断 $a$ 和 $b$ 的大小关系：如果 $a>b$ 那么本轮令 $a=a-b$，否则本轮令 $b=b-a$。

时间复杂度 $O(a+b)$。

T3

60%

对于每条训练指令：

• 先循环第一遍找到同学 $x_i$ 在队列中的位置；
• 然后循环第二遍将 $x_i$ 左边的同学都向右移动一位；
• 最后将 $x_i$ 放在队列的最左边。

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

100%

对于第一部分，算法的时间复杂度瓶颈在于将 $x_i$ 左边的同学都向右移动一位。

考虑只将 $x_i$ 移动到队列最左边，不将 $x_i$ 左边的同学都向右移动，这样每条训练指令就会在队列中留下一个空位。

用 $a[i]$ 表示从左到右第 $i$ 个位置上同学的编号，$a[i]=0$ 说明这个位置是空位。

用 $p[i]$ 表示同学 $i$ 的位置。

维护当前队列中最左边同学的位置 $L$，为了避免下标出现负数，可以将队列向右平移 $m$ 个位置，即初始时 $L=m+1$，且对于 $i=1\sim n$ 有 $a[m+i]=i$ 和 $p[i]=i+m$。

对于每条训练指令：

• 将同学 $x_i$ 移动到位置 $L-1$，他原本的位置留下一个空位，即 $a[L-1]=x_i$，$a[p_{x_i}]=0$，$p_{x_i}=L-1$，注意这几个操作的顺序；
• 更新 $L=L-1$。

处理完所有训练指令后，用一次循环枚举 $i=1\sim n+m$，如果 $a[i]\neq 0$ 说明这个位置不是空位，那么输出 $a[i]$。

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

T4

50%

两重循环分别枚举 $i=1\sim N$ 和 $j=1\sim N$，答案增加 $\gcd(\gcd(i,N),\gcd(j,N))$。

注意取模。

时间复杂度 $O(N^2\log(N))$。

100%

因为 $i\leq N$ 所以 $gcd(i,N)$ 一定是 $N$ 的因数。$N$ 的不同因数不超过 $\sqrt{N}$ 种。

枚举 $i=1\sim N$，记录 $f[x]$ 表示有多少个 $i$ 满足 $\gcd(i,N)=x$，顺便将 $N$ 的不同因数用一个 $\text{vector}$ 类型的 $P$ 来保存。

两重循环分别在 $P$ 中枚举 $N$ 的因数 $x$ 和 $y$，对应 $\gcd(i,N)=x$ 且 $\gcd(j,N)=y$ 的情况，答案增加 $\gcd(x,y)\times f[x]\times f[y]$。

注意：三个或更多的数相乘可能会超出 $\text{long\ long}$ 范围，要及时取模。

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

T5

60%

考虑第 $i$ 个小组中支持款式 $1$ 的同学的数量为 $num[i]$ 的情况：

• 首先需要保证 $\sum_{i=1}^nnum[i]=a$ 且 恰好有 $x$ 个小组 $num[i]>\lfloor \frac{k}{2}\rfloor$；

• 前 $i-1$ 个小组一共有 $\sum_{j=1}^{i-1}num[j]$ 个同学支持款式 $1$，所以还剩 $a-\sum_{j=1}^{i-1}num[j]$ 个未分组同学支持款式 $1$，$(n-i+1)\times k-(a-\sum_{j=1}^{i-1}num[j])$ 个未分组同学支持款式 $2$；

• 对于第 $i$ 个小组，需要从剩下 $a-\sum_{j=1}^{i-1}num[j]$ 个支持款式 $1$ 的未分组同学中选出 $num[i]$ 个分到当前小组，再从剩下 $(n-i+1)\times k-(a-\sum_{j=1}^{i-1}num[j])$ 个支持款式 $2$ 的未分组同学中选出 $k-num[i]$ 个分到当前小组。

用杨辉三角法预处理所有 $0\leq i\leq n \times k$ 且 $0\leq j\leq i$ 的组合数 $\text{C}_i^j$。

用 $\text{DFS}$ 依次枚举第 $i$ 个小组中支持款式 $1$ 的同学的数量为 $num[i]$，如果 $\sum_{i=1}^nnum[i]=a$ 且 恰好有 $x$ 个小组 $num[i]>\lfloor \frac{k}{2}\rfloor$，答案增加 $\prod_{i=1}^n(\text{C}_{a-\sum_{j=1}^{i-1}num[j]}^{num[i]}\times \text{C}_{(n-i+1)\times k-(a-\sum_{j=1}^{i-1}num[j])}^{k-num[i]})$。

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

100%

定义 $dp[i][j][s]$ 为只考虑前 $i$ 个小组，其中有 $s$ 个同学支持款式 $1$ 且有 $j$ 个小组支持款式 $1$ 的不同分组方案数量，初值为 $dp[0][0][0]=1$。

用四重循环进行转移：

• 第一重循环枚举 $i=1\sim n$；
• 第二重循环枚举 $j=0\sim \min(i,x)$；
• 第三重循环枚举 $s=0\sim \min(a,i\times k)$，此时前 $i$ 个小组中共有 $i\times k-s$ 个同学支持款式 $2$，所以需要保证 $i\times k-s\leq n\times k-a$；
• 第四重循环枚举 $num=0\sim min(k,s)$ 表示第 $i$ 个小组有 $num$ 个同学支持款式 $1$，此时前 $i-1$ 个小组一共有 $s-num$ 个同学支持款式 $1$，所以还剩 $a-(s-num)$ 个未分组同学支持款式 $1$，$(n-i+1)\times k-(a-(s-num))$ 个未分组同学支持款式 $2$；
• 如果 $num>\lfloor\frac{k}{2}\rfloor$ 说明第 $i$ 个小组支持款式 $1$，这种情况下前 $i-1$ 个小组中有 $j-1$ 个小组支持款式 $1$，因此需要保证 $j>0$，转移为 $dp[i][j][s]+=dp[i-1][j-1][s-num]\times \text{C}_{a-(s-num)}^{num}\times \text{C}_{(n-i+1)\times k-(a-(s-num))}^{k-num}$；
• 否则说明第 $i$ 个小组支持款式 $2$，这种情况下前 $i-1$ 个小组中有 $j$ 个小组支持款式 $1$，转移为 $dp[i][j][s]+=dp[i-1][j][s-num]\times \text{C}_{a-(s-num)}^{num}\times \text{C}_{(n-i+1)\times k-(a-(s-num))}^{k-num}$；

答案即为 $dp[n][x][a]$。

注意：三个或更多的数相乘可能会超出 $\text{long\ long}$ 范围，要及时取模。

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

T6

30%

将每个站点，根据时间取模 $k$ 的余数分为 $k$ 个点，这样共有 $n\times k$ 个节点，将站点 $i$ 余数 $j$ 对应的点记作 $(i,j)$。

对于第 $i$ 条公交路线，建一条从 $(u_i,a_i)$ 出发到达 $(v_i,(a_i+t_i)\mod k)$，边权为 $0$ 的有向边。

另外对于每一个站点的每个余数，向同站点余数加一的点建边权为 $1$ 的有向边，表示在站点等待 $1$ 分钟。即分别建从 $(i,j)$ 出发到达 $(i,(j+1) \mod k)$，边权为 $1$ 的有向边。

答案即为从 $(1,0)$ 出发到达任意 $(n,j)$ 的最短路，可以用 $\text{Dijkstra}$ 等单源最短路算法来求。

边的总数规模约为 $E\approx m+n\times k$。

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

60%

对于测试点#4~6，因为 $m\leq 1000$，将每条公交路线视为点，并虚构第 $0$ 条公交路线：$a_0=0,u_0=v_0=1,t_0=0$。

两重循环枚举第 $i$ 条公交路线和第 $j$ 条公交路线，如果满足 $v_i=u_j$，那么建一条从第 $i$ 条公交路线出发到达第 $j$ 条公交路线，边权为 $a_j-((a_i+t_i)\mod k)$ 的有向边。

答案即为从第 $0$ 条公交路线出发到达任意满足 $v_i=n$ 的公交路线的最短路。

边的总数规模约为 $E\approx m^2$。

注意：边权都是模意义下的，所以边权为负数或大于等于 $k$ 时需要调整到 $0\sim k-1$。

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

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

100%

在第一部分的基础上，考虑只留下 $(u_i,a_i)$，以及 $(1,0)$，在它们之间建边。记 $f(x,y)$ 为离散化之后 $(x,y)$ 对应的编号。

对于第 $i$ 条公交路线，建一条从 $f(u_i,a_i)$ 出发到达 $f(v_i,(a_i+t_i)\mod k)$，边权为 $0$ 的有向边。

对于留下的点中位于同一个站点的不同余数，将它们按余数大小排序后，在每个余数向后一个余数建边，边权为后一个余数减去当前余数。比如留下的点中有 $cnt[i]$ 个位于站点 $i$，余数从小到大依次为 $p_1,p_2,\dots,p_{cnt[i]}$，分别建从 $f(i,p_j)$ 出发到达 $f(i,p_{j+1\mod cnt[i]})$，边权为 $p_{j+1\mod cnt[i]}-p_j$ 的有向边。

答案即为从 $(1,0)$ 出发到达任意 $(n,j)$ 的最短路。

边的总数规模约为 $E\approx 3\times m$。

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