10.2 总结

T1 躲避技能

赛时拿的是暴力的 \(40\) 分，没开 long。

40pts

用 LCA 乱搞，枚举每一个人去哪里，复杂度 \(\mathcal O(m! \log n)\) 。

AC

给每一个躲避点打上 \(-1\) 标记，当前点打上 \(1\) 标记，每一次向上转移边长乘子树标记和即可。

T2 奶茶兑换券

暴力不会。

T3 帮助

40 pts

枚举每两个同学，看看能不能互帮互助，复杂度 \(\mathcal O(n^2)\) 。

T4 神奇的变换

Subtask 1

暴力即可

Subtask 2

不会。

Subtack 3

先算出每一个 \(a_i\) 的每一个约数的个数，然后询问时用前缀和算出来即可，复杂度 \(\mathcal O(1000(n+q))\)。

Subtask 4

用前缀积然后计算即可。