Contest Info

date: 2019.02.18 09:30-14:30

practice link

Solutions

A. Apples

签到题。

B. Brains Eating

题目大意：给你一个有向图，\(n\le20\)，每条边上有一个字母，另外给出字符串 \(s,t\)，\(|s|\le10,|t|\le50\)。现在从 \(1\) 出发，每次等概率随机选一条边走，如果当前走出的字符串包含 \(s\) 为子串，或包含 \(t\) 为子序列，那么游戏结束。问期望走多少步。

题解：比较经典的高消题，但是直接做的复杂度为 \(\mathcal{O}(n^{3}|s|^{3}|t|^{3})\)，显然是不行的。注意到 \(t\) 这一维每次要么 \(+1\)，要么不变，因此我们可以倒着 \(dp\) \(t\) 这一维，剩下两维高消。

时间复杂度 \(\mathcal{O}(|t|n^{3}|s|^{3})\)。

C. Classical Problem

题目大意：二维平面上有\(n\le2000\)个点，求最小的非零三角形面积。

题解：动态维护法向量偏序，\(O(n^2\log{n})\)，常数有点大，需要卡时间输出。

G. Gapless Filling with Tetrominoes

题目大意：问有多少种方案可以用俄罗斯方块密铺一个\(n\times4\)的棋盘，\(n\le10^9\).

题解：记录三行的状态，稍微限制一下不合法的状态，剩下的状态不超过\(100\)，直接矩阵乘法快速幂。

H. Hand-made Cube

题目大意：给了你 \(8\) 个 \(1\times1\times1\) 的立方体的平面展开图，问你能否拼成一个 \(2\times2\times2\) 的大立方体，使得内部的小正方体的面都为黑色，外面的每个大正方体的面同色，且每个面互不相同。

题解：主要难点在于从平面展开图构建出立方体。我们先给每个面编号，打表记录每个面的邻面的编号。折叠平面展开图时，我们直接从某个面开始 dfs，搜索时记录一下我们折叠的方向，即可完全还原这个立方体。

I. Inverse LCP Problem

题目大意：给定一个小写字母串\(s\)，\(|s|\le2\times10^5\)。然后\(q\)次询问，每次给出一个整数\(k\)，求一对前缀\(i\)和\(j\)，他们的lcp长度恰好为\(k\)，如果有多组解，首先令lcp的字典序最小，然后令二元组\((i,j)\)最小。

题解：建立后缀树，显然只有后缀树上的节点可能是lcp，然后维护一下子树最小值和与其不在一个子树的次小值即可。

K. Killer

题目大意：这个题面有毒叭。。。我把转换了 \(+\infty\) 层的题意描述一下：给出 \(n\le10^{4}\) 和 \(k\le n\)，我们把 \(1\sim2n\) 按某种顺序连成一个长为 \(2n\) 的有向环，问 \(1\to2,3\to4,\cdots,2n-1\to2n\) 中，恰好有 \(k\) 条边存在的方案数。不取模。

题解：容斥部分不难。设 \(f_{i}\) 表示长度为 \(i\) 的有向环的数量，显然有 \(f_{i}=(i-1)!\)。那么答案即为 \[ \sum_{i=0}^{n-k}(-1)^{i}{k+i\choose i}\left(2^{k+i}{n\choose k+i}f_{2n-k-i}\right) \] 实现时需要特别注意，如果在循环中使用了大整数乘除法，那么效率肯定是很低的。不过稍微推一下，可以发现这个式子的组合数及阶乘都可以写成递推式，这样就只需要乘除小整数了。