Contest Info

date: 2018.08.05 12:00-17:00

practice link

Solutions

A. Decoding Baby Boos

签到题

B. And Or

签到题

C. A game for kids

题目大意：有一棵 \(n\le10000\) 个节点的树，节点 \(i\) 处放着 \([L_i,R_i](1\le L_i \le R_i \le 50)\) 内的所有整数。选择一条路径，然后从路径上每一个节点恰好取出一个数，这个选择方案的价值就是这些数的 gcd 。

统计价值为 \(g\in[1,50]\) 的方案数量，取模。

题解：容斥，先求 gcd 是 \(g\) 倍数的方案数，做 \(50\) 次树 dp 即可。

算答案的时候倒着给每个因子减去当前的答案即可。

复杂度 \(\mathcal{O}(50n)\)。

D. Flood in Gridland

题目大意：\(n\times m(1\leq n, m\leq 75)\) 的矩阵每个位置要么是一个数字 \(h_{ij}\)，要么为空。一次操作可以把某一行全 \(+1\)，或者把某一列全 \(-1\)。要求若干次操作之后，每个数字都在区间 \([L, U]\) 之间，且数字之和最大。输出一种方案。

题解：设 \(\text{sizeRow}(i)\) 表示第 \(i\) 行非空的数字个数， \(\text{sizeCol}(j)\) 表示第 \(j\) 列非空的数字个数。设我们对第 \(i\) 行操作了 \(P_i\) 次，对第 \(j\) 列操作了 \(Q_j\) 次。我们可以将问题改写为标准型线性规划形式：

\[ \begin{aligned} \text{Maximize:} \\ &\sum_{i=1}^nP_i\cdot \text{sizeRow}(i) - \sum_{j=1}^mQ_j\cdot \text{sizeCol}(j)\\ \text{Subject to:}\\ &P_i-Q_j\leq U - h_{ij}\\ &-P_i+Q_j\leq h_{ij}-L \end{aligned} \]

约束 \(Ax\leq B\) 中，\(A\) 满足它的每一行恰有一个 \(+1\)，和一个 \(-1\)，且相邻两行的 \(+1,-1\) 正好相反。我们继续写出上述线性规划的对偶形式：

\[ \begin{aligned} \text{Minimize:}\\ &B^{T}y\\ \text{Subject to:}\\ &A^{T}y\geq \left( \begin{matrix} \text{sizeRow}(1)\\ \vdots\\ \text{sizeRow}(n)\\ -\text{sizeCol}(1)\\ \vdots\\ -\text{sizeCol}(m) \end{matrix} \right) \end{aligned} \]

现在 \(A^{T}\) 每列恰有一个 \(+1\) 和一个 \(-1\)。我们将所有的约束相加，发现 \(0\geq 0\)，也即所有的 \(\geq\) 都要取到 \(=\)。现在考虑 \(A^{T}\) 中每一行是一个点，每一列是一条有向边，从 \(-1\) 指向 \(+1\)。那么 \(y_i\) 可以视作是一条边上的流量，\(B\) 向量是边上费用。我们最优化的是一个费用流。

只考虑这 \(n+m\) 个点之间的流量关系，流量还未平衡，我们需要加上源汇点。考虑每个约束是 \(\sum\text{in flow}-\sum\text{out flow}=\text{constant}\)，当 \(\text{constant}>0\) 的时候（点 \(1\sim n\)），入流小于出流，说明它向汇点连边；当 \(\text{constant}<0\) 的时候（点 \(n+1\sim n+m\)），入流大于出流，说明源点向它连边。

如此我们求出了最优解的数值，也就是最优目标值。接下来我们构造解，在跑完费用流之后的图中，如果某条边流量非空（\(y_i\neq 0\)），那么对应的原约束的 \(\leq\) 应该取到 \(=\)（增加 \(x\leq P_i-Q_j\) 的约束）（互补松弛性），我们建立差分约束系统，跑一遍最短路得到一个最优解，最后减去 \(\text{min}\) 即可保证解非负。

无解当且仅当费用流有负环。

E. Refraction

题目大意：有一个长方形的碗中有一个物体，一个人在碗的右上方看它。最初视线被碗挡住了，无法看到。现在向其中倒入折射率为 \(\mu\) 的液体，问液体多高时恰能看到该物体。

题解：简单计算几何，求一些直线的交即可。

F. Reverse Polish Notation

题目大意：给出一个只由变量 \(a\) 和操作符 \(+\) 组成的表达式，问你最少操作几步使得其为一个后缀表达式。操作可以在任意位置添加 \(a\) 或者添加 \(+\)，或者交换相邻两个字符。

题解：计算前缀和，\(a\) 视作 \(+1\)， \(+\) 视作 \(-1\)，那么合法的后缀表达式满足条件：每一个前缀和都 \(\geq 1\)，且整个的和恰好为 \(1\)。我们先检查整个的和，如果不等于 \(1\)，那么我们可以在头部补充若干个 \(a\)，或者在末尾补充若干个 \(+\)，这样一定不会更差。

接着我们考虑，我们可以花费 \(2\) 的代价，在头尾各增加一个 \(a\) 和 \(+\)，作用是每一个前缀和都增加 \(1\)。可以证明 \(-1\) 以下的前缀和，使用这种方法是不会更差的。所以我们先把所有的前缀和抬到 \(-1\) 及以上，然后考虑 \(-1\) 的前缀和，它后一个一定是 \(0\)，我们可以交换这两个，使得 \((-1,0)\) 变成 \((1,0)\)；再考虑 \(0\) 的前缀和，它后一个一定是 \(1\)，交换一次使得 \((0,1)\) 变成 \((2,1)\)。我们在交换操作，和前后各增加一个符号的操作中取 \(\text{min}\) 即可。

注意还可能既交换，也前后增加符号。例如 \(+aa+a+a\)，前缀和为 \(-1,0,1,0,1,0,1\)。处理这种情况，我们只需要在上述基础上再把所有前缀和抬到 \(0\)，然后同样判断即可。

G. Just Some Permutations

题目大意：求长度为 \(n\le2000\) 的排列，至少有 \(k\) 个数 \(i\) 满足它排在 \((i-1)\text{ mod }{n},i,(i+1)\text{ mod }{n}\) 这三个位置之一的方案数，取模\(10^9+7\)。

题解：类似于错排，如果能求出 \(r_k\) 表示填入 \(k\) 个错误的位置的方案数，就可以容斥求出恰有 \(k\) 个数错排的方案数，求后缀和即可。

考虑用 dp 来求解 \(r_k\) ，记录 \((n,1)\) 和 \((i,i+1)\) 四个位置的状态即可转移，时间复杂度 \(\mathcal{O}(64\cdot n^2)\)，对于多组数据不需要重算 dp ，把 \(n\) 这里的合法方案统计出来即可。

加上容斥，时间复杂度为 \(\mathcal{O}(64\cdot n^2 + T\cdot n^2)\)。

H. Load Balancing

题目大意：给出 \(n\) 个人的分数 \(c_i\in[0, 160]\)，让你给出字典序最小的 \(0\leq a<b<c<160\)，分数落在 \([0,a],[a+1,b],[b+1,c],[c+1,160]\) 的个数设为 \(t_0,t_1,t_2,t_3\) ，要求使得 \(\sum |t_i-\frac{n}{4}|\) 最小。

题解：设 \(\text{dp}[i][j]\) 表示处理到第 \(i(1\leq i\leq 3)\) 个数字，它取 \(j\) 的最小代价。

I. Volume of Revolution

题目大意：求一些旋转体的体积。

题解：积分即可。注意一个多项式的平方不是把它每一项的指数乘以 \(2\)。

J. Maximum Score

题目大意：给出 \(n\le10^5\) 种不同的数字，第 \(i\) 种数字为 \(f_i\)，数量为 \(p_i\) ，记 \(\sum p_i = m\)。定义这 \(m\) 个数的多重集合排列 \(P\) 的价值为以每一个数作为山峰的、向两边单调不增的最长子序列长度之和。求最大价值，以及有多少不同的排列可以取到最大价值。

最大价值不取模，不超过 unsigned long long ，数量对 \(10^9+7\) 取模。

题解：最大价值显然是每个数都可以得到不大于它的所有数的贡献时取到最大。这样的排列可以从最大的数开始放，次大的数不可以放入更大的数内部。

排序一下扫两遍即可，时间复杂度 \(\mathcal{O}(n\log{n})\)。

Dirt Replay

J: -1 D 改了 ull 之后没有改输出 %llu

F: -2 case 没有分析清楚；复制粘贴之后忘记删掉一句话