在看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)\)。
但是这个比起上面的那个还是逊了一点，因为这个点数上限是强行给的，并不自然。
总之就是，通过强力的剪枝极大缩减状态数，通过把搜索过程细分，每一小步都进行一次剪枝来进一步优化。
由于问题数量太少，极少的状态数看起来还是可遇不可求，这让我们非常难受。如果将来我见到了更多这类题，会来补一下并尝试总结。