Contest Info

date: 2018.12.06 19:38-24:38

practice link

Solutions

A. Product

签到题。

D. Error in code

签到题。

E. Birthday

题目大意：把一个 \(n\leq 2000\) 的无向图的点集划分成 \(k\) 个非空集合 \(S_1,S_2,\dots,S_k\)，使得对于 \(\forall\) 边，它要么在一个点集中，要么连接两个相邻的点集 \(S_i\) 和 \(S_{i+1}(i<k)\)。

题解：

对于每个连通块，找一个点，到其它点的最短路中最长的最大，将连通块中的点按到这个点的最短路距离划分就是能划分出的最多集合。

没有找到好的性质来找这样的点，于是就枚举\(n\)个起点做bfs，因为是稠密图，所以每次的时间复杂度为\(O(n^2)\).

考虑用bitset来加速，把邻接矩阵和未访问的点都用bitset维护，每次扩展的时候，将邻接向量和未访问点与一下，取出其中所有的\(1\)入队。

这样每次bfs，每个点在入队前会贡献\(32\)的枚举复杂度，入队后会贡献\(n/32\)的枚举复杂度，总的时间复杂度为\(O(n^2/32)\).

总的时间复杂度为\(O(n^3/32)\)，可以通过全部数据。

J. Office

简单贪心。

K. Recursive circuit

题目大意：一个电路有 \(k\) 个端口。电路是嵌套定义的，定义一个电路的时候，给出 \(n\) 个点，和 \(s\) 个子模块，\(1\sim k\) 号点为该电路的端口，\(tk+j\) 是第 \(t\) 个子模块的第 \(j\) 个端口。\(k(s+1)\leq n\)。再给出这 \(n\) 个点的 \(m\) 条边。现在给出 \(q\) 次询问，每次问电路的两个端口 \(a,b(a,b\leq k)\)，问它们是否连通，如果连通，连通路径最少进入几层嵌套。

题解:

给每条边一个时间，初始的边的时间为\(0\)，之后按时间添加边，每次合并两个集合的时候，如果这两个集合中分别存在最外层的点，则任意选择一对，添加\(s\)条第二层的边，时间为当前的边的时间加一。

最多发生\(k-1\)次包含两个第一层节点的集合的合并，总共发生最多\(n-1\)次集合的合并，因此这一部分的时间复杂度为\(O(m+k(s+1))\)。

将合并过程加点建树，则问题转化为求两个点的lca，时间复杂度\(O((n+q)\log{n})\)。

L. Subsequences

题目大意：定义一个小写字母串是好的，当且仅当它的本质不同子序列个数有偶数个。给你 \(n\leq 20\) 个字符串，总长度不超过 \(10^5\)，问有多少种排列，使得它们拼成的串是好的。

题解：首先考虑求本质不同子序列的数量。

我们可以写出一个经典的 \(dp\) 方程：\(dp[i][c]\) 表示前 \(i\) 个字符中，以字符 \(c\) 结尾的本质不同子序列有多少个，那么转移方程为：

\[ dp[0][\text{a}]=\cdots=dp[0][\text{z}]=0, dp[0][\varepsilon]=1 \]

\[ dp[i][c]= \begin{cases} &dp[i-1][c]&(c\neq s[i])\\ &dp[i-1][\varepsilon]+\sum_{j=\text{a}}^{\text{z}}dp[i-1][j]&(c=s[i]) \end{cases} \]

容易证明，\(dp[i]\) 中除了 \(dp[i][\varepsilon]\) 恒为 \(1\)，至多只有一个为奇数。因此我们可以用一个大小为 \(27\) 的状态来记录 \(dp\) 的奇偶性。

外层也是一个经典的 \(dp\)，不再赘述。注意需要预处理内层的转移，否则复杂度要乘上串长。

时间复杂度 \(\mathcal{O}(2^{n}n|\Sigma|+|\Sigma|\cdot\sum{|s_{i}|})\)