2018 CCPC Qinhuangdao Onsite

Problem A

Solved by ultmaster. 02:50 (+1)

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

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

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

Problem B

Solved by zerol. 00:09 (+)

题意：问几点到几点时针分针重合几次。

题解 12 小时中只重合 11 次，其中 [11, 12) 没有重合过。

zerol: 这题我做过，小学奥数题。

Problem C

Solved by ultmaster. 01:00 (+2)

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

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

Problem D

Solved by kblack. 04:51 (+1)

题意：树上每个点一个多项式，求 $u$ 到 $v$ 路径上的多项式之积在 $x$ 点的值。

题解：正解似乎是多项式多点求值，以后补。考场上直接优化了暴力，添加了读入优化和一个常数优化，竟然直接跑过去了。

Problem G

Solved by zerol. 01:58 (+4)

题意：判断一棵树是不是完全 k 叉树，k 尽可能小。

题解：设最大度数是 x，那么 k=x 或 k=x-1，随便挑一个度数为 k 的为根做 dfs 判断所有叶子深度是否一样。

坑点：n=1 答案是 1，n=3 的链答案是 1 而不是 2，只有两层的树某些写法可能要特判。

一开始一通特判，后来觉得特判太多要出事就重写了。然后写完测了一下 n=1 答案是 0，觉得没问题。后来 k 最大最小搞反了。然后就 T 了，优化一下常数也没用。后来加了剪枝（n 必须能表示成 $1+k+k^2+\cdots$）和快速读过了。过完发现 dls&jls 这题已经 -7，突然觉得问题似乎也不大。

zerol: 题没读清楚，罚钱。但是签到题卡常，出题人也有责任。

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+bc+c^n)$。这个转移可以写作一个 $3$ 维的矩阵，初始向量 $(0, A_1, 1)$，第 $3$ 维用来加常数，线段树维护即可。