Contest Info

date: 2018.08.29 13:30-18:30

practice link

Solutions

A. GUI

签到题

B. Searching on the Cube

题目大意：交互题。在一个 \(n\times n\times n(3\leq n\leq 300)\) 的立方体上，在 \(6n^2\) 个表面格子中有一个格子装有宝藏。你在某个表面的某个格子处，面朝某个方向。每次可以选择左转、右转、前进或者挖四种行为。每次前进之后，jury 会告诉你你现在距离宝藏的在三维空间中的欧式距离（两个格子中心点的距离）的变化情况（closer、farther 或者 same），当你确信你在装有宝藏的格子时，输出 dig 来挖宝藏。注意你不知道 \(n\) ，也不知道你的初始位置和方向，更不知道宝藏的位置。

题解：容易发现有两个极值点，在这两个点处往周围任何一个方向走一步都不会 closer。这两个极值点分别为宝藏，和宝藏在立方体对面的对应位置。我们可以一直贪心地走到某一个极值点，然后我们往一个方向一直前进，每一步都检查当前是否为另一个极值点。如果走到了另一个极值点，并且一路上的 farther <= closer，那么走到的这个极值点有宝藏，否则我们走回原来的位置挖出宝藏。

C. Mirrors

题目大意：有一个 \(n\times m(n\le10^{9},m\le10^{9})\) 的网格图。图中有 \(s\) 面镜子，每面镜子占一格，镜子的中心位于格子的中心。镜子有 \(4\) 种朝向，\(0\) 代表垂直，\(1\) 代表从格子的左下到右上，\(2\) 代表水平，\(3\) 代表从左上到右下。一些镜子是固定的，另一些镜子从 \(t(1\le t\le p)\) 秒开始，每隔 \(p(1\le p\le7)\) 秒顺时针旋转 \(45^{\circ}\)。另外图中有若干个起点和一个终点，一个人想要尽快地走到终点。他可以从任意非负整数时间开始，从任意一个起点，沿任意一个方向出发，以 \(1格/s\) 的速度行走。在行走过程中，如果他碰到镜子或者边界就会被反射。求他走到终点最短的时间。

题解：注意到对于所有镜子，\(lcm(4,\cdots,28)=1680\)，因此每隔 \(1680s\)，所有镜子的状态一定和原先相同。设 \(dp[i][time][dir]\) 表示这个人当前在第 \(i\) 面镜子，当前的时间模 \(1680\) 为 \(time\)，方向为 \(dir\) 的状态下，走到终点所需最小的时间。转移时只需在图中查询沿当前方向走到的下一面镜子，采用记忆化搜索即可。

时间复杂度 \(\mathcal{O}(1680s\log s)\)。

D. Roads to cinematography

题目大意：给定 \(n\) 个点，满足：

\[ \begin{cases} 0\leq x_1\leq x_2\leq x_3\leq \dots \leq x_{n-1}\leq x_n\\ 0\leq y_n\leq y_{n-1}\leq y_{n-2}\leq \dots \leq y_2\leq y_1 \end{cases} \]

要求你连接一些与坐标轴平行的边，使得 \((0,0)\) 与这些点连通。

题解：显然 \(1\) 号点往下走， \(n\) 号点往左走。那么存在一个点 \(i\in[1, n)\) 满足 \(i\) 往左， \(i+1\) 往下，于是区间可以分为 \([1,i], [i+1,n]\)。区间 dp 即可。

E. Geometric solver

签到题。

F. Monsters

题目大意：给定两个长度为 \(n\) 的正整数数列 \(\{M_i\},\{S_i\}\)，定义当前的价值为 \(\displaystyle \prod_{i=1}^n \min\left(M_i, \max_{j=1}^iS_j\right)\)。还有 \(k\) 次修改，每次把两个数列中的某个数字变大，让你每次输出修改之后的价值。

题解：

将题目变形一下，令\(S^{'}_1=X,S^{'}_{i+1}=S_i\)，则要求\(\prod_{i=1}^n \min(M_i, \max_{j\le i}S^{'}_i)\).

将数列按大小\(T\)分块，每块按\(M_i\)升序排列并维护\(val_i=\min(M_i, \max_{j\le i}S^{'}_i)\)。

修改\(M_i\)，则重建一块，利用冒泡排序在\(O(T)\)时间内完成。

修改\(S^{'}_i\)，则是对于区间\([i,j]\)，满足\(j=\max\{k|\max_{k\le j}S^{'}_k=S^{'}_i\}\)，将\(M_k\ge S^{'}_i\)的\(Val_k\)都改成\(S^{'}_i\).

显然对于每个被修改的位置，下一次修改的\(S^{'}_i\)是单调不降的。

因此我们可以每块记录一下最后一次修改的\(S^{'}_i\)，这一次修改时没有改的值一定不会再被修改了，它们的\(val\)应该等于\(a\)，然后会有一个后缀被修改为\(S^{'}_i\)，每次重建块时会有\(O(T)\)的势能，暴力修改就好。

因为算后缀积时需要用到快速幂，复杂度为\(O(\frac{n}{T}\log{n})\)。

时间复杂度为\(O(nT+\frac{n^2}{T}\log{n})​\)，\(T​\)取\(O(\sqrt{n\log{n}})​\)时有最小值\(O(n\sqrt{n\log{n}})​\).

G. Regular expressions

题目大意：定义正则表达式如下：

• a,g,t,c 字符集

• (R|P)

• (RP)

• (R*)

其中 * 表示可以出现 \(0\) 次或若干次，给出一个字符串集合，输出能匹配这个集合的最短的正则表达式。

题解：显然 ((((a|g)|t)|c)*) 一定是一个答案，其长度为 \(16\)。我们只需要暴力生成长度小于等于 \(15\) 的正则表达式，然后每次暴力判断即可。我们先枚举不含 * 和 | 的基本串，并且显然这些串中不能有连续的相等子串，例如 agaga 可以写成 (a((ga)*)) ，优于 ((((ag)a)g)a)。然后我们在基本串上应用规则生成其他串即可，几个剪枝：1.基本串不直接拼接。2.我们用 | 连接两个串的时候，要求前半的长度大于后半。3.不拼接 (u*) 和 u，也不在 (u*) 的外面套一层 *。

最后，我们可以搜出 \(50403\) 个串。c++ 的 std::regex 很慢，所以我们用 java 的 Pattern 类，预处理之后直接暴力即可，可以通过本题。

H. WSO-2017 soccer team

题目大意：

给出两个数列\(a_n\)与\(b_n\)，\(n\le10^5\)。

\(m\le10^5\)次询问，每次询问一个区间\([l,r]\)，保证区间长度是\(3\)的倍数。

问将区间中的位置等分成三组，第一组贡献\(a_i\)，第二组贡献\(b_i\)，第三组贡献\(\frac{a_i + b_i}{2}\)，最大的总贡献是多少。

题解：

按\(a_i-b_i\)排序，则是让区间前\(\frac{len}{3}\)大去第一组，前\(\frac{len}{3}\)小去第二组，剩下的在第三组。

在主席树上二分即可，\(O(n\log{n})\).

I. Primitive divisors

签到题。

J. Tickets

签到题。

K. Logarithm smoothing

题目大意：定义 \(f(x)=c\ln x\)，要求你在 \([a,b]\) 这段区间内找出一个不超过 \(n\) 段的折线段 \(g(x)\)，使得 \(\max_{x\in[a,b]}|f(x)-g(x)|\) 最小，求这个最小值。

题解：二分答案，并且注意到 \(c\) 可以最后乘。设当前二分到的值为 \(mid\)，那么就相当于我们要判断在 \(x\in[a,b],y\in[\ln x-mid,\ln x+mid]\) 这样一个图形中，能否用不超过 \(n\) 段折线将 \(x=a\) 和 \(x=b\) 连接起来。

我们从 \((a,\ln a+mid)\) 出发，二分求出我们最远能走到 \(y=\ln x+mid\) 的什么位置，使得这两点的连线与 \(y=\ln x-mid\) 相切或不相交。之后再从新的点用同样的方法走，直到走到 \((b,\ln b+mid)\)。判断走的段数是否超过 \(n\) 即可。

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

L. Outer space signals

签到题。

Dirt Replay

A: -2 D 弱智

B: -4 没有还原位置，没有还原方向，f 和 c 个数关系判断错

D: -3 输出方案写错

E: -2 算法细节

J: -1 交成了 hello world（数字题号有毒）

K: -3 式子写错两次，eps 开大了

L: -1 没有判串不存在