Contest Info

practice link

Solutions

A. Gennady and a Card Game

签到题。

B. Petr and a Combination Lock

签到题。

C. Yuhao and a Parenthesis

签到题。

D. Makoto and a Blackboard

签到题。

E. Egor and an RPG game

题目大意：给你一个 \(1\sim n\) 的排列，要求你把它划分成若干个上升或下降子序列，且序列的数量不得超过所有 \(1\sim n\) 的排列（划分成的序列数量的最小值）的最大值。

题解：设 \(k\) 是使得 \(\frac{k(k+1)}{2}\) 不大于 \(n\) 的最大整数，我们构造 \(1,3,2,6,5,4,10,9,8,7,\cdots\) 显然这个排列所需的序列数量至少为 \(k\)。接下来我们构造一个不超过 \(k\) 个序列的划分方案。

• 若该排列的 \(LIS\) 长度大于等于 \(k\)，那么我们把 \(LIS\) 取出，然后递归下去即可。

• 若该排列的 \(LIS\) 长度小于 \(k\)，我们知道每个序列都可被划分为 \(|LIS|\) 个下降子序列，下面我们用两种方法来证明：
  • 将该序列的每个元素和它的下标组成一个 pair，那么 \(LIS\) 显然就是一个最大链，而下降子序列则是一个反链。根据 \(Dilworth\) 定理，我们可以划分出 \(LIS\) 个反链。但是这个证明不能给出构造方案。
  • 我们维护一个下降子序列的 vector，从左到右填入排列中的数。若集合为空或该数比集合中所有下降子序列的最后一个元素都大，那么我们将它作为一个新的下降子序列。否则我们找到所有最后一个元素中最小的比它大的，将它插入这个元素后面。显然所有最后一个元素组成的序列一直是一个上升子序列。按照上述插入的规则，我们很容易归纳证明：对每个 \(i\in[1,vec.size()]\)，都存在一个原序列的上升子序列，使得它的第 \(j\) 个元素属于 \(vec[j]\)，且第 \(i\) 个元素是 \(vec[j]\) 的最后一个元素。根据 \(Dilworth\) 定理，\(vec.size()\) 不小于 \(LIS\) 的长度，因此 \(vec.size()\) 等于 \(LIS\) 的长度。

F. Alex and a TV Show

题目大意：有 \(n\) 个 multiset，要求你维护四种操作：

• 将第 \(x\) 个 set 置为 \(\{v\}\)
• 将第 \(x\) 个 set 置为第 \(y\) 和 \(z\) 个 set 的并
• 将第 \(x\) 个 set 置为 \(\{\gcd(a,b)|a\in set_{y}, b\in set_{z}\}\)
• 询问第 \(x\) 个 set 中 \(v\) 的数量，对 \(2\) 取模

\(n\le10^{5},q\le10^{6},v\le7000\)

题解：容易想到用 bitset 维护。难点在于第三种操作。事实上对于每个 \(i\)，我们维护 \(\sum_{i|j}cnt_{j}\) 即可，这样第三种询问就转化为了对应元素的数量相乘。

G. Vladislav and a Great Legend

题目大意：给你一棵树，对于它的点的非空子集 \(X\)，定义 \(f(X)\) 表示使得 \(X\) 中所有点连通的最小边集的大小。求 \(\sum_{X\subset V,X\neq\emptyset}f^{k}(X)\)。

题解：参考这里的技巧，我们可以把求 \(f^{k}(X)\) 转化求 \(k\) 元组的数量。但是 \(k\) 元组中会有重复元素，处理起来比较麻烦，我们把它做一些变形： \[ \begin{aligned} f^{k}(X)&=\sum_{i=0}^{k}\begin{Bmatrix}k\\i\end{Bmatrix}(f(X))_{i}\\ &=\sum_{i=0}^{k}\begin{Bmatrix}k\\i\end{Bmatrix}{f(X)\choose i}i! \end{aligned} \] 第一个等号不是特别复杂，这里就不赘述了。

因此我们只需要对每个 \(i\in[0,k]\)，求出任意 \(i\) 条不同的边的贡献即可。我们先来研究给定一个边集，\(f(X)\) 要包含它，\(X\) 需要满足什么样的条件。对于每条边 \(u-v\)，不妨设 \(v\) 较深，那么显然 \(X\) 中必须至少包含 \(v\) 的子树中的一个点。如果不存在一条边使得所有边都在它的子树中，那么上述条件已经是充分的；否则这条边的另一侧也必须有至少一个点属于 \(X\)。那么我们可以用 \(dp[u][i]\) 表示考虑 \(u\) 的子树加上它与父亲的边中，选取 \(i\) 条边的方案数，转移时注意把第二种中非法的情况减去即可。

时间复杂度 \(\mathcal{O}(nk+k^{2})\)。第一部分的复杂度证明如下：我们在转移时类似于那种常见的树 \(dp\)，每个子树枚举的范围是 \(k\) 和 \(sz\) 取 \(\min\)。我们考虑树的 \(dfs\) 序，假设 \(A\) 子树和 \(B\) 子树转移，相当于我们取 \(A\) 中 \(dfs\) 序最大的 \(\min\{k,sz\}\) 个，\(B\) 中 \(dfs\) 序最小的 \(\min\{k,sz\}\) 个两两贡献复杂度，并且显然 \(A\) 和 \(B\) 两个子树的 \(dfn\) 是连着的。因此每一对贡献复杂度的点 \(u,v\) 满足 \(|dfn_{u}-dfn_{v}|\le2k\)。那么显然复杂度是 \(\mathcal{O}(nk)\)。如果我们取 \(k=n\)，就用另一种方式证明了常见的树 \(dp\) 复杂度为 \(\mathcal{O}(n^{2})\)。

H. Mateusz and an Infinite Sequence

题目大意：用如下方式构造一个模 \(m\) 意义下的无限序列 \(\{M\}\)：首先给出长度为 \(d\) 的 \(\{M_{1}\}\)。\(\{M_{i}\}\) 则是由 \(d\) 个 \(\{M_{i-1}\}\) 连接起来，但是第 \(i\) 个中的每个元素要加上 \(M_{1i}\) 的偏移量。之后抽出子序列 \(M_{\infty l}\sim M_{\infty r}\) 作为序列 \(A\)，另外给出长度为 \(n\) 的序列 \(B\)。问 \(A\) 中有多少个位置，使得 \(A\) 从该位置起长度为 \(n\) 的子串每个位置都小于 \(B\) 对应的位置。

题解：显然我们把区间询问拆成两个前缀和。我们枚举起始位置 \(x\) 对 \(d\) 的模，那么对于每个除 \(d\) 相同的区间，我们可以将这个区间中的限制全部用第一个位置的限制来表示，这样就把 \(B\) 的长度缩小大约 \(d\) 倍。如果 \(B\) 的长度为 \(1\)，那么就转化成了一个简单的数位 \(dp\)，而且容易发现这个数位 \(dp\) 可以预处理。但是当 \(B\) 长度为 \(2\) 时，如果起始位置模 \(d\) 余 \(d-1\)，那么序列的长度将还是 \(2\)，因此我们还要限制一下位数。

时间复杂度 \(\mathcal{O}(n\log_{d}rd^{2}m)\)。其实感觉复杂度应该还能降。