本次挑战赛的难度有挑战赛的难度。听君一席话,如听一席话
T1
直接拓扑排序一下即可。注意可能有非 111 源点,需要把这些点的路径数量设为 000 再加入搜索队列,时间复杂度 O(n+m)O(n+m)O(n+m)。
T2
无论如何旋转都一样,相当于对于每一个 1≤i,j≤n1\leq i,j\leq n1≤i,j≤n,都有 a[i][j]=a[j][n−i+1]=a[n−j+1][i]=a[n−i+1][n−j+1]a[i][j]=a[j][n-i+1]=a[n-j+1][i]=a[n-i+1][n-j+1]a[i][j]=a[j][n−i+1]=a[n−j+1][i]=a[n−i+1][n−j+1]。因此,我们考虑将这些字符中的最大值分别减去每一个字符,得到的结果即为让这四个字符相同需要的操作次数。时间复杂度 O(n2)O(n^2)O(n2)。
T3
考虑对 aj−ai=j−ia_j-a_i=j-iaj −ai =j−i 条件进行变换:aj−j=ai−ia_j-j=a_i-iaj −j=ai −i。因此我们可以求出对于每一个 i≤ni\leq ni≤n 的 ai−ia_i-iai −i,并对其进行桶计数。容易得出,若一个桶内有 xxx 个元素,则这个桶对答案的贡献为 x(x−1)2\dfrac{x(x-1)}22x(x−1) 。时间复杂度 O(n)O(n)O(n)。
实现时有一些小细节:答案要开 long long,并且桶可能被放入负数,可以考虑对每一个放入桶中的元素都 +2×105+2\times 10^5+2×105。
T4
直接广搜即可,步长分别为 (−2,−2),(2,−2),(−2,2),(2,2)(-2,-2),(2,-2),(-2,2),(2,2)(−2,−2),(2,−2),(−2,2),(2,2)。时间复杂度 O(n2)O(n^2)O(n2)。
T5
发现 nnn 的数据范围极小,考虑暴力搜索。直接深搜即可。发现答案差值不会太大(不会超过 10910^9109),为了避免爆 long long,可以在 lil_ili 过大(大约 101010^{10}1010)时直接剪枝即可。但是过程中仍然可能爆 long long(646464 位乘 323232 位时),由于我不想写高精度,就用了 long long long long __int128。时间复杂度(大约) O(2n)O(2^n)O(2n)。
T6
好吧,这次的签到题竟然事 T6,让我想起了某届欢乐赛。
思路:找到 ? 所处的那一行,然后看那一行少了哪个字母。
后记
好吧,你说得对,但是这篇题解确实都是在集训营里肝出来的,所以非常生草。