2018 CCPC Qinhuangdao Onsite

Problem A

Solved by ultmaster. 02:50 (+1)

题意：给一个无向图，每条边加单位容量有一个代价，求在给定代价内能够达到的最小割的最大值。

题解：裸的最小费用最大流。如果当次 Bellman Ford 跑出来的流量已经不能全部买到了，那就切一部分买到的。

抄模板漏了一个 &，WA +1。

Problem B

Solved by zerol. 00:09 (+)

Problem C

Solved by ultmaster. 01:00 (+2)

题意：答案有 36 种可能，求字典序最小的答案是输入串的子序列。

题解：直接枚举即可。因为忘记找到了以后就 break OLE 两发，差点自闭（感谢 kblack）。

Problem D

Solved by kblack. 04:51 (+1)

Problem G

Solved by zerol. 01:58 (+4)

Problem I

Solved by ultmaster. 02:03 (+)

题意：已知有一些值（糖果），另外一些值（包）是其中一些值的和（每个值至多只能被用一次）。现在把所有值都打乱了给你，求可能的方案数。

题解：预处理每个包可以装哪些子集。因为数据范围很小，可以枚举哪些是包。然后对于这些包进行 DFS，每个包暴力枚举可能的东西。复杂度是看起来是 $\mathcal{O} (2^{2n})$，但实际上不知道是不是——就算是也常数很小。

Problem J

Solved by kblack. 00:51 (+)