爆搜的胜利

/se

Posted by ShanLunjiaJian's Blog on January 11, 2022

在看Itst的OI Memory,然后看到了 https://zhuanlan.zhihu.com/p/56269536 。

下面这个题确实把我吓到了。然后我就把这个blog看完了,感觉上非常牛逼。


给一个序列,求所有子序列中权值和第\(k\)小的。\(n\leq 10^5,a_i\leq 10^9,k\leq 10^6\)。

考虑二分答案\(d\),然后问题变成统计有多少个子序列权值和\(\leq d\)。

背包失败了,因为值域很大。

这里有一个极好的性质,也就是\(k\leq 10^6\)。如果我们每次操作都伴随着权值和\(\leq d\)的子序列个数的增加,那么只需要\(k\)次操作。

于是考虑爆搜,我们维护当前的和,如果这个和\(>d\)那就返回,否则个数\(+1\)继续递归。呃但是这里有一点问题,注意到如果当前这个数没选,那么个数就不会\(+1\),所以如果这个数不能选,我们继续递归的复杂度就假了。考虑把所有数从小到大排序,那么如果这个数不能选,后面都不能选了,于是就结束了。复杂度是\(O((n+k)\log v)\),这里看起来\(k\)比\(n\)要高阶。

这个问题也有经典的扩展做法,我们开一个堆维护若干个子序列,每次拿出最小的,然后用它扩展,扩展方法是选择子序列外面最小的,或者选择把上一个选择的换成刚好比这个大的,这可以用可持久化堆轻松搞定。复杂度是一样的。


于是有一个k短路的简单俩\(\log\)做法。

我们二分答案\(d\),然后统计有多少长度\(\leq d\)的路径,方法是从\(t\)建最短路树,从\(s\)出发dfs,按走完之后最短路从小到大的顺序枚举下一条边,够了\(k\)就返回,超了\(d\)也返回。

但是这个可能会死,因为我们走下一条边这个事情并不可靠,我们可能会让每个方案都沿着最短路树上的一条长链走一遍,这样复杂度就\(nk\log\)了。

考虑一个牛逼做法,我们直接跳到下一个有出边,并且走完这个出边的最短路足够短以至于可以让路径数\(+1\)。可以用倍增搞定这个事情。

但是k短路的可持久化堆是一个\(\log\)的,所以这个方法可能不够强。


二分图k小权匹配

\(n\leq 20,m\leq 100,k\leq 10^5,v\leq 1000\),不要求极大匹配。

这个咋做?简单想法是跑出最小权匹配,然后通过某种交换或者退流-推流来扩展,但是这个很复杂。

此时爆搜变得非常简单。我们二分完了开始搜就行了,复杂度是\(O(mk\log v)\)。


还有别的一类爆搜,这个更接近ad-hoc,是给出剪枝极强的爆搜然后分析复杂度。

XVII Open Cup, GP of Romania B. Entanglement

给一个\(n\times m\)的矩阵和常数\(k\),求有多少对长\(n,m\),值域都在\([1,k]\)的序列\(a,b\),满足矩阵中每个位置\((i,j)\),和\(a_i,b_j\)中至少一个相等。\(n,m\leq 300\)。

考虑直接搜,考虑先确定\(a_1\),如果它不等于第一行的某个数\(j\),那么\(b_j\)必须是这个数。至于\(a_2\),如果它不等于第二行的某个数\(j\),并且\(b_j\)还没确定,那么\(b_j\)必须是这个数,否则要么不合法要么不用管。

考虑怎么求这个东西的复杂度,它是\(T(n,m)=T(n-1,0)+\sum_{x}T(n-1,c(x))+O(nm)\),其中\(c(x)\)是\(x\)在这一行的出现次数,\(nm\)是我们确定一列之后需要把已经合法的标记上。

我们归纳证明这个复杂度不超过\(n^2m\)。因为\(c\)的总和是\(O(m)\),所以递归树上每一层\(m\)的总和是不变的,一共有\(n\)层,所以总共就是\(O(n^2m)\)。

上网搜一搜,你会发现Claris的blog上这个题留坑了(


这个是一类分析搜索树的技巧。当你无计可施的时候,可以考虑一个爆搜,然后给极强的剪枝,然后对搜索树进行分析。

但是这几乎可以算是ad-hoc了,因为这些问题看不出任何性质。


好像是奇怪的区域赛题,可以在nowcoder看到 https://ac.nowcoder.com/acm/problem/124582 。然而我没有nowcoder号¿

转化之后据说是,求一个\(512\)个点的图的最小点覆盖,如果点数超过\(\lg n=8\)直接输出-1。

然而爆力不行,因为\(\binom{512}{8}\)是1e17级别。

考虑我们把决策的过程强行细分,依次考虑每一条边,如果有端点选了那就赢麻了,否则枚举选哪个端点递归下去。这样每一步的决策是二选一,而不是\(n\)选一,看起来要好一些。

然后这样做复杂度居然是多项式级别的。考虑每个状态只会经历\(\lg n\)次决策,并消耗\(n^2\)的算量,问题是最终状态数。

一个很牛逼的事情是,状态数是\(O(n)\)的。因为每个状态只会经历\(\lg n\)次决策,而每次决策只能产生两个分支,忽略掉不进行决策的点(也就是把直链缩成一条边),这玩意显然是一个满二叉树的一部分,高度是\(\lg n\),于是状态数就是\(O(n)\)。

最后的优化也很简单,只需要在边数超过\(n\lg n\)的时候直接-1就彳亍了。总复杂度是\(O(n^2\log n)\)。

但是这个比起上面的那个还是逊了一点,因为这个点数上限是强行给的,并不自然。


总之就是,通过强力的剪枝极大缩减状态数,通过把搜索过程细分,每一小步都进行一次剪枝来进一步优化。

由于问题数量太少,极少的状态数看起来还是可遇不可求,这让我们非常难受。如果将来我见到了更多这类题,会来补一下并尝试总结。