Contest Info

date: 2019.05.15 10:30-15:30

practice link

Solutions

A. Angle Beats

题目大意：

给出一个\(2\le n\le100\)行\(2\le m\le100\)列的网格，每个格子要么是一个+，要么是一个*，要么是一个.。可以不重叠地放置一些\(I\)形或\(L\)形的由\(3\)个连通的格子组成的骨牌，要求\(I\)形的中心格子必须是+，另外两个格子必须是.，\(L\)形的中心格子必须是*或+，另外两个格子必须是.。问最多可以放下多少块骨牌，输出方案。

题解：相当于是一个二分图的\(V\)形最大匹配问题，*和+是左部顶点，.是右部顶点，*和+向其邻居的.连边，*要同时匹配其水平和竖直方向各一个邻居.，+要同时匹配其任意两个邻居.。拆点转化为一般图最大匹配问题：*拆成两个点，其中一个向水平方向的邻居.连边，另一个向竖直方向的邻居.连边；+成两个点，两个点都向其所有邻居.连边；同一个点拆成的两个点连一条边。对于原图中的*和+只有拆出来两个点都有不同的匹配点时贡献答案。带花树算法在一般图上的上界是\(O(n^3)\)，但这个建模应该有更低的上界，可以通过。

B. Best Subsequence

题目大意：给你一个长度为 \(n\) 的正整数序列 \(w\)，对于一个长度为 \(k\) 的子序列，定义价值为 \(\max(w_{i_{1}}+w_{i_{2}},w_{i_{2}}+w_{i_{3}},\cdots,w_{i_{k}}+w_{i_{1}})\)，求最小价值。

题解：显然二分。设二分到的值为 \(\text{mid}\)，我们需要判断是否能够找出一个子序列使得每相邻两项之和不大于 \(\text{mid}\)。我们称大于 \(\frac{\text{mid}}{2}\) 的元素为大的，小于等于 \(\frac{\text{mid}}{2}\) 的元素为小的。

先把大于 \(\text{mid}\) 的元素去掉。假设所有元素都是小的，那么显然随便找 \(k\) 个就行了。如果所有元素都是大的，那么最多只能取一个元素。否则我们将序列旋转一下（这显然是不影响答案的，因为题意就是一个环），使得第一个元素是大的，最后一个元素是小的。注意到每一段连续的大元素至多只能取 \(1\) 个，并且显然会取其中最小的，这样可以认为每一段大的都只有一个。

现在我们贪心地解决这个问题，首先选取所有的小元素，然后对于每个大元素，如果它加入进来和左右两边的小元素满足要求，就加入它；否则的话，为了满足要求，我们至少要删掉一个小元素，那答案就不会更优，不如不加。当然加到 \(k\) 个的时候就可以停了。

时间复杂度 \(\mathcal{O}(n\log(\max w))\)。

C. Cool Pairs

签到题。

E. Expected Value

题目大意：给你一个连通平面图，开始在 \(1\)。每次等概率随机走到一个邻点，问第一次走到 \(n\) 的期望次数。

题解：由于可以用矩阵递推，考虑用 BM 求解。由于平面图满足 \(E\le3V-6(V\ge3)\)，因此这部分的复杂度为 \(\mathcal{O}(V^{2})\)。

假设 \(P(x)=\sum_{i=0}^{+\infty}p_{i}x^{i}\)，\(Q(x)\) 为递推式，设 \(R(x)=P(x)Q(x)\)，显然 \(R(x)\) 只有前 \(V\) 项不为 \(0\)。我们所求即为 \[ \begin{aligned} &P'(1)\\ =&(\frac{R}{Q})'(1)\\ =&\frac{R'(1)Q(1)-R(1)Q'(1)}{Q^{2}(1)} \end{aligned} \] 这部分的时间复杂度也为 \(\mathcal{O}(V^{2})\)，用 FFT 可以加速到 \(\mathcal{O}(V\log V)\)。

时间复杂度 \(\mathcal{O}(V^{2})\)。

I. Interesting Graph

题目大意：给你一个无向图，对于任意一个 \(7\) 个点的集合 \(A\)，都存在两个点 \(a,b\in A\)，及一个 \(c\not\in A\)，使得任何一条 \(a\) 到 \(b\) 的路径都经过 \(c\)。分别求用 \(1\sim n\) 种颜色给图染色的方案数。

题解：该条件等价于任何一个联通块的大小不超过 \(6\)。假如存在一个大于等于 \(7\) 个点的连通块，那么我们一定能找到一个它大小为 \(7\) 的连通子集，这个子集显然是不满足要求的。而如果不存在大于等于 \(7\) 个点的连通块，那么 \(A\) 一定不连通，只要让 \(a,b\) 是两个不同的连通块中的点即可。

显然我们只要对每个连通块求答案，然后再乘起来即可。对于一个大小为 \(k\) 的连通块，我们可以用一个显然的状压 \(dp\) 求出它用 \(1\sim k\) 种颜色染色的方案数，而可以归纳地证明，一个大小为 \(k\) 的图的色数多项式的次数一定是 \(k\)。因此我们可以插值求出它的色数多项式（还需要一个 \(F(0)=0\)），然后对于 \(1\sim n\) 的每个值暴力计算即可。

当然我们不能算出所有的色数多项式在 \(1\sim n\) 的值，这样复杂度就变成 \(\mathcal{O}(n^{2})\) 了。但是显然这些多项式会有很多相同的，打表可知至多只有 \(73\) 种，对于同一种快速幂即可。

K. Knowledge

题目大意：定义两个串相等，当且仅当其中一个串经过如下操作可以变成另一个串：

• 在某个位置加上 aa，bbb 或 ababab
• 从某个位置删去 aa，bbb 或 ababab

给出一个串，求所有长度为 \(x\)，且与该串相等的串的数量。

题解：与 KMP 上 \(dp\) 的思想类似，我们可以先找出等价类，然后求出（爆搜出）等价类之间的转移关系，然后矩乘就好。

当然我们不可能爆搜无限的长度，因此需要给爆搜定一个长度上界，我定的是 \(12\)。求所有等价类是这样的，从空串开始，分别在后面添加 a 或者 b，如果它们和已有的串都不在一个等价类中，那么就将它作为一个新的等价类。求转移也是类似的道理。

最后会找到 \(12\) 个等价类。题解说是一个正四面体群，但是不知道也没关系。