Contest Info

date: 2018.08.12 12:00-17:00

practice link

Solutions

A. Arranging Hat

题目大意：给你 \(n\) 个 \(m\) 位的十进制整数，允许有前导零，问最少改变多少个位可以使这 \(n\) 个整数单调不减。

题解：设 \(\text{dp}[i][j][k][u]\) 表示使得第 \(j\) 个数到第 \(k\) 个数的低 \(i\) 位有序，且 \(k\) 的第 \(i\) 位为 \(u\) 的最小代价，那么转移方程为： \[ \text{dp}[i][j][k][u]=\min_{j-1\le k'<k,0\le u'<u}\left(\text{dp}[i][j][k'][u']+\min_{t=0}^9\text{dp}[i-1][k'+1][k][t]+\sum_{x=k'+1}^{k}\left[s[i][x]\neq u\right]\right) \] 使用前缀和优化可以做到 \(\mathcal{O}(n)\) 转移。时间复杂度 \(\mathcal{O}(10mn^{3})\)。

B. British Menu

题目大意：给出一个 \(n\le10^5\) 个点和 \(m\le10^6\) 条边的有向图，满足图中所有的 scc 大小都不超过 \(5\)，求最长的简单路径的点数。

题解：因为 scc 大小很小，所以可以暴力求出 scc 内部任意两个点作为起点和终点的最长路径长度，之后可以在缩点后的 DAG 上进行 dp ，需要枚举每个 scc 进入和离开的节点进行转移。

时间复杂度 \(\mathcal{O}((n+m)\times5\times2^5)\)。

C. Careful Ascent

签到题。

D. Driving in Optimistan

题目大意：给出一棵树的 \(n(n\leq 500)\) 个叶子间两两的距离（距离最大值 \(10^6\) ），原树所有的边长为 \(1\)。问原树中所有点对的距离的平均值。

题解：如果能建出原树，那么我们计算每条边两端的 size 乘积，便是它的贡献。但是原树点可能非常多，所以我们只考虑增加 \(n-1\) 个点。

我们把 \(1\) 提起来作为根，然后计算出其余所有点对的 lca 到 \(1\) 的距离，然后每次新建距离最大的 lca。点对 \((u,v)\) 的 lca 到 \(1\) 的距离为 \(\displaystyle \frac{\text{dis}[1][u]+\text{dis}[1][v]-\text{dis}[u][v]}{2}\)，同时我们也可以算出 \(u,v\) 分别到 lca 的距离。

树建好之后，我们先 dfs 算出 size，这里的 size 是不包括根的点数，那么我们设 \(m=\text{size}[1]+1\)，对于 \(u\) 到 \(v\) 的一条长度为 \(w\) 的边，它的贡献为：

\[ \sum_{i=1}^w(\text{size}[v]+i)\left((m-\text{size}[v]-w)+w-i\right) \]

E. Exam Redistribution

签到题

F. Free Weights

题目大意：有两行数字，每行有 \(n\le10^6\) 个数，这 \(2n\) 个数中每种数字恰好有两个，值域 \([0,10^9]\) 。最小化需要移动的最大数字，使得每对相同的数字都相邻。移动后每行的数字数量不同也合法。

题解：二分答案，然后将所有不超过答案的数字都删去判断剩下的数字是否满足条件即可。时间复杂度 \(\mathcal{O}(n\log \text{ans})\)。

G. Gotta Nudge ’Em All

题目大意：给你一个 pokemon go 的游戏系统，已知若干条宝可梦的进化链。有一个糖果系统，捕捉一只宝可梦可得 \(3\) 颗糖果，放生一只宝可梦可得 \(1\) 颗糖果，糖果绑定进化链。进化宝可梦花费糖果，且进化高级的宝可梦的花费不低于低级宝可梦。捕捉一只宝可梦可得 \(100\) 经验，进化一只宝可梦可得 \(500\) 经验。有一个道具幸运蛋，在 \(1800s\) 内经验翻倍。全程该道具只有一个，且规定只在它生效期间内进化宝可梦。现在给出一个捕捉宝可梦的时间序列，求获得经验的最大值。

题解：显然我们可以在幸运蛋失效的最后一刻尽可能地进化宝可梦，所以我们可以按照时间用滑动窗口来处理。注意到每条进化链是独立的，每次我们只需要更新新捕捉到的宝可梦所在的进化链的答案即可。那么现在的问题就变成了，已知某条进化链捉到了哪些宝可梦，如何安排进化和放生使得经验最多。

考虑一条进化链，显然每次进化最低级的宝可梦，而且每只宝可梦进化完后将它放生。设捉到了 \(x\) 只宝可梦，那么进化最后一只宝可梦之前，我们总共能获取 \(4x-1\) 颗糖果。下面我们证明，如果一个进化方案需要的糖果数量小于等于 \(4x-1\)，那么这个方案一定能够完成。设 \(c_{i}\) 为第 \(i\) 只宝可梦进化所需的代价，且假设我们已经将所有不需要进化的宝可梦事先放生，那么我们有 \(c_{i}\ge 1\)。进化第 \(i\) 只宝可梦时，糖果的数量为 \(3x+i-1\)，而我们有 \(\sum_{j=1}^{i}c_{j}\le4x-1-\sum_{j=i+1}^{x}c_{j}\le4x-1-(x-i)=3x+i-1\)。因此不论我们怎么安排进化的顺序，每次进化时糖果的数量都是足够的。有了这个结论后，我们可以二分将宝可梦进化到哪个阶段，并用树状数组维护一些数量即可。

时间复杂度 \(\mathcal{O}(n\log^{2}n)\)。

H. Hamiltonian Hypercube

题目大意：求两个 Gray Code 的距离。

题解：考虑 Gray Code 的镜射构造过程，最高位为 \(1\) 的时候，用 \(2^n-1\) 减掉递归的答案。

I. Iron and Coal

题目大意：\(n\) 个点的有向图，有的点有煤矿，有的点有铁矿。问连接 \(1\) 号点和至少一个煤矿一个铁矿的最少点数。

题解：把所有的煤矿连向一个点，铁矿连向另一个点，即求三个点的 Steiner Tree。bfs 三次求出最短路，然后枚举一个点拼起来。

J. Jupiter Orbiter

题目大意：\(q\) 个队列，每个队列有一个最大的容量 \(c_i\)。 \(s\) 个传感器，每个传感器绑定了一个队列。 \(n\) 次事件，第 \(i\) 次事件为每个传感器往绑定的队列生成 \(a_{ij}\) 的数据。数据都生成结束之后，\(q\) 个队列一共可以下载 \(d_i\) 的数据。问是否存在一种方案，可以不遗失所有的数据。

题解：最大流。我们把每个队列在每天建一个点，然后把这个点拆成两个点，共 \(2qn\) 个点。入点向出点连 \(c_i\) 的容量，同一个队列，前一天的出点向后一天的入点连 \(\infty\) 的容量。每个事件建一个点，向汇点连 \(d_i\) 的容量。每个队列每天的出点连事件点 \(\infty\) 的容量。源点连每个队列每天的入点该天的总数据量。

最后判断最大流是否等于生成的总数据量即可。

K. Kiwi Trees

题目大意：给你一个简单多边形，问能否在里面放两个半径相等的圆，使得它们不相交。

题解：脑补一下可以发现这两个圆一定被放在两个角里面。对于每个角，我们将它的两条边向多边形内部移动 \(r\) 的距离，新的交点就是圆的圆心，这里要注意判一下这样放圆是否真的在多边形内。之后 \(\mathcal{O}(n^{2})\) 地枚举两个圆是否相交即可。

Dirt Replay

F: -1 D 瞎想了一个不是最优的做法

C: -1 Z 输出速度的时候取了 abs

B: -3 dp 的时候没有加以 scc 为结尾的贡献；dfs 只从 1 开始