一般来讲，搜索主要分为两条路bfs和dfs，本节主要研究两种方式搜索一些延申及优化。一、DFS -> 剪枝 -> IDDFS void dfs(int s, int t, int depth) { if (s == t && depth <= n) { //输出答案 return; } if (check(s) || depth > n) //剪枝 return; for (int i = 0;;) { //寻找当前节点的子节点，即树的下一层 int new_s = s + i; //新的状态 if (!vis[new_s]) { //记忆化剪枝 vis...

洛谷P1908 https://www.luogu.com.cn/problem/P1908  逆序对常规解法归并排序或者离散化+树状数组（线段树），网上教程很多这里暂且不表，AVL树和红黑树也可以解决，但是略麻烦（比较小众），笔者在这里提供一种新解法——跳表（暂时在网上没看到有发的）。跳表https://oi-wiki.org/ds/skiplist/ 具体可以在这里了解，简略来讲就是可以进行二分查找插入等操作的单调链表，只不过这个链表的结点多了很多层（有点像树了，但实际不是），便于操作。类似这种（网上随便扒的图）思路来源 其实这种思路与树状数组解法或者AVL解法类似，倒序遍历+找比当前数字...

一、ST表（RMQ或RGQ问题等） ST算法处理静态空间的RMQ问题效率相当高，预处理时间复杂度 O(nlogn) ，查询时间复杂度 O(1)。思路同莫队算法类似，同为分块+处理，但是ST完全不支持修改，如果只有查询，ST查询效率远高于莫队。 思路：DP预处理（倍增法）+贪心查询 首先，ST需要分块，通过倍增思路分块。第一组全分为长度为1的块，第二组全分为长度为2的块，第三组长度为4，倍增地以此类推。注意这里的分块每个块之间不是完全互斥的，和归并排序中的分组完全相反，这里的分块是分别以每个元素为头找到长度为2^(组数-1) 的块，只要块的尾没到数组的结尾，就把每个元素都找到这样的块。如此，总共...

整数二分规范 介于二分取左右边界的不确定性和容易陷入死循环的问题，笔者这里自己总结一点学习小技巧先写出未完善二分模板 int fun(int n){ int l=0,r=n; while(l<r){ int mid=(l+r)>>1; if(check(mid)) l=mid;//或者r=mid else r=mid-1;//或者l=mid+1 } return l; }  2.通过题干条件完善check以及后面的mid的转移 check内部根据题干完成，后边根据要求看l=mid还是r=mid，这些完成后else后面的语句自然就完成了。 3.看if或者else后边的语句，根据...

先附链接 正如标题所说，这道题是一道鸽巢原理的题（本蒟蒻做之前还不知道什么是鸽巢原理），对于鸽巢原理，可移至这里了解详细。 鸽巢原理 存在n+1只鸽子进入n个鸽巢，那么必定会有一个鸽巢存在两只鸽子。 存在n只鸽子进入m个鸽巢，那么必定有一个鸽巢存在r只鸽子 r=[(n-1)/m]+1 对于本题呢，我们可以先看hdu1205  该题是非常典型的鸽巢原理问题。 我们将最多的一种糖果想象成鸽巢，将剩余其他糖果总和想象成鸽子，也就转换成了sum-maxa与maxa的问题 令S=sum-maxa，N=maxa S个鸽子在一个队列中，相同的鸽子连续在一起排放，将鸽子顺序塞入鸽巢之中，每个鸽巢可以想象成一个...