Contest Info

date: 2019.03.19 16:14-21:14

practice link

Solutions

A. Piece of Cake

题目大意：给你一个 \(n\) 个点的凸包，等概率选取 \(k\) 个点，问这 \(k\) 个点的凸包的期望面积。

题解：枚举每条边，计算叉积以及被选取的概率即可。需要注意精度。

B. Busy Board

题目大意：给你一个由 \(X\) 和 \(O\) 组成的棋盘，每次操作你可以将一个 \(O\) 变成 \(X\)，然后将同行同列的其它位置置为 \(O\)。给出开始和结束时的局面，问是否可能。

题解：首先注意到，如果结束时某一行（列）有两个以上的 \(X\)，那么这一行不能被操作，否则这一行（列）一定至多有一个 \(X\)。为了方便， 不妨设这样的行（列）都是最上（左）的行（列）。

XXXX     XXOX
XXOO     XXOO
XOOO     OOXO
XOOO     XOOO

• 如果某个格子行列都有两个以上的 \(X\)，那么它必需保持不变，例如左上角的四个格子。
• 如果某行的 \(X\) 不超过 \(1\) 个，那么它的所有有两个以上 \(X\) 的列要么保持不变（第四行第一、二列），此时该行也不可操作；要么全变为 \(O\)（第三行第一、二列），列同理。
• 假如开始时所有行列均可操作的格子均为 \(X\)，那么开始和结束的局面必须相同。
• 假如开始和结束时所有行列均可操作的格子均为 \(O\)，那么开始和结束的局面必须相同。因为只要操作就会带来至少一个 \(X\)，不可能到达结束的情况。

很容易发现，只要满足上面的要求，一定是可操作的。感性的说，就是你可以在行列均可操作的格子中想干什么干什么，使得所有可操作的行列达到结束时的情况，具体过程请自行脑补。

C. Cost of Living

题目大意：有 \(c\) 个物品，连续 \(y\) 年观察它们的物价，发现物价变化满足 \(p(i,j)=p(i,j-1)f(j-1)g(i)\)，其中 \(p(i,j)\) 表示物品 \(i\) 第 \(j\) 年的物价，\(f(j-1)\) 是第 \(j-1\) 年的物价变化系数，\(g(i)\) 是物品 \(i\) 的物价变化系数。其中有一些数据缺失。给出若干个询问，每次问某一年某一物品的价格。需要判断是否能唯一确定。

题解：取 \(\ln\) 后就变成线性方程组了，高消即可。

D. It’s a Mod, Mod, Mod, Mod World

类欧裸题。

E. Monotony

题目大意：给定一个 \(r\times c\)（\(1\le r, c\le 20\)）的矩阵，每个位置有一个数字，它们互不相同。定义一个矩阵是好的，当且仅当它的每一行、每一列都是单调的（增减性独立）。在所有的 \((2^r-1)(2^c-1)\) 种非空子矩阵中，有多少个好的？

题解：枚举一个行指标集，我们对满足单调性的列来 dp。我们预处理每两列之间的增减性（用一个 \(s\in [0, 2^r)\) 来表示），那么对于当前行指标集，任意两列之间的增减性可以用预处理的值 and 上指标集即可。

然后我们 dp。\(\text{dp}_{i,c}\) 表示当前在第 \(i\) 列，增减性为 \(c\) 的方案数。转移的时候枚举 \(j\)，设列 \(j\) 和列 \(i\) 之间的增减性为 \(k\)。那么有 \(\text{dp}_{i,k}\leftarrow \text{dp}_{i,k}+\text{dp}_{j,k}\)。复杂度 \(\mathcal{O}(2^r\times c^2)\)。

F. Heaps of Fun

题目大意：给你一棵树，每个点的点权在 \([0,d[u]]\) 上独立均匀分布。问这棵树是一个小根堆的概率。

题解：积一下分就行了，每个点的答案是一个分段函数。

G. Intersecting Rectangles

签到题。

H. Rocket Powered Hovercraft

不知道出题人怎么证明是凸的。以后有缘再补吧。

I. Cutting Strings

题目大意：给出一个长度为\(n\le10^5\)的字符串\(s\)，至多删去\(k\)个不相交的子区间，使得剩下的字符串字典序最长。

题解：首先应该尽量最大化开头的最大的字符数量，在相同的情况下再最大化剩下的后缀的字典序。

• 如果开头就是一段连续的最大字符，直接保留不需要任何代价，转而去处理剩下的后缀；
• 如果剩下的操作数足够将全部最大字符都放在开头，操作完后转而去处理剩下的后缀；
• 否则需要选择一段最大字符，选择前面最长的\(k-1\)段最大字符，与它自己的后缀组合成最终的字符串，先最大化最大字符数，再最大化这个后缀的字典序。

前\(k\)大用堆维护，后缀用后缀数组比较即可，时间复杂度\(O(n\log{n})\).

J. Subsequences in Substrings

题目大意：给出字符串\(s\)和\(t\)（\(|s|\le10^5,|t|\le100\)），求\(s\)有多少子串，\(t\)是其子序列。

题解：令\(dp[i][j]\)为\(s\)以\(i\)结尾，\(t\)中是其子序列的最长前缀为\(j\)的方案数，直接转移即可，时间复杂度\(O(|s||t|)\)。

K. Knight of the Tarot Cards

题目大意：给你一个无限大的棋盘，上面有 \(n\) 张卡，第 \(i\) 张卡在 \((r_{i},c_{i})\) 的位置，有两个正参数 \(a_{i},b_{i}\)，和一个价格 \(p_{i}\)。一个人开始时在 \((r_{1},c_{1})\) 的位置，如果他所在的位置有卡，那么他可以买下来。有一个参数为 \((a,b)\) 的卡时，他可以移动 \((\pm a,\pm b)\) 和 \((\pm b,\pm a)\) 这 \(8\) 种任意的方向。问他最少花多少钱到达 \((0,0)\)。

题解：对于一张卡，如果 \(\frac{a}{\gcd(a,b)}\) 和 \(\frac{b}{\gcd(a,b)}\) 同奇偶，那么可以移动 \((\pm\gcd(a,b),\pm\gcd(a,b))\)，否则可以移动 \((\pm\gcd(a,b),0)\) 和 \((0,\pm\gcd(a,b))\)。有多张卡时也可以类似处理。

设 \(dp[i][\text{flag}]\) 表示当前的 \(\gcd\) 为 \(i\)，情况为 \(\text{flag}\) 时，到 \((0,0)\) 的最小代价。转移时枚举接下来要买哪张卡即可。转移时让 \(\gcd\) 变大或者 \(\text{flag}\) 变坏显然是没有好处的，所以我们控制不进行这样的转移即可去掉后效性。

时间复杂度 \(\mathcal{O}(nA\log A)\)。其中 \(A\) 是所有的 \(a,b\) 中任意子集的不同的 \(\gcd\) 的数量。\(A\) 有一个很显然的上界，就是所有不同的 \(a,b\) 的不同的约数个数。但是这个上界应该也是远远达不到的。

L. Plans, Trains, but not Automobiles

题目大意：给定了一个 \(n\)（\(1\le n\le 10^5\)) 个点，\(m\)（\(0\le m\le 10^5)\) 条有向边的 DAG。问你最少可以被划分为多少条链。并且还要输出，在所有取到最小值的划分方案中，所有可以作为链端点的点。

题解：第一个问题就是求最小链覆盖。我们求二分图匹配即可，出点向入点连边。答案即为点数减去匹配数。复杂度 \(\mathcal{O}(m\sqrt n)\)。

第二个问题，我们考虑一个点可以作为链的起点。那么说明如果我们删掉该点的入点，匹配数不发生改变。同理，如果一个点可以作为链的终点，那么删掉该点的出点，匹配数不发生改变。

对于未盖点，显然可以删掉。如果从一个已盖点出发，可以搜到一条到未盖点的交错路，那么我们可以把交错路上的匹配/未匹配边取反，将这个点变成未盖点。所以我们从每个未盖点出发，走交替路，将已盖点打上答案标记。复杂度 \(\mathcal{O}(n+m)\)。

M. XOR Sequences

题目大意：给你 \(x_{1},\cdots,x_{n}\)，且互不相同，每个都在 \([0,2^{m})\) 之间。对于每个 \(y\in[0,2^{m})\)，都有一个 \(j\) 使得 \(x_{j}\oplus y> x_{i}\oplus y(1\le i\le n, i\neq j)\)。这样我们就得到了一个长为 \(2^{m}\) 的序列 \(\{j\}\)。现在给了你这个长为 \(2^{m}\) 的序列，问有多少种可能的 \(x\)。

题解：\(x_{j}\oplus y>x_{i}\oplus y\)，等价于 \(x_{j}\) 与 \(x_{i}\) 最高的不同位 \(l\) 满足 \(x_{jl}\neq y_{l}\)，也就是说满足要求的所有 \(y\) 是固定了一位，其它位任取的形式。由于 \(x_{j}\oplus y\) 取得最大值可以写成 \(n-1\) 个上面形式的不等式，因此每个 \(x_{j}\) 取得最大值的 \(y\) 是固定了若干位，其它位任取的形式。如果不满足则无解。

注意到对于固定的位，\(x_{j}\) 的值就已经知道了，因此 \(x_{j}\) 可以写成如下的形式：

???0101???0101???...

我们把所有 \(x_{i}\) 的 pattern 找出来，从高位到低位计算方案数。

如果有一个数最高位是 ?，那么这一位所有的 \(x_{i}\) 的值必须一样。否则假设 \(x_{j}\) 的最高位是 ?，而 \(x_{i}\) 的最高位和 \(x_{j}\) 不一样，那么 \(y\) 在最高位就只能和 \(x_{i}\) 相同，那么 \(x_{j}\) 的最高位就会固定而不是 ?。如果所有数最高位都是 ?，01 可以任取，方案数需要乘 \(2\)。

否则，如果所有数的最高位都相同，也是无解的，理由和上一种情况恰好是反过来的（\(y\) 的最高位取值随意，应该是 ?）。

否则，最高位为 \(0\) 和 \(1\) 的两部分之后的位互不干扰，我们分成两块递归去做即可。