Contest Info

date: 2018.08.18 12:00-17:00

practice link

Solutions

A. Advertising Strategy

题目大意：有 \(n\le10^{18}\) 个人看电影，主办方准备了 \(2\le k\le10^5\) 份礼物。第 \(i\) 天，设前 \(i-1\) 天已经看过电影的人有 \(b_i\) 个，主办方可以花费 \(c_i\) 份礼物，让 \(c_i\) 个人提前看电影，这样一共就有 \(a_i = b_i + c_i\) 的人看了电影。之后，第\(i\)天新增的看电影的人数是 \(\min(a_i, \lfloor\frac{n-a_i}{2}\rfloor)\)。问至少多少天可以让所有人都看过电影。

题解：显然最优策略是在第一天给一部分礼物让第一批人看电影，之后在最后一天补一部分礼物让剩下的人看电影。枚举第一天给的礼物数量，答案不会超过\(\mathcal{O}(\log{n})\)，暴力计算取最优即可。时间复杂度 \(\mathcal{O}(k\log{n})\) 。

B. Byteland Trip

题目大意：有一个长度为 \(n\) 的序列，每个位置由 < 和 > 组成。如果一个位置是 <，那么可以往左跳，否则可以往右跳。对于每个 \(1\le i\le n\)，求从任意点出发，回到 \(i\)，且经过每个点各一次的方案数。

题解：对于每条合法的路径，我们可以将它分成 \(i\) 左边的若干段和 \(i\) 右边的若干段。设 \(f[i][j]\) 表示点 \(i\)（含）左边的点，划分为 \(j\) 段，且每段最后一步向右的方案数（各段之间有序）；\(g[i][j]\) 表示点 \(i\)（含）右边的点，划分为 \(j\) 段，且每段最后一步向左的方案数（各段之间有序）。那么答案很容易用 \(f[i-1]\) 和 \(g[i+1]\) 求出。以 \(f\) 的转移为例：若 \(s[i]\) 为 <，那么 \(i\) 可以作为之前某一段的起点，或者用来把之前的两段合起来；若 \(s[i]\) 为 >，那么 \(i\) 可以作为新的一段，或者作为之前某一段的终点。

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

C. Carpet

题目大意：\(n\) 个点的树，求一种方案，把每个点放入 \(10^6\times 20\) 的棋盘中，使得边不相交。

题解：轻重链剖分，重链放在同一列，轻链依次放在下一列。注意先访问轻儿子。

D. Decoding of Varints

签到题。

E. Empire History

题目大意：有两个无向连通图 \(G_1\) 和 \(G_2\)（每个图至少有两个点），从 \(G_1\) 中选择 \(l\) 个点，\(G_2\) 中选择 \(k\) 个点，然后把它们通过 \(l\times k\) 条边两两连接，得到一个新的图 \(G\)。现在给你图 \(G\)，让你输出一对可能的 \(G_1,G_2\)，以及对应的 \(l,k\) 和这些点的编号。

题解：昂神说是个假题，于是假装不存在。

F. Fake or Leak?

题目大意：给出一个 ACM-ICPC 的榜单，包括 \(m\le1000\) 支队伍，\(1\le n\le26\) 道题目，以及每个队伍封榜之前每道题的通过状态，总提交次数，最后提交时间。给出 \(k\le m\) 行榜单，判断它们是否可能是终榜上的连续一部分。排名首先比较题数，然后是总罚时，接着最后 ac 提交时间，最后比较队名字典序。

题解：先将 \(k\) 个新的纪录排序比较相对顺序是否正确。对于剩下的 \(m-k\) 个队伍，要判断他们是否可以出现在这 \(k\) 个人之前或者之后。每支队伍，判断一下在最好情况（封榜一瞬间 ak ）和最坏情况（封榜之后不提交）是否可以满足即可。

G. God of winds

题目大意：给了你一个 \(n\times m\) 的循环网格（最上边界等价最下边界，最左等价最右）。每个边有一个权值，在每个网格处可以放置若干个顺时针/逆时针的龙卷风，不同方向的龙卷风对边界的权值有不同影响，影响可以叠加。问你是否存在一种方案使得恰好是给出的权值。

题解：我们假设每个网格的龙卷风是 \(x_{ij}\)，用正负来表示方向。那么每个边可以写成 \(x_{ij}-x_{kt}=w\) 的形式，我们用差分约束系统求解。由于只判断是否存在方案，我们可以直接 dfs 判断是否有两条长度不同路径到达同一个点即可。

H. Hilarious Cooking

题目大意：给你一个 \(T\)，问你是否能构造出一个长度恰为 \(n\) 的非负整数数列 \(\{t_{n}\}\)，使得 \(\sum_{i=1}^{n}t_{i}=T\)，\(|t_{i}-t_{i+1}|\le1\)，并且该数列的一些位置已经给定。

题解：考虑所有的填数方案，显然所有方案可能得到的数列和一定是一个区间，我们只需要算出这个区间，然后判断 \(T\) 是否在里面即可。最大值和最小值分别是在每个区间中填入形如“山峰”和“山谷”的情况下取得的。实现时有各种细节，需要注意。

I. Infinite Gift

题目大意：给你 \(\mathbb{Z}^{k}\) 中的 \(n\) 个向量 \(v_{1},\cdots,v_{n}\)，对于每个 \(v_{i}\) 和 \(w\in\mathbb{Z}^{k}\)，从 \(w\) 向 \(w+v_{i}\) 连一条无向边，保证整个空间连通。问这个图是否是一个二分图。

题解：因为整个空间连通，所以在这 \(n\) 个向量中一定能找到整个空间的一组基。显然这个图是二分图等价于全部 \(n\) 个向量在这组基下的各维坐标之和是一个奇数，使用 bitset 加速高消即可。时间复杂度 \(\displaystyle \mathcal{O}(\frac{n^{2}m}{64})\)。

J. Judging the Trick

题目大意：一个 \(w\times h\) 的矩形中有 \(n\le10^{5}\) 个三角形（都是整点），且它们的总面积之和严格小于 \(wh\)。找出一个不在任何三角形内的点。

解法一：二分横坐标，每次判断中线上是否有在三角形外的点，如果没有，那么它的左右两侧至少有一块满足所有三角形在它内部的总面积小于该矩形的总面积，到该矩形中继续查找即可。时间复杂度 \(\mathcal{O}(n\log n\log \frac{1}{eps})\)。

解法二：扫描线。三角形的总面积之和严格小于 \(wh\) 等价于至少有一条与 \(y\) 轴平行的直线与所有三角形相交的线段长度之和小于 \(h\)，那么这条直线上必然有一点满足要求。容易发现，对于每个三角形，与 \(y\) 轴平行的直线和它相交的线段长度与这条直线横坐标的关系可以用一个或两个分段的一次函数来表示，因此我们可以用扫描线来维护这些一次函数的和，为了方便，每次取两条扫描线的中线判断它是否满足要求。

观摩昂神的代码后发现，取总相交长度最短的中线来查找可以获得更好的精度。时间复杂度 \(\mathcal{O}(n\log n)\)。

Dirt Replay

C: -1 细节想错了，应该先访问轻儿子

F: -1 W 跟 D 说了实现细节，然而 D 没好好听写错了一次

H: -3 写错了；算 max 的时候 r 算重了；W 发现了之后，Z 把 min 也顺便改了，然而 min 不需要改

I: -4 前两次 Z 猜了错误结论；W 没想到基一定有 m 个； 没有累计 cnt