2018 CCPC Qinhuangdao Onsite

From EOJ Wiki
Revision as of 11:37, 28 September 2018 by Kblack (talk | contribs) (→‎Problem J)
Jump to navigation Jump to search

Replay

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 (+)

题意:$N$ 个数字,中间随机插入 +*,求所以可能的表达式的结果的和。

题解:考虑用状态 $(a, b)$ 表示当前缀的形状表示的是 $a+b$,期中 $a$ 是最后一个加号前的一堆东西的和,$b$ 是最后部分的积。当增加一个数字 $c$ 的时候,有两种转移方式,分别转移为 $(a+b, c)$ 或 $(a, bc)$,发现操作都是线性的,也就是说,用一个状态 $(2a+b, bc+c)$ 代替这两个状态和原式等效,特别的如果是第 $N$ 个,用 $(2a+b_bc+c^n)。这个转移可以写作一个 $3$ 维的矩阵,初始向量 $(0, A_1, 1)$,第 $3$ 维用来加常数,线段树维护即可。