Contest Info

date: 2019.03.06 15:59-20:59

practice link

Solutions

A. Airport Check-in

题目大意：有 \(n\in[2,4]\) 个柜台，每个柜台的服务时间在 \([l,r]\) 中独立均匀分布，记为 \(t_{i}\)。现在每个柜台服务的剩余时间在 \([0,t_{i}]\) 中独立均匀分布，记为 \(p_{i}\)。现在有一个人，他会选择剩余的服务时间最少的柜台，问这个柜台恰好也是服务时间最少的柜台的概率。

题解：不妨设 \(1\) 号柜台的 \(t_{i},p_{i}\) 都最小，最后答案乘 \(n\) 即可。以下有可能省略取值范围，请自行理解（咕咕咕）。

以 \(n=2\) 为例。概率密度函数为 \(f(t_{1},t_{2},p_{1},p_{2})=\frac{1}{(r-l)^{2}t_{1}t_{2}}\)。答案即为 \[ \begin{aligned} &\iiiint_{p_{1}\le p_{2}\le t_{2},p_{1}\le t_{1}\le t_{2}}f(t_{1},t_{2},p_{1},p_{2})\mathbb{d}t_{1}\mathbb{d}t_{2}\mathbb{d}p_{1}\mathbb{d}p_{2}\\ =&\frac{1}{(r-l)^{2}}\iiint_{p_{1}\le t_{2},p_{1}\le t_{1}\le t_{2}}\frac{t_{2}-p_{1}}{t_{1}t_{2}}\mathbb{d}t_{1}\mathbb{d}t_{2}\mathbb{d}p_{1}\\ =&\frac{1}{(r-l)^{2}}\iint_{p_{1}\le t_{1}}\frac{r-p_{1}\ln r-t_{1}+p_{1}\ln t_{1}}{t_{1}}\mathbb{d}t_{1}\mathbb{d}p_{1} \end{aligned} \]

之后就不写了。

对于 \(n\ge 3\) 的情况，注意到 \((t_{i},p_{i})(i\ge2)\) 对之间相互独立，因此答案为 \[ \frac{1}{(r-l)^{n}}\iint_{p_{1}\le t_{1}}\frac{(r-p_{1}\ln r-t_{1}+p_{1}\ln t_{1})^{n-1}}{t_{1}}\mathbb{d}t_{1}\mathbb{d}p_{1} \]

需要用到分部积分的技巧。

B. Beyond the Rescue

题目大意：一个城市的广场（点）和连接广场的道路（边）构成了一棵树。一个杀手要从 \(s\) 走到 \(t\)，警察则是沿着序列 \(a_{1},\cdots,a_{n}\) 循环移动，每两个点之间警察会走最短路。开始时警察在 \(a_{1}\)。每条边杀手和警察走需要的时间不相同。如果杀手和警察在点相遇，不会发生任何事情；如果在边相遇（只需要在同一条边，不需要在边的同一个位置），杀手会被抓住。求杀手安全地从 \(s\) 走到 \(t\) 所需的最小时间，或判断不可能走到。

题解：显然杀手一定会走 \(s\) 到 \(t\) 的最短路，如果绕路的话，还不如在原地等。这样的话，警察走的路也可以看做杀手走的路上的一段区间。从而这个问题转化到了序列上。

我们考虑杀手要从 \(i\) 走到 \(i+1\)。我们能够知道警察在哪些时间段会经过这条边，这些时间段是不能走的。而时间段之间的 gap 则是可以通过的。杀手显然会选择离当前时间最近，且时间间隔不小于他走这条边所需时间的那个 gap。如果没有则无解。

类似于扫描线，我们让杀手一步一步走，每个警察最多进入和删除一次。用线段树来维护这些 gap。警察所走的边有两种，一种是从小到大，经过这条边的时间随杀手的行走逐渐增大；一种是从大到小，经过这条边的时间随杀手的行走逐渐减小。所有的 gap 考虑它两边的边的种类，共有四种可能，所以需要四棵线段树。容易发现，对于同一种 gap，在杀手移动一步后（例如从 \(i\to i+1\) 到 \(i+1\to i+2\)），它们都改变同样大的数值。我们可以用 offset 来维护这种变化。

查询的时候直接在线段树上二分即可。注意到警察是循环移动的，所以线段树需要查两次（现在想想，好像把序列延长一倍好一些）。

好难写啊。。。

C. Casino Cheating

题目大意：交互题。一开始对手手上有单位 \(1\) 的巧克力，你手上为 \(0\)。操作 \(n\) 轮，交替操作，从你开始。保证 \(n\) 为奇数。你每次可以选择对手手上一块巧克力，选择一个 \(x(\frac{1}{3}\le x\le \frac{2}{3})\)，你获得那块巧克力的 \(x\) 倍，对手剩下 \(1-x\) 倍。

对手每次等概率从你手上选择一块巧克力，然后选择 \(x=\frac{2}{3}\)。要求你最后手上的巧克力总和大于 \(0.55\)。

题解：如果 \(n=1\)，那么直接选 \(x=\frac{2}{3}\)。下面考虑 \(n\ge 3\)。如果你每次贪心的拿对方最大块的 \(\frac{2}{3}\)，那么你最后大概可以得到 \(\frac{1}{2}\)（模拟一下可以得到？）。

第一次拿 \(\frac{1}{3}\)，然后最后一次拿一开始剩余的 \(\frac{2}{3}\) 的 \(\frac{2}{3}\)，那么你至少可以有 \(\frac{4}{9}\)。对方的第一次会拿取你手上 \(\frac{1}{3}\) 的 \(\frac{2}{3}\)，也就是 \(\frac{2}{9}\)。你对 \(\frac{2}{9}\) 采用上述的贪心策略，大概可以得到 \(\frac{1}{9}\)。那么总的就是 \(\frac{5}{9}\approx 0.5556 > 0.55\)。

D. DotA Quals

签到题。

E. Enumeration of Tournaments

题目大意：题意有毒。主要问题在于需要对 \(\mathcal{O}(\log n)\) 个 \(x\) 计算 \((2x-1)!!\)，其中 \(x\) 大致在 \(10^{18}\) 范围内。对 \(2^{64}\) 取模。

题解：考虑多项式 \(f_{n}(x)=\prod_{i=0}^{n-1}(2x+2i+1)\)，我们令 \(x=0\)，这个多项式的值即为 \((2n-1)!!\)。注意到 \(x\) 的系数总是 \(2\)，那么大于等于 \(x^{64}\) 的项的系数模 \(2\) 全为 \(0\)。

我们首先倍增地预处理出所有的 \(f_{2^{i}}(x)\)，然后类似于数位 dp 地查询即可。

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

F. Fresh Matrix

题目大意：定义一个 \(01\) 矩阵是好的，当且仅当所有 \(1\) 都不相邻，所有 \(0\) 相互四连通。问有多少种 \(n\times m\) 的好的 \(01\) 矩阵，对质数取模。\(n\le11,m\le10^{9}\)。

题解：对列记录该列有哪些格子是 \(1\)，以及 \(0\) 的格子之间的连通情况，状态有 \(2161\) 个，转移有 \(96219\) 个。然后 BM 即可。

复杂度 \(\mathcal{O}(ST+S^{2}\log m)\)。如果你想用 FFT 优化到 \(\mathcal{O}(ST+S\log S\log m)\)，那自然也是极好的。不过抄板可能会累死你 : P

G. Game of Chairs

题目大意：给出一个序列 \(a_i\)，\(1\le a_i\le c\)。选择一个位置 \(i\)，然后会随机选择一个整数\(k\in[1,c]\)，代价是距离 \(i\) 最近的该整数位置的距离，让你选择一个位置 \(i\) 最小化代价的期望。

题解：每种数字独立，考虑相邻的两个位置，中点左边由左边的点贡献，右边由右边的点贡献（两端单独处理），对于每个位置 \(x\) 维护一下 \(Ax+B\) 即可，通过查分和前缀和可以做到 \(\mathcal{O}(n)\)。

H. Hung Fu

题目大意：给定长度为 \(n\) 的正整数数组 \(a, b\)。求一个排列 \(p\)，最小化：

\[ \sum_{i=1}^n \text{min}_{1\le j\le i}a_{p_i}\oplus b_{p_j} \]

最小值相同的时候，要求排列字典序最小。

题解：我们先求出最小值。观察式子可以发现，每个 \(p_i\)，我们需要找到一个 \(p_j\) 满足 \(j\le i\)，如果不考虑取等的情况，这让我们想到了树。建有向图，枚举所有的有向边 \(j\rightarrow i\)，边权为 \(b_j\oplus a_i\)。考虑取等的情况，我们新建一个结点作为根，连接有向边 \(\text{root}\rightarrow i\)，边权为 \(b_i\oplus a_i\)。求最小树形图，即得到了最小值。

要使得方案最小，我们从左往右枚举排列的每个位置，每种取值，然后 check 当前的图能否达到最小值即可。一次 check 的复杂度为 \(\mathcal{O}(n^2\log n)\)，总复杂度 \(\mathcal{O}(n^4\log n)\)。

I. Is It a p-drome?

题目大意：给出一个长为 \(m\) 的串 \(s\) 和一个长为 \(n\) 的排列 \(p\)，求出 \(s\) 所有长度为 \(n\) 的子串 \(s'\)，满足 \(\forall i,s'_{i}=s'_{p_{i}}\)。

题解：对排列构造多项式解决这个问题。首先我们找出所有环，然后为每个环分配一些随机的数，使得它们加起来等于 \(\text{mod}\) 即可。然后把串 \(s\) 的多项式（数字作为系数）反过来跟排列 FFT 即可。要保证正确性，可以多随机映射几次原数字到 mod 范围内。

coldwater’s comment:

一种分配方法是，对于 \(\forall i\)，随机一个数 \(c\)，将 \(\text{coe}_i\) 加上 \(c\)，将 \(\text{coe}_{p_i}\) 减去 \(c\)。

J. Journey

题目大意：长度为 \(n\) 的数列 \(a_i\)，满足 \(a_i\in [1, n)\)。你一开始站在位置 \(1\)，手上拿着数 \(h_1(h_1\in [1, n))\)。假设位置 \(i\)，手上拿的数是 \(h_i\)，那么你可以跳到 \(i+h_i\) 或者 \(i+a_i\)。\(h_i\) 等于上一跳的距离。求 \(1\) 到 \(n\) 的方案数。

题解：题意可以理解为在位置 \(i\) 可以跳到位置 \(j=i+k\cdot a_i(k\ge 1, a_j\neq a_i)\)。从后往前计算方案数。初始值 \(f_n=1\)。将 \(a_n\) 设置为 \(-1\)。

那么 \(\displaystyle f_i = \sum_{k = 1, j = i + k\cdot a_i}^{j\le n} f_j\cdot [a_j\neq a_i]\)。从后往前计算。对 \(a_i\) 大小分块，如果 \(a_i \ge \sqrt n\)，我们直接暴力枚举 \(k\) 即可。

记录 \(\text{sum}[i][j]\) 表示下标模 \(i\) 余 \(j\) 的位置的和。如果 \(a_i< \sqrt n\)，那么答案为 \(\text{sum}[a_i][i\bmod a_i]\)。更新的时候对 \(\forall j, j\neq a_i\)（通过 \(a_i\) 跳过来的时候不被贡献），更新 \(\text{sum}[j][i\bmod j]\) 即可。

K. Kid’s Nightmare

题目大意：给定一个弦图，问最少删掉多少个点使得没有环。

题解：求出弦图的 clique tree，然后在上面 dp，复杂度 \(\mathcal{O}(m\sqrt m)\)。

（不会写

L. Lazy Student

题目大意：一场考试有 \(n\) 次机会，如果在一次考试中复习了 \(x\in[0,1]\) 的知识，那么通过的概率为 \(x\)。一个人每次考试前会复习一些知识，复习过的知识不会再忘记。考试必须通过，也就是说最后一次考试前必须复习完。问最优策略下最小的复习数量。答案化为最简分数后，分子分母分别对 \(10^{9}+7\) 取模。

题解：设 \(f_{k}(x)\) 表示还剩 \(k\) 场考试，已经复习 \(x\) 的知识，最小的期望复习数量。答案即为 \(f_{n}(0)\)。

那么显然有 \(f_{1}(x)=1\)，\(f_{i}(x)=\displaystyle \min_{x\le x'\le 1}\big(x'^{2}+(1-x')f_{i-1}(x')\big)\)。因此 \(0\le x\le\frac{1}{2}\) 时有 \(f_{2}(x)=\frac{3}{4}\)，且 \(x>\frac{1}{2}\) 时，\(f_{2}(x)>\frac{3}{4}\)。设 \(f_{i}(0)=a_{i}\)，我们可以猜测 \(\displaystyle{a_{n+1}=a_{n}-\frac{a^{2}_{n}}{4}}\)。容易证明 \(a_{n}\) 单调递减，因此这个猜测是正确的。

稍微推一下可以发现，\(\displaystyle{a_{n}=\frac{b_{n}}{2^{2^{n}-2}}}\)，其中 \(\displaystyle{b_{n+1}=2^{2^{n}}b_{n}-b^{2}_n}\)。后面这个比较难搞，我们首先两边除以 \(\displaystyle{2^{2^{n+1}}}\)，有 \(\displaystyle{\frac{b_{n+1}}{2^{2^{n+1}}}=\frac{b_{n}}{2^{2^{n}}}-(\frac{b_{n}}{2^{2^{n}}})^{2}}\)，令 \(\displaystyle{\frac{b_{n}}{2^{2^{n}}}=c_{n}}\)，则有 \(c_{n+1}=c_{n}-c^{2}_{n}\)。事实上这个式子应该是没法找出通项的（也可能是我太菜了），但是我们可以找循环节，\(5000\) 多项就开始循环了。

coldwater’s comment:

设 \(a_n\) 可以被表示为既约的两部分 \(\frac{b_n}{c_n}\)。注意 \(a_1=\frac{1}{1}\)，分子是一个奇数。用数学归纳法，\(\displaystyle a_{n+1}=a_n-\frac{a_n^2}{4}\)，得到 \(\displaystyle a_{n+1}=\frac{4b_nc_n-b_n^2}{4c_n^2}\)。分子还是奇数，而分母是 \(2\) 的幂，显然是既约的。还可以观察到分母的递推式是独立的，所以我们可以求出 \(\frac{P}{Q}, Q\) 取模之后的值，二者相乘就可得到 \(P\)。同样的 \(a_i\) 也是有循环节的。