Contest Info

practice link

Solutions

A. Cram Time

签到题。

B. Minimum path

签到题。

C. Triple Flips

题目大意：给你一个长度为 \(n\) 的 \(01\) 串，每次操作选取一个三项的等差数列，将这三项取反。要求你在 \(\lfloor\frac{n}{3}\rfloor+12\) 步之内将这个数列全变为 \(0\)，或判断不可能。

题解：数列较短时直接暴搜。数列较长时，考虑每次用 \(k\) 步将前 \(3k\) 项变成 \(0\)，最后一部分暴搜。

\(k=1\) 时容易发现 110 不可能一步变成 \(0\)

\(k=2\) 时暴搜可知，只要 \(n\ge11\)，任意 pattern 都能两步变成 \(0\)

D. Familiar Operations

题目大意：给你两个小于 \(10^{6}\) 的数，每次可以让其中一个数乘上一个质数或者除以一个质数（整除）。问最少多少次使得两个数约数个数相等。有 \(10^{5}\) 次询问。

题解：不同的质因数分解 pattern 只有 \(289\) 种。直接暴搜即可，一边最多操作 \(8\) 次。

E. Rain Protection

题目大意：有两个点，分别可以在线段 \((0,0),(w,0)\) 和线段 \((0,h),(w,h)\) 上运动。有 \(n\) 个整点，分别在第 \(t_{i}\) 秒出现在 \((x_{i},y_{i})\)，保证 \(x_{i}\in[0,w],y_{i}\in(0,h)\)。现在要求每个整点出现的时候，都落在这两个点的连线段上，问端点移动的速度至少是多少，或判断不可能。

题解：判断不可能比较简单。

计算时间时显然先二分速度，然后倒序扫描时间。我们维护两个点的横坐标组成的点的可行域，容易发现一定是一个凸多边形。

如果当前时间只有一个点，那么当前时间的可行域是一条线段。与凸多边形求交之后，线段经过 \(t\) 秒的运动会变为一个六边形，需要注意和边界做一个半平面交。

如果当前时间有若干共线的点，那么当前时间的可行域是一个点。与凸多边形求交之后，线段经过 \(t\) 秒的运动会变为一个正方形，也要和边界交一下。