XIX Open Cup named after E.V. Pankratiev. Grand Prix of America, Division 1

Contest Info

date: 2019.03.19 16:14-21:14

practice link

Solutions

A. Piece of Cake

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

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

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

签到题。

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|)\)

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\) 的两部分之后的位互不干扰,我们分成两块递归去做即可。