Sam的打字计划 - 题解

T4 Sam的打字计划 - 题解

一看数据就知道可以搜，但是暴力搜索有 $O(9^9)$ 直接 $TLE$ 了。

但是这道题是没有办法进行剪枝或者优化的，那么其实虽然是搜索，但本质是枚举。

枚举所有方案有个优化，叫折半搜索，标准的空间换时间的思路。

先枚举前 $5$ 个数字会导致的所有局面，再枚举后 $5$ 个数字会导致的所有局面。

上下匹配就可以将复杂度降低到 $O(2\times9^5)$。

当然这道题还有第二种做法：

将这个 $5\times4$ 的方格分成 $13$ 个区块：

1
2
3
4
5

1  2  2  3
4  .  .  5
6  7  7  8
9  .  .  10
11 12 12 13

每个区块的覆盖次数为 $a[i]$。

不难发现 $a[13]$ 所有数字都会用，而 $a[1]$ 只有 $1$ 不会用，所以 $cnt[1]=a[13]-a[1]$。

同理：

• $a[6]$ 只有 $1,7$ 不用，那么 $a[6]=a[13]-cnt[1]-cnt[7]$，即 $cnt[7]=a[13]-a[6]-cnt[1]$。
• $a[2]$ 只有 $1,4$ 不用，那么 $a[2]=a[13]-cnt[1]-cnt[4]$，即 $cnt[4]=a[13]-a[2]-cnt[1]$。
• $a[10]$ 只有 $2$ 不用，那么 $a[10]=a[13]-cnt[2]$，即 $cnt[2]=a[13]-a[10]$。
• $a[4]$ 只有 $1,2,3,7$ 不用，那么 $a[4]=a[13]-cnt[1]-cnt[2]-cnt[3]-cnt[7]$，解得 $cnt[3]$。
• $a[7]$ 只有 $1,7,0$ 不用，解得 $cnt[0]$。

综上，$cnt[1],cnt[2],cnt[3],cnt[4],cnt[7],cnt[0]$ 可以直接算出。接下来只需要计算 $5,6,8,9$。

又因为 $cnt[5]+cnt[6]+cnt[8]+cnt[9]=a[13]-cnt[1]-cnt[2]-cnt[3]-cnt[4]-cnt[7]-cnt[0]$，设为 $z$，所以我们现在有三个方程四个未知数。

要让 $cnt[5]$ 最小，则最大化 $cnt[6]$，而 $cnt[6]=x+y-z+cnt[9]$，则 $\max\{cnt[6]\}=\min(9,\min(x+y-z+9,min(x,y)))$。

再利用之前的 $x,y,z$ 可解得所有数字的个数。