【做题记录】搜索

· · 个人记录

做了几道搜索，记一下。

Gym - 100825C. KenKen You Do It?

减和除直接 O(n^2) 枚举即可，对于加和乘考虑搜索，朴素的搜索一位一位枚举即可，剪掉行列中的相同数以及不可能达成目标的状态，但时间还是很紧张。

考虑把搜索过程分为两部分，一部分只搜出每个数各出现多少次，比如设 c_i 表示 i 填的次数。此处不考虑是否真的能填进去，而是凑出 t 来即可。

把一组 c_i 跑出来后，考虑计算其填进格中有多少种不同方式。我们发现 i 的取值已经不重要了，重要的只是有多少相同数出现。所以给 c_i 排个序，计算排序后的次数序列有多少中出现的可能即可。

对于每种出现次数的计算，可以在前面预处理出来，像朴素搜索中一样搜出来，但复杂度大致由 O(m^n) 降至阶乘，因为只考虑出现次数，每次只可能多开一种。把跑出来的所有情况放 map 里，在前面用到时在 map 里查一下即可，这样就跑过了。

CF293B. Distinct Paths

Sol.1 搜索 + 剪枝（同类搜一次）

根据抽屉原理，k 种颜色只能不重复地放到 k 个格子里，若路径上的格子总数 n+m-1 超过了 k，则一定无解。所以数据范围实际上是 n+m-1\le10，考虑搜索。

朴素的搜索也就是开 v_{i,j} 表示以 (i,j) 为右下角，(1,1) 为左上角的矩形内出现过的数，状压存一下就行。每一位先记录下 v_{i,j}=v_{i-1,j}\cup v_{i,j-1}，然后枚举其中没有的一项填上再继续往下搜即可。可以加的剪枝是其中没有的项数不足 (n-i+m-j+1) 时一定无解，但是这样复杂度还是高。

考虑把相同的东西放到一块搜，发现填到 (i,j) 时，所有在已填过的区域和题目规定的限制中均未出现过的数本质上是等价的，也就是不管在这填哪一种，后面接着填的方案数相等。那么第一次出现这样的数就搜下去记一下，后面再出现直接加上标记就行。判断是否是这样的数只需要开个数组记录是否出现过即可。

Sol.2 状压 DP（容易超时）

考虑一格一格填，发现若 (k,l) 填 x 导致后面填 (i,j) 时不能填 x，当且仅当 k\le i 且 l\le j。由于 k\le i 一直满足，重要的就是前面填过的 x 中列数最小的那个 l。所以把 k 种颜色的这个列数在 16 进制下状压，用 map 存一下，每次取出来找 l\le j 的转移一下即可。

这份代码用了一些剪枝，把开头和结尾的颜色剪掉了，剩了 8 个颜色跑，但还是跑不到 1 秒内，不知道是不是我实现的问题。

AT_icpc2012autumn_b. Texas hold 'em

发现从剩余的 45 张牌里选两张的方案数为 \frac{45\times44}{2}=990，每个人从七张牌中选五张的方案数为 \frac{7\times 6}2=28，总共需要处理的牌型有 990\times28\times2=55440 种，所以直接暴力搜出每一种即可。

另外还有一些处理牌型时能注意到的点：

因此想到如果能把每种牌型都压成一个数，会更方便比较。所以代码中把牌的类型作为高位，其他关键字依次作为低位压成了一个数。而且这里只需要保证同种类型的牌型处理时位置对齐即可，不同类型之间已经由于最高位不同分出大小了。

另外可以用函数判断区间相等，用函数把关键字压成一个数等，可以简化代码。

CF525D. Arthur and Walls

从宏观看到微观，发现只要是矩形，在 2\times 2 的格子里就一定会有 0,1,2,4 个点，反之若有三个点，则另一个必须也变成点才能形成矩形。因此初始把本来是三个点的位置放到队列里，BFS 搜索，每次修改后再判断修改处有关的四个 2\times 2 区域是否变为三个点，再放到队列里一直处理，直到队列空为止，此时一定恰好全部变为矩形。

由于每个 2\times2 区域最多被找到四次，时间复杂度 O(4nm)。