[3rd ucup] Zielona Góra 站选做

有点奇怪的一场，有一些通过人数稍少但反而简单的题。

感觉有几个我没做出来的题不算难，导致我感觉我是个唐氏。

比赛链接。

E. Pattern Search II

题意

定义 ，，。

给定一个由 构成的串 。

找出一个最短的串 ，满足 是 的子序列，且 是 的子串。

。

题解

设 。

首先可以发现， 这个串里面不会出现 和 这两个子串。

换句话说， 中相邻三个字符，一定至少出现了一个 和一个 。

也就是说，答案一定不会超过 。

考虑如果我们找到了一个合适的 ，使得 是 的子串，这代表了什么。

我们知道 。

假设 完全在 或 中，那么这很牛。

否则我们可以知道， 在 中一定是 的右边和 的左边一段拼起来。

那么考虑如果 ，『 的右边』就一定在 这一部分以内，『 的左边』就一定在 这一部分以内。

这说明 是 的子串。

综上所述，如果 并且 是 的子串，那么 一定是 的子串。

这就说明，我们只需要找一个 满足 ，那么我们直接在 里面找答案就好了。

那么现在问题在于，如何找答案。

考虑到硬做肯定是不太好做的，那么我们就必须要利用这个串的特殊性质。

那么这个串有什么性质呢，。

那么就设 表示在 中匹配 这一段，可以匹配到哪里（以及如果匹配完了需要多长）。

就会有 。考虑到 大约是 级别的，所以算出这个 dp 值是 的。

然后直接枚举 在 中的起点，然后根据这个 dp 的值算出结尾位置即可。

时间复杂度 。

提交记录。

L. Chords

题意

圆上有 个点，被随机分成了 个弦。

找出一个弦的集合，使得其中任意两条弦不相交，使得这个集合大小最大。

。

题解

有点脑瘫了。

首先断环为链，设 表示只选两端点都在 这个范围内的弦，答案最大是多少。

一共两种情况，第一种是不选 对应的弦，此时贡献是 。

第二种情况是 是某条弦的左端点，其对应的右端点 满足 。

那么这种情况的贡献是 。

这样就得到了一个 的做法。

考虑因为数据随机，所以答案不会太大。

所以设 表示最小的 ，使得 。

时间复杂度 。

提交记录。

J. Polygon II

题意

现在有 条线段，第 条线段长度是 间的随机实数。

求出这些线段能够组成一个 边形的概率。

，。

题解

感觉和我想象的做法完全不一样，有点牛。

设第 条线段长度为 ，那么容易发现一组方案不合法当且仅当存在一个 使得 。

同时容易发现，如果一组方案不合法，那么只会出现一个这样的 。

也就是说，我们可以考虑计算方案不合法的概率，即 。

同时我们知道 是在 内均匀随机的，这个东西他非常的对称。

所以有 。

问题在于这个东西怎么计算，考虑所有 的随机范围是一个 的次幂，所以考虑按照二进制位来考虑。

设 为一个随机变量，满足 。设 为 间的随机实数。

发现可以直接拿 来代替 。

设 表示已经考虑完了所有 的 取值，当前 的二进制下最低 位，恰好 的概率

转移是比较容易的，唯一可能出现问题的地方在于 怎么算。

容易发现这相当于算 个 内随机实数变量，和 的概率是多少。

这可以看成一个 维空间中，一个边长为 的超立方体中，各维坐标和 的点体积是多少。

直接对边长为 的超立方体这个条件进行容斥即可。

时间复杂度 。

提交记录。

B. Roars III

题意

给定一棵 个点的树，初始时你已知某些点上有一颗石子。

现在可以进行若干次操作，每一次操作是选择一个石子，并向其将点 移动一步，要求不能有两个石子同时在一个点上。

对于每一个 ，求出石子移动的最大次数。

。

题解

先考虑如何对单个 求出答案。

考虑找到一个最深的点 ，使得 上当前没有石子，并且 子树内至少有一个石子。

那么我们找到 子树里面的一个点 ，满足 上有石子且深度最深。

（注意到此时 这条链的所有点上都有石子）

那么我们贪心的把 这一段石子统一往上移一个位置。

使用线段树维护这种东西，单个 就可以 算出来。

那么考虑直接加一个换根就过了。

时间复杂度 。

提交记录。

I. Mercenaries

题意

现在有 个城市和 条道路，第 条道路连接了城市 和 。

每一个城市都有一个勇士，第 个城市的勇士力量属性为 ，魔法属性为 。

每一条道路上都有一个商店，第 条道路上的商店有 个物品，属性分别为 。

若一个勇士当前在城市 ，则他可以走到城市 去，并在第 条道路的商店购买至多一个物品。

购买的物品的力量、魔法属性将会直接加给这个勇士。

给定 次询问，第 次询问中，第 个城市出现了一个怪物，属性分别为 。

一个力量为 ，魔法为 的勇士能打败他当且仅当 。

求一个最大的 ，使得第 个城市的勇士走到城市 后能打败这个怪物。

，。

题解

可能是这场最难的题，给了我一种我想出来不太可能，但是想不出来很脑瘫的感觉

考虑将人和道具都看成二维平面上的点，那么如果这里有一坨点，只有他们的右上凸壳是有用的。

考虑假如我们走过了两条路，这两条路拿道具的方案很多，但是由于只有凸壳上的点有用。

所以我们只需要把两条路的凸壳做闵可夫斯基和，就能得到从两条道路上拿道具的方案数。

所以用线段树直接维护每一个树上的区间，人和道具组成的凸包。

合并两个区间就是左边的人和右边的道具做闵可夫斯基和，然后再和右边的人放一起再求一遍凸壳。

然后把所有询问离线下来，按照 进行排序，然后线段树上二分。

复杂度是单 的。

提交记录。