杂题 - 深搜专题杂题选讲

ExFish · 2025-01-21 20:04:53 · 算法·理论

题意：简单的数独，随便写都能过。

题解：深搜。

我们使用 row,col,blk 分别记录行，列，宫格的占用情况。

~~别问为什么我英文错了~~

注意单坐标 r,c,b 数值的维护。

然后用 inNum 记录不用枚举的情况。

对于记录的情况看代码。

~~别问为什么这个代码能通过，问就是远古评测机。~~

加强。

别看此为远古题，反正我过了。

我就稍稍改了下代码，超时了？？？？

~~-- 没救了。~~

好我们要优化。

优化！

考虑先访问 0 少的行，再访问 0 多的行。

然后过了。

太难了，我做了两天。

你们看着做吧，想水道黑的看这里。

代码放着，你们按需截图。

什么？是折半搜索？

算了我们最后一题再来讲这个。

~~不好笑 \sout{\mathcal O(3^n)} 不超时。~~

这题没什么技术含量。

我们先把 a 从大到小排序。

~~我是不会告诉你我没有用这个炸了好几次。。。。。。~~

接着，把你能想到的一大坨剪枝加上去就过了？？？

出数位 dp 那咋了。

直接上题解。

搜一次 2^n，搜两次 2\times 2^{\frac{n}{2}}，不就过了吗。

对着代码讲讲。