Contest Info

date: 2018.08.20 13:00-18:00

practice link

Solutions

A. Abstract Picture

题目大意：有一个粉刷匠在 \(n\times n\) 的墙壁上刷小写字母，每次选一个字母然后刷一行或者一列。现在给出最后的结果，输出一种可能的刷墙方案，结果中可能有通配符 “?”。

题解：最后一次操作一定是一整行或者一整列，我们倒着撤销操作即可。

B. Battle Mage

题目大意：在一个 \(n\le700\)个 顶点的凸多边形内部，有 \(c\le2000\) 个圆形空洞，现在要用顶点 \(v\) 将图形悬挂起来，问稳定后凸多边形各个顶点的坐标。

题解：稳定之后，图形的重心应该在悬挂点的正下方，求出重心后，算出重心以悬挂点为中心旋转到目标位置需要的角度，将所有顶点以悬挂点为中心旋转同样的角度即可。

求重心可以先不考虑圆，将凸多边形三角剖分，求出每个三角形的重心乘上三角形面积的矢量和，以及总面积。然后求出圆的并集的重心和面积，将三角形的重心乘上三角形面积的矢量和减去圆并重心乘上圆并面积的矢量和，最后除以凸多边形面积减去圆并面积的值即求出了总的重心。

抄一下圆并的板，时间复杂度\(O(n+c^2\log{c})\)。

C. Constant Ratio

签到题。

D. dir -C

题目大意：给出一个长度为 \(n\le10^5\) 的数列 \(1\le a_i\le10^9\) ，和一个正整数 \(1\le w\le10^9\)。求最小的正整数 \(l\) ，使得数列按大小 \(l\) 分块（只有最后一块大小可以不足 \(l\) ）后，每块的最大值加 \(1\) 的和不大于 \(w-1\)。

题解：sparse-table 预处理后，枚举 \(l\) 暴力计算即可，\(\mathcal{O}(n\log{n})\)。

E. Extreme Permutations

题目大意：定义一个 \(1\sim n\)（\(n\) 为奇数）的排列是好的，当且仅当对于任意的 \(1\le i<n\)，满足 \(|p_{i}-p_{i+1}|\ge\min(p_{i},p_{i+1})\)。现在有一些位置已经给定，求好的排列的数量。

题解：观察样例容易发现，在 \([\frac{n+1}{2},n]\) 之间的整数必须排在奇数位置，其余的数必须排在偶数位置，因为这些大的整数必须互不相邻。

考虑从小到大填入 \([\frac{n+1}{2},n]\) 之间的整数。设 \(\text{dp}[i][S][j]\) 表示当前填到 \(i\)，\(S\) 存已经填过的奇数位置，\([1,\frac{n-1}{2}]\) 间的整数已经用掉 \(j\) 个的方案数。转移时枚举将 \(i+1\) 填入 \(1,3,\cdots,n\) 中的某个位置，设为 \(k\)，如果 \(k-2\) 没有填过，那么我们就向 \(k-1\) 中填入某个 \([1,\frac{n-1}{2}]\) 中的数，填法恰有 \(\lfloor\frac{i}{2}\rfloor-j\) 种。这是因为我们在从小到大填，因此之前用过的 \(j\) 个数必然在 \([1,\lfloor\frac{i}{2}\rfloor]\) 的范围内。同样，因为现在 \(k-2\) 还没填过，它一定比 \(i+1\) 大，不论如何填 \(k-1\)，都不会与 \(k-2\) 冲突。对于 \(k+2\) 同理。

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

coldwater’s comment:

\([\frac{n+1}{2},n]\) 之间的整数没有比它大一倍的数，那么它必须要比两边的数都大一倍，故只能在奇数位置。最后的数列是大的夹小的，每个较小数的方案，是在放两个大数的较小者的时候被计算。

F. Find the Length

题目大意：给出一个 \(n\le300\) 个点的无向图，边带权，对于每一个顶点 \(i\) ，求包含 \(i\) 的最小简单环。

题解：简单环可以由 \(i\) 与 \(j\) 的直接连边，与不包含这条边的 \(i\) 到 \(j\) 的最短路组成。先用 floyd 算法求出两两之间的最短路长度，对于点 \(i\)，以 \(i\) 为根 dfs 建出一个最短路径树。

树上一个不与 \(i\) 直接相连的点 \(j\) ，如果在原图中存在 \(i\) 到 \(j\) 的直接连边，用最短路与这条边的和更新答案。再枚举两个点 \(x\) 和 \(y\) 满足 \(\text{lca}(x,y)=i\) ，且原图中存在 \(x\) 到 \(y\) 的直接连边，用这两个点的最短路与这条边的和更新答案。时间复杂度 \(\mathcal{O}(n^3)\)。

coldwater’s another solution:

cdq 分治套 floyd。每次把前一半的点作为中介点做 floyd，然后递归后一半。同样对后一半做一次，递归前一半。到最底层的时候，不含点 \(l\) 的两两最短路已经求得，枚举 \(i, j\)，\(w[i][l] + w[j][l] + \text{dis}[i][j]\) 即为一个环。复杂度 \(\mathcal{O}(n^3\log n)\)，不会慢太多。

G. Game “Minesweeper”

题目大意：交互题。扫雷，要求你把没有雷的位置点开，有雷的位置打上标记。

题解：枚举每个没点开的位置，尝试放一颗雷，然后去 dfs 判断是否矛盾。如果矛盾，那么点开。如此直到没有可以点开的位置。

H. Hierarchy

stl 练习题。

I. Interactive Casino

题目大意：一个人赌博，开始有 \(160\) 元钱。每次把至少 \(1\) 元至多手里所有钱下注，第 \(i\) 局有一个数字 \(x_i\)，若这个数字的各二进制位之和为奇数，赢；否则输。若赢，可以获得下注的双倍的钱，否则损失他的赌注。他的目标是手里有 \(200\) 元钱。另外还知道，赌场使用的随机数发生器是 \(487237\times x_{i-1}+1011807\mod{2^{20}}\)，但是每次 \(x_{1}\) 的值未知。

题解：枚举 \([0,2^{20})\) 内的每个数作为 \(x_1\)，发现接下来 \(64\) 次的胜负状态可以唯一确定 \(x_1\)。我们倍增打出这个表，然后前 \(64\) 次下注解出 \(x_1\)，之后每次按照最优策略行动。

J. Judgement

题目大意：一个比赛有 \(n\) 个裁判，每个裁判有一个权值 \(a_{i}\)，并且给出通过或不通过。有一个阈值 \(p\)，若所有给出通过的裁判的权值和大于等于 \(p\)，那么整体就算通过。给出第二组裁判，权值为 \(b_{i}\)，阈值为 \(q\)，判断所有 \(2^{n}\) 种判断下这两组给出的结果是否完全相同，如果不相同，给出一种不相同的方案。

题解：背包 dp，设 \(\text{dp}[i][j]\) 表示前 \(i\) 个裁判中，第一组给出通过的裁判的权值和为 \(j\) 的情况下，第二组裁判的权值和的最小值。那么对于 \(\forall1\le i\le n,j\ge p\)，如果有 \(\text{dp}[i][j]<q\)，那么我们就找到了一组不相同的方案，否则容易证明两种方案一定相同。注意要反过来再做一次。

为了压缩空间，实现的时候不需要 \(i\) 这一维，记录方案时只需要记录这一位裁判是否给出通过，可以用 bitset 优化。时间复杂度 \(\mathcal{O}(np)\)，空间复杂度 \(\mathcal{O}(n+\frac{np}{64})\)。

K. Krotek

题目大意：平面上有 \(n\) 条线段，线段只在端点相交，端点是整点，且保证没有三点共线。现在让你把一些端点连起来，使得所有点连通，且最小化新加边长度，边不能相交。

题解：我们枚举所有的 pair，如果连接这两个点不与给出的线段相交，那么就加这条边。最后跑一次 kruskal 即可，可以证明如果 MST 中新加边如果相交，那么一定有另外的边可以替换相交的边。

实现的时候，我们枚举每个点，把其他点对它极角排序，然后扫描线。用一个 set 维护与扫描射线相交的线段，set 中线段按照与射线交点离固定点距离升序排序。那么判断一个点是否可见，只需要判断它在 *set.begin() 这条线段的哪一侧即可。实现细节：

• 极角排序用叉积

• 扫描射线初始为 \(x\) 轴正方向，要把初始的相交线段放入 set，这些线段的入端点和出端点也要打标记

L. Liesbeth and the String

题目大意：长度为 \(n\) 的由字母 \(a\) 组成的串，询问做多少次操作变成长度为 \(1\)。每次操作删掉起始两个字符，并根据第一个字符是 \(a,b,c\) 分别在末尾拼接 \(bc,a,aaa\)。

题解：只考虑操作途中仅由 \(a\) 组成的串，发现是考拉兹猜想（Collatz conjecture）/角谷猜想。

M. Matrix, The

题目大意：求字典序第 \(k\le10^{18}\) 小的满足下列条件的 \(n\times n\) 的 \(01\) 矩阵：

• 每一行的 \(1\) 的个数在区间 \([a,b]\) 内
• 每一列至少有一个 \(1\)
• 每一列的 \(1\) 都是连续的

题解：令三进制状态 \(S\) 记录每一列的状态，\(0\) 表示这一列还没有放过 \(1\)，\(1\) 表示这一列末尾放了 \(1\)，\(2\) 表示这一列放过 \(1\) 但不在末尾。令 \(\text{dp}[i][S]\) 表示考虑 \(i,\cdots ,n\) 行，开始状态为 \(S\) 的总方案数，枚举一行中合法的 \(01\) 状态进行转移即可，需要预处理一下转移。

时间复杂度 \(\mathcal{O}(n\cdot2^n\cdot3^n)\)，实际上这个上界远不会达到，可以通过。

Dirt Replay

D: -1 return printf 没有逗号 0

I: -6 本质上都是看错了 input，但是之前没有在本地测试猜想和时限

J: -1 数组开小了，下标写错

M: -2 常数太大 tle两次