CCPC-Wannafly Winter Camp Day7

From Ingenuity Wiki

Problem A

unsolved. (-4)

Problem C

solved by ybmj. (+2)

二分答案 $x$,把小于 $x$ 的放在二分图的左侧,剩下的放在右侧。Dinic算法判断是否存在完美匹配。

复杂度:$O(n \sqrt{m} \log n)$

Comment: 实际上不需要二分,直接从小到大枚举,每次把右边的点拆掉放在左边继续增广就好。

Problem E

upsolved by CSL. (-8)

需要支持区间赋矩阵,区间求矩阵乘积。

直接上线段树打标记,会在 pushdown 的时候用矩阵快速幂计算区间乘积,复杂度 $O(3 ^ 3 m \log^2 n)$ 会超时。

需要把线段树强制写成 2 的幂次,这样线段树的区间长度就只有 $O(\log n)$种。每个矩阵直接预处理幂次,下放标记的时候就不需要重新计算了。

复杂度: $O(3 ^ 3 m \log n)$