Petrozavodsk Winter-2018. ITMO U 1 Contest

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]\) 即可。

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\) 也是有循环节的。