1102总结

T1

原题就是让你化简式子:
\[
\begin{aligned}
\sum _ { j = l } ^ { r } \left( \begin{array} { c } { j } \\ { k + j – l } \end{array} \right) &= \sum _ { j = l } ^ { r } \left( \begin{array} { c } { j } \\ { l – k } \end{array} \right)
\\
&= \left( \begin{array} { c } { r + 1 } \\ { l – k + 1 } \end{array} \right) – \left( \begin{array} { c } { l } \\ { l – k + 1 } \end{array} \right)
\end{aligned}
\]

T2

判断是否能加入一条边时,如果这条边的两端已经联通,我们需要知道这个联通块是否有环。
如果不连通,那么可以加入这条边,而且通过两端的联通块是否有环可以得到新的联通块是
否有环。
于是我们用并查集维护连通性,额外维护联通块里是否有环即可
\( O ( ( n + m ) \log n )\)

T3

哈希二分的方法其实就是不断的询问字符串的某一部分的哈希值。
我们可以用线段树来维护哈希值,那么每次修改一个位置只需要把父亲的线段树改一个位置。
利用主席树来维护,比较的时候也从主席树的两个根开始递归比较,可以做到\( O \left( n \log ^ { 2 } n \right) \)

0