GYM102471K All Pair Maximum Flow 做题记录

给定一个 nn 个点 mm 条边的无向图,每条边有流量 wiw_i,保证其是一个逆时针从 11nn 编号的正 nn 边形,且边只会在顶点处相交,求 nn 个点两两间的最大流之和,对 998244353998244353 取模。

3n2×1053\le n\le 2\times 10^5nm4×105n\le m\le 4\times 10^50wi1090\le w_i\le 10^9

阅读全文 »

CF725F Family Photos 做题记录

nn 个大小为 22 的照片堆,每张照片可以用一个二元组 (a,b)(a,b) 描述,每个堆可以用一个四元组 (a1,b1,a2,b2)(a1,b1,a2,b2) 描述,表示堆顶的照片为 (a1,b1)(a1,b1),堆底的照片为 (a2,b2)(a2,b2)

Alice 和 Bob 要轮流取照片,Alice 先手,轮到某个人取时他可以选择跳过,若一轮中两人均选择跳过则游戏结束。

对于一张照片 (a,b)(a,b),Alice 取它能获得 aa 分,Bob 能获得 bb 分,位于堆底的照片要等到相应堆顶的照片被取掉才能取。

记 Alice 的得分和为 tata,Bob 的为 tbtb。Alice 的目标是最大化 tatbta-tb,Bob 则要最大化 tbtatb-ta

两人绝顶聪明,求出游戏结束时的 tatbta-tb

1n1051\le n\le 10^50a1,b1,a2,b21090\le a1,b1,a2,b2\le 10^9

阅读全文 »