Contest Info

date: 2018.08.27 12:00-17:00

practice link

Solutions

A. Secret of Chocolate Poles

签到题。

B. Parallel Lines

签到题。

C. Medical Checkup

题目大意：\(n\) 个学生依次检查 \(1,2,\cdots\) 个项目，每个学生每个项目检查 \(h_i\) 时间，每个项目同时只能一个人检查，其他人需要等待。给出时间 \(t\)，输出每个学生正在（等待）检查哪个项目。

题解：答案为 \(\displaystyle \frac{t - \sum_{j=1}^ih_j}{\max_{j=1}^ih_j}+2\)。其中 \(t-\sum_{j=1}^ih_j\) 是第 \(i\) 个人检查完项目 \(1\) 之后还剩余的时间，接下来他会被前面最大的 \(h_j\) 阻塞。

D. Making Perimeter of the Convex Hull Shortest

题目大意：二维平面上有 \(n\le10^5\) 个整点，要求去掉两个点，使得剩下的点的凸包周长最短。

题解：先 \(\mathcal{O}(n\log{n})\) 求出 \(n\) 个点的凸包，最优解至少要删一个凸包上的点。取凸包内部一点 \(O\)，将这 \(n\) 个点关于点 \(O\) 极角排序。

如果删除凸包上逆时针序第 \(i\) 个点，那么需要重新计算凸包上极角序在第 \(i-1\) 个点到第 \(i+1\) 个点之间的所有点。这一部分计算最多进行 \(2n\) 次，即可以 \(\mathcal{O}(n)\) 求出删掉一个凸包上的点后新增的点和周长的差值。

删除的第二个点可能是新增的点之一，那么同理我们枚举删去一个新增的点，计算新的凸包也可以在总共 \(\mathcal{O}(n)\) 的时间内完成。其它情况还有：删除的两个点是原凸包上相邻的顶点，删除的两个点是原凸包上不相邻的顶点。

如果删除两个相邻的顶点 \(i\) 和 \(i+1\) ，我们需要重新计算凸包上极角序在第 \(i-1\) 个点到第 \(i+2\) 个点之间的所有点。这一部分的计算总共不超过 \(3n\) 次，可以 \(\mathcal{O}(n)\) 完成。最后如果删除的两个点是原凸包上不相邻的顶点，我们找出删除后周长最优的 \(4\) 个点，这种情况的最优值一定由其中不相邻的两个点产生。

这样这题就做完了，时间复杂度 \(\mathcal{O}(n\log{n})\)。

E. Black or White

题目大意：给定两个长度相同的 \(0/1\) 的初始串 \(s\) 和目标串 \(t\)。你每次可以把长度不超过 \(k\) 的一段变成相同数字，问最少操作次数。

题解：dp。\(f[i]\) 表示前缀 \(i\) 个的最少操作次数，那么有：

\[ f[i] = \begin{cases} f[i-1]&,s[i]=t[i]\\ \displaystyle \min_{j\in[i-k, i)}\left(f[j]+\text{cost}(j+1,i)\right)&,\text{otherwise} \end{cases} \]

其中 \(\text{cost}(j+1,i)\)，我们可以先操作一次，把整个区间变成 \(t[j+1]\)，设 \((j+1,i]\) 中有 \(x\) 段，那么还需要操作 \(\lceil x/2 \rceil\) 次。设 \(b[i]\) 表示前缀 \(i\) 中的段数，于是 \(\displaystyle \text{cost}(j+1,i)=1+\lceil \frac{b[i]-b[j+1]}{2} \rceil\)。转移函数的第二段可以写成：

\[ f[i]=\min_{j\in[i-k,i)} \lfloor \frac{2f[j]-b[j+1]+b[i]+1}{2}\rfloor + 1 \]

用滑窗优化。

F. Pizza Delivery

题目大意：给定一个有重边的边带正权有向图，保证一开始有从 \(1\) 到 \(2\) 的路径。对于每条边，询问把它反向之后，从 \(1\) 到 \(2\) 的最短路如何变化。

题解：求出从 \(1\) 到 \(2\) 的最短路径图，这是一个 DAG。枚举每条边 \((u,v,w)\)，如果这条边是 DAG 上的桥，那么把它反向最短路一定变得更差。否则，我们判断 \(\text{dis}[1][v]+w+\text{dis}[u][2]\) 是否小于 \(\text{dis}[1][2]\)，如果小于，那么这条路径就是最短路，容易证明这条路径是合法的（不经过 \(u\rightarrow v\)，一定经过反向之后的边 \(v\rightarrow u\)）；否则，我们还是能取到原来的最短路，最短路不会变差。

求 DAG 的桥边我们在对应的无向图中从 \(1\) 开始 tarjan 判断是否有 \(\text{low}[v] > \text{dfn}[u]\) 即可。

G. Rendezvous on a Tetrahedron

题目大意：有一个正四面体，两只虫子在上面沿直线爬行，爬过正四面体的边时它与边的夹角不变。给出它们爬行的方向和距离，问它们最后是否在一个面上。

题解：按照套路把正四面体展开，密铺到整个平面上，然后在平面上走一条线段即可。在计算虫子所处的平面时，可以将坐标系按照 \((1,0)\) 和 \((\frac{1}{2},\frac{\sqrt{3}}{2})\) 分解，这样所有的等边三角形会变为等腰直角三角形，处理起来就非常方便了。

H. Homework

题目大意：有两门课程，一共 \(n\) 个作业。每个作业有一个布置时间 \(l_i\)、结束时间 \(r_i\) 以及属于的课程。每一天都要选一门课程，然后在该课程已经布置的作业中，选择还未过期的、过期时间最近的作业来做，如果没有这样的，那就摸了。问最少做多少作业，最多做多少作业。

题解：最多做多少作业，我们直接把所有作业放在一起，每次贪心做 ddl 最近的即可。

最少做多少作业，我们用最小割来求解。我们把天数放两排，第一排每个点向第二排对应点连容量为 \(1\) 的边。源点向第一门课的每个作业连容量为 \(1\) 的边，第二门课的每个作业向汇点连容量为 \(1\) 的边。第一门课每个作业，向第一排的 \(l_i\sim r_i\) 各连容量为 \(1\) 的边；第二排的 \(l_i\sim r_i\) 的每个点向对应的第二门课的作业连容量为 \(1\) 的边。

如此，我们每一天在选择课程以及课程的作业的时候，可以看做割掉对应点到源/汇点的边，那么该作业连向天数的边可以视为被删除（源汇不会通过这些边连通了）。那么一个割集就对应了一种合法的方案，当源汇点不连通的时候，不存在一天没有选择课程。

I. Starting a Scenic Railroad Service

签到题。

J. String Puzzle

题目大意：有一个长度为 \(n(n\le10^{9})\) 的串，有一些位置已经给出，另外还有一些等价关系，以如下格式给出：给出长度为 \(b\) 的两个数列 \(y_{i}\) 和 \(h_{i}\)，其中 \(0\le h_{i}<y_{i}\)，\(2\le y_{1}<y_{2}<\cdots<y_{b}\le n\)。若 \(h_{i}\) 大于 \(0\)，那么该串 \([y_{i},y_{i+1}-1]\) 和 \([h_{i},h_{i}+y_{i+1}-y_{i}-1]\) 的位置对应相等；若 \(h_{i}=0\)，那么 \(y_{i}\) 只是用来给 \(y_{i-1}\) 提供结束位置信息。然后给出 \(q\) 个询问，询问某个位置是否已经确定，如果确定，该位置的字符是什么。

题解：对于 \(\forall p,q\in[h_i,y_{i+1})\)，位置 \(p\) 和 \(q\) 等价的充要条件为 \(y_i-h_i|p-q\)。显然我们要维护一些连通块，但是 \(n\) 太大，不能暴力去做。注意到在题目的输入下，每个位置至多往它左边的一个位置连一条边，也就是说，这些位置构成一个森林，每棵树是一个等价类。这个森林缩 \(2\) 度点之后每棵树的深度只有 \(\mathcal{O}(b)\)。

因此对于某一个位置，我们只要贪心地尽可能往左跳 \(y_i-h_i\) 的倍数步，且不跳出所在区间，一直跳到根。复杂度 \(\mathcal{O}(qb)\)。

K. Counting Cycles

题目大意：\(n(n\leq 10^5)\) 个点，\(m(n-1\leq m\leq n+15)\) 条边的简单无向连通图，问有多少个简单环。

题解：求出一棵生成树，那么非树边只有 \(16\) 条。加上非树边 \(e\) 之后形成的环 \(C_e\) 叫做一个 fundamental cycle，所有的 fundamental cycle 组成了 cycle space 的一组基。这个空间的加法定义为对称差，空间的元素是欧拉生成子图。空间的维度为 \(m-n+c=16\)，最多有 \(2^{16}\) 个点。于是简单环最多也只有 \(2^{16}\) 个。

我们把所有度小于等于 \(2\) 的点都缩掉（以非树边关联点为关键点建虚树），然后在这个最多 \(63\) 个点，\(78\) 条边的图上爆搜即可，可以每次枚举环上的最大点搜索。这样爆搜复杂度不好分析。

建虚树之后，我们也可以直接枚举 fundamental cycle 的子集，把它们做一个对称差（等价于枚举空间中的每个点），然后判断是不是一个环。实现的时候，fundamental cycle 可以通过两个端点到根的链的对称差求得，于是转换为求若干个链的对称差。

Dirt Replay

F: -1 错算法

H: -1 错算法

I: -1 错算法（少读了条件）