Contest Info

date: 2018.08.13 12:00-17:00

practice link

Solutions

A. Admiral

题目大意：求两个点之间的两条最小不相交路径。

题解：费用流，记得拆点。

B. Beer Pressure

题目大意：\(n(n\leq 5)\) 个旅馆，一共 \(k(k\leq 50)\) 个人。有若干个人预先对旅馆投票，在此基础上，剩余的人依次投票。每次选择一个旅馆的概率是它已拥有票数除以目前已投票总数。都投票完成后，票数最高的旅馆获胜，如果有多个，那么等概率获胜。先给出一个初态，问每个旅馆获胜概率。

题解：设状态为 \((a_1,a_2,a_3,a_4,a_5)\)，那么有 \(\sum_{i=1}^5a_i+t=50,a_i, t\geq 0\)，于是状态一共有 \({55\choose 5}=3478761\) 个。直接爆搜即可。

C. Cycling

题目大意：在水平数轴上有 \(0\le L\le10\) 个红绿灯，第 \(i\) 个红绿灯坐标在 \(X_i\)，红灯每个周期亮 \(10\le R_i\le500\)，绿灯每个周期亮 \(10\le G_i\le500\)。在 \(t=0\) 时所有红绿灯恰好都开始亮红灯，同时一个人骑自行车从 \(0\) 出发，要去 \(1\le X_{dest} \le1000\) 处。

这个人可以以 \(0.5m/s^2\) 的最大加速度进行加速，但减速到任意速度（或停止）不花费时间。他不可以闯红灯，不可以逆行，但是可以在任意点停留，问到达目的地的最短时间。

题解：最坏情况是等待每一个红绿灯，这样时间也不会超过 \(6000\)。因此只用考虑每个红绿灯至多 \(300\) 个周期的状态。关键时间点包括起始时间 \(0\)，以及每个绿灯的结束时刻，对于这些关键点，我们到达时的速度越大越好。

最优的运动方式只有两种，将两种状态都记为 \(q\) ：

• 以初始速度 \(q>0\) 进行匀加速运动
• 停留 \(-q(q<0)\) 秒后，以初始速度 \(0\) 进行匀加速运动

这样在 \(t\) 时刻从坐标 \(x\) 出发能通过某个红绿灯的某个周期的 \(q\) 是一个区间，我们可以进行 dfs 。每次 dfs 时看当前运动状态是否可以通过第 \(i\) 个红绿灯，更新临界状态的最大速度，并将可以通过的状态继续下一个红绿灯处的搜索。

时间复杂度为 \(\mathcal{O}(n^2)\)，这里 \(n\le3001\) 是关键点的数量。

D. Digital Clock

签到题

E. Edge Case

题目大意：求一个 \(n\le10000\) 元简单环有多少种不同的匹配方案。

题解：令 \(f(n)\) 表示长度为 \(n\) 的一条链有多少中不同的匹配方案，则 \(f(0)=f(1)=1,f(n)=f(n-1)+f(n-2)\)。枚举选不选 \(1\) 和 \(n\) 这条边，环上的方案就是 \(f(n)+f(n-2)\)。答案很大，可以写个 java。

F. Foul Play

题目大意：\(n=2^k\) 个队伍进行锦标赛，你知道任意两支队伍的胜负关系，让你安排一种比赛方法，使得 \(1\) 号队是冠军。保证 \(1\) 号队可以打败至少一半队伍，并且对于某个队伍 \(t\)，若 \(1\) 不能胜它，那么存在一个队伍 \(t'\) 可以胜 \(t\)，且 \(1\) 可以胜 \(t'\)。

题解：构造一个方案使得下列两个条件可以一直保持：

• \(1\) 号点可以打败至少一半队伍

• 对于某个队伍 \(t\)，若 \(1\) 不能胜它，那么存在一个队伍 \(t'\) 可以胜 \(t\)，且 \(1\) 可以胜 \(t'\)

如果对于只有两个队伍的时候，上述条件成立，那么显然有解。对于其他情况，我们考虑，设 \(1\) 可以打败的队伍为 O，不能打败的队伍为 X，在 O 中可以打败 X 的为 B。那么我们可以安排一次锦标赛如下：

   1     2    3       4
+-------------------------+
|BBBBB | 1 | XXX | (X)OOOO|
|XXXXX | O | XXX |  O OOOO|
+-------------------------+

我们在第一列安排尽可能多（显然至少存在一个）的 B 和 X 的 pair，那么可以看出每次 X 至少减少一半，所以条件 1 满足。考虑条件 2，对于第三、四列中存活的 X，显然它们都会被第一列中的 B 打败（如果被 O 打败，那么可以提到第一列），而第一列中的 B 都存活。证毕。\(\Box\)

G. Guards

题目大意：给出一个无向连通图 \(G\) ，点数 \(n\le10000\) 。\(G\) 可以被缩点成一棵树，每个点是原图中的一个不超过 \(10\) 个点的连通块。求 \(G\) 的最小顶点覆盖数。

题解：块内暴力枚举可以覆盖内部边的点集，块间树 dp。时间复杂度 \(\mathcal{O}(n\cdot2^{10})\)。

H. Hip To Be Square

题解：给你一个区间 \([a,b](1<a<b\le 4900)\) ，求出它的一个非空子集，使得其中元素的乘积是完全平方数，且乘积最小。

题目大意：首先注意到若 \([a,b]\) 中有完全平方数，那么答案一定是其中最小的完全平方数。否则，在题目的数据范围下，区间中至多有 \(138\) 个数。

我们把每个数质因数分解，如果某个质数只出现了一次，那么它所在的数一定不能选取；如果某个质数恰出现了两次，那么这两个数要么同时选取，要么同时不取，可以合并。这样可选的数至多只有 \(35\) 个。折半暴搜再剪剪枝就可以通过了。

I. Idol

题目大意：问 2-sat 是否存在一个 \(x_1=1\) 的解。

题解：如果 \(x_1\) 和 \(\lnot x_1\) 不在一个连通块，那么 \(x_1\) 可以取任意值；否则在一个连通块，那么 \(x_1\) 在 \(\lnot x_1\) 拓扑序后面的时候可以取 \(1\)。在我的模板下只用判断是否有 bel[1] < bel[1 + n] 即可。

J. Joint Venture

签到题

K. Key Insight

题目大意：给你两个长度为 \(n\) 的串 \(s\) 和 \(t\)（下标从 \(0\) 开始），再给出 \(k\)， \(k\) 是 \(n\) 的一个约数，求所有满足下列要求的 \(0\sim k-1\) 排列 \(p\) 的数量：对于按长度 \(k\) 依次分成的 \(\frac{n}{k}\) 块，每块内部的变化是排列 \(p\)，也即

\[ \displaystyle \forall i\in [0,n),\displaystyle s_{i}=t_{ \displaystyle k\lfloor i/k \rfloor+p_{\displaystyle i\text{ mod }k}} \]

题解：我们将 \(s\) 和 \(t\) 分别分解为 \(k\) 个 \(\frac{n}{k}\) 元组，第 \(i\) 个为 \(S_{i}=\left(s_{i},s_{i+k},\cdots,s_{i+(\frac{n}{k}-1)k}\right)\)。那么条件等价于，对于 \(\forall i\in[0,k),S_{i}=T_{p_{i}}\)。那么我们只需要把 \(S\) 和 \(T\) 对应相等的 \(\frac{n}{k}\) 元组找到，所有合法的排列数量即为每种 \(\frac{n}{k}\) 元组的数量的阶乘的乘积。

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

Dirt Replay

A: -1 W没拆点

D: -1 W时间加法进位19没进20

K: -1 结论漏了情况

B: -2 没考虑全0的情况，0除以0出现nan；搜索的时候常数太大，每次要decode