Solution

A. Broken Audio Signal

签到题。

B. Restore Calculation

题目大意：给你三个长度相等的整数 \(A,B,C\)，其中有些位置被擦掉了，需要填入 0-9 中的一个数字，不能有前导 \(0\)，求满足 \(A+B=C\) 的填法数量。

题解：设 \(dp[i][0/1]\) 表示后 \(i\) 位已经填好，向第 \(i+1\) 位产生/不产生进位的方案数，答案即为 \(dp[n][0]\)。转移很简单就不写了，注意前导 \(0\) 即可。

C. SIRO Challenge

题目大意：

有一个\(n\le300\)个点，\(m\le5000\)条边的无向连通图，其中有\(l\le16\)个关键点，第\(i\)个关键点有一家拉面馆，在这里吃一碗拉面需要花费\(e_i\)的时间，现在要从\(s\)点出发（\(s\)不是关键点），在\(t\)秒内回到\(s\)点，问最多可以品尝多少不同拉面馆的拉面。

题解：

先floyd求出任意两点之间的最短路径，再状压dp品尝了哪些拉面即可。

D. Everlasting One

题目大意：一个游戏中的角色有 \(n\) 种属性，每种属性可以取暗和亮两种值，因此共有 \(2^{n}\) 种属性。另外给出一个 \(n\) 个点的无向图。定义两个角色 \(A\) 和 \(B\) 本质相同，当且仅当：

• 存在两种属性 \(a\) 和 \(b\)，满足 \(A\) 的 \(a\) 和 \(B\) 的 \(b\) 均为亮的，且 \(a\) 和 \(b\) 在给出的无向图中连通。
• 对于全部 \(n\) 种属性，\(A\) 和 \(B\) 不能同时是亮的。

求本质不同的角色数量。

题解：如果无向图中没有边，显然所有角色都本质不同，答案为 \(2^{n}\)。

否则，假设每个连通块内的点都同为亮或同为暗，那么显然所有这样的角色都不能与任何其它角色本质相同，这里有 \(2^{连通块数量}\) 个本质不同的角色。容易证明其余的所有角色本质相同（易将它们转移到同一种角色），因此答案为 \(2^{连通块数量}+1\)。

E. Putter

题解：给出一个凸包和它内的一个点，现在将这个点以某个角度发射出去，每当它碰到一条边时就会反弹。问有多少种边的排列，使得该点存在一个出射角度，在该角度下点恰好按照该排列的顺序撞击每条边各一次，且不撞到顶点上。

题解：枚举边的排列，模拟点撞击边的过程，点的反弹可以看做将多边形关于该条边做镜面对称。每次撞击可以得到一个出射角度的区间，将这些区间求交即可。

F. Shipura

题目大意：给出一个含有S<>操作和>>操作的表达式，求值。

题解：为了区别S<>的>和>>的>，我们先扫一遍，把数字前面的>>替换为其他符号即可。

G. Floating Islands

题目大意：

有一个\(n\le4000\)的无向完全图，每个点有一个坐标\(p_i\)，任意两点之间的边的长度为\(|p_i-p_j|\)，给每个点一个度数限制\(1\le d_i \le n\)，求每个点不超过度数限制的最小生成树，无解输出-1。

题解：

将点分为\(d_i>1​\)和\(d_i=1​\)两种，对于\(d_i>1\)的点，显然不能依靠\(d_i=1\)的点来连通，这一部分最优的连边方式为按\(p_i\)大小串成一条链。

接着考虑将\(d_i=1\)的点挂到链上，注意到一定是按\(p_i\)的顺序往上挂，否则交换两个一定不会更差。

令\(dp[i][j]\)表示链上前\(i\)个点一共挂了\(j\)个点的最优值，可以滑动窗口优化到\(O(n^2)\).

std solution:

费用流来求解上述的 dp 问题，\(d_i > 1\) 和 \(d_i=1\) 的两种点分为两层，连边。为了优化复杂度，可以在第一层的相邻两两点之间连边。

H. Venn Diagram

题目大意：给你一个维恩图，要求你将它画出来，使得表示每个部分的图形的面积恰等于集合的大小。其中全集 \(U\) 是一个 \(W\times H\) 的矩形，集合 \(A\) 和 \(B\) 分别是一个圆。

题解：

解法一：将较大的圆放在右上角，如果放不下则无解。由于 \(AB\) 的大小已知，因此两圆的圆心距是固定的，也就是说小圆圆心的轨迹是一个圆。我们将矩形各边向内缩 \(r_{小}\)，如果得到的新矩形与小圆圆心的轨迹相交，那么就有解，否则无解。

解法二（题解）：将较大的圆放在左下角，较小的圆放在右上角，如果放不下则无解。此时两圆交的面积达到最小值，如果 \(|A\cap B|<S_{交}\)，那么无解。否则我们将小圆的圆心向大圆不断移动，中间必然有一个位置满足要求。这个位置可以二分求解。

I. Overwriting Game

题目大意：

有一个\(h\times w\)（\(1\le h,w\le5\)）的网格，每个格子为黑色或者白色。

每次操作随机选择一个点\((i,j)\)和一个颜色\(c\)，将\((1,1)\)到\((i,j)\)的子矩阵都染色成\(c\)，花费代价为\(i\times j\).

给定初始局面与目标局面，求期望代价和为多少。

题解：

对于一个中间局面，如果点\((i,j)\)的颜色与目标局面不同，那么\((1,1)\)到\((i,j)\)子矩阵中其它格子的颜色都无关紧要，因为要变成目标局面必须要先重新染色。

搜出所有这些重要的不同位置的轮廓线，对于\(5\times5\)时，\(maxS=252\).

用这些状态进行高斯消元即可。

搜索状态的时候可以搜关于行的单调递减数列。

J. Magical Switches

题目大意：求 \(\bigwedge_{i=1}^m((x_{00}\wedge x_{01})\vee(x_{10}\wedge x_{11})\vee(x_{20}\wedge x_{21}))\)，其中 \(x_{ij}=y_k\) 或者 \(x_{ij}=!y_k\) 。找一组可行解。

题解：显然如果存在数据使得 \(x_{i0}=x_{i1}(i\in [0, 3))\)，那么问题变成一个 3-sat 问题，没有多项式解法。注意到 \((x_{00}\wedge x_{01})\vee(x_{10}\wedge x_{11})\vee(x_{20}\wedge x_{21})=\bigwedge_{i,j, k\in[0, 2)}x_{0i}\vee x_{1j} \vee x_{2k}\)，转换为标准的 3-sat 问题。我们直接搜索即可。