The 2025 ICPC Asia East Continent Online Contest (II)

比赛链接

Review

这场非常有参与感哈哈，因为我签到题 C 贪心写了两小时，中间下机若干次让队友过题，写完已经完全不知道队友进度是啥了，后续就当小黄鸭被带飞了哈哈。

Solution

C. Jiaxun!

那我确实需要 jiaxun

额额贪心不会啊，但是会网络流。

先二分，把选择唯一的先填好，变成左四右三的最大流问题，最大流等于最小割，所以只需要枚举割哪些边，判断是否连通再判最小值是否为要求流量。

E. Zero

比较困难的限制是相邻，而异或和是可以靠最后一个位置力挽狂澜的！

于是朴素计算就是 \(2^m\times (2^m-1)^{n-2}\)，第一个随便放，后面只要和前一个不同就行。那么重复就只可能是最后一个，就变成规模 \(-2\) 的问题。

于是 \(f_n=2^m\times (2^m-1)^{n-2}-(2^m-1)f_{n-2}\)，做一些数列变化求一下通项。