[luoguP2336] [SCOI2012]喵星球上的点名（后缀数组 + 暴力）传送门原本的想法是把所有的串不管是名字还是询问都连起来，记录一下询问串在sa数组中的位置对于每个询问可以在sa数组中二分出左右边界，第一问用莫队，第二问差分乱搞。结果发现

[BZOJ1594] [Usaco2008 Jan]猜数游戏（二分 + 并查集）传送门

题中重要信息，每堆草的数量都不一样。
可以思考一下，什么情况下才会出现矛盾。
1.如果两个区间的最小值一样，但是这两个区间没有交集，那么就出现矛盾。
2.如果两个区间

[BZOJ4779] [Usaco2017 Open]Bovine Genomics（hash + 二分）传送门网上的题解：枚举左端点，二分右端点位置，最后所有左端点的答案取最小值我的题解。。。二分答案，枚举左端点，看看是否有解。。好像和上面是反的，但是思路没问题过程用hash判重

[luoguP2862] [USACO06JAN]把牛Corral the Cows（二分 + 乱搞）传送门

可以二分边长
然后另开两个数组，把x从小到大排序，把y从小到大排序
枚举x，可以得到正方形的长
枚举y，看看从这个y开始，往上能够到达多少个点，可以用类似队列来搞

其实发

[luoguP1783] 海滩防御（二分 || 最短路 || 最小生成树）传送门

因为答案满足单调性，所以看到这个题，第一反应是二分，但是总是WA，也没有超时。

看了题解，，，，，，

这题刚开始很多人会想到二分，二分答案，然后看看是否能绕过所有信号塔，但是，这样

[HDU3586]Information Disturbing（DP + 二分）传送门

题意：给定一个带权无向树，要切断所有叶子节点和1号节点（总根）的联系，每次切断边的费用不能超过上限limit，问在保证总费用<=m下的最小的limit
二分答案，再 DP，看看最终结果

[luoguP1316] 丢瓶盖（二分答案）传送门

二分答案再判断即可

——代码


1 #include <cstdio>
2 #include <iostream>
3 #include <algorithm>
4 #define max(x, y) ((x) > (y) ? (x) : (y))
5 #def

[luoguP2680] 运输计划（lca + 二分 + 差分）传送门

暴力做法 50 ~ 60
枚举删边，求最大路径长度的最小值。
其中最大路径长度运用到了lca

我们发现，求lca的过程已经不能优化了，那么看看枚举删边的过程能不能优化。
先把

[luoguP2601] [ZJOI2009]对称的正方形（二维Hash + 二分 || Manacher）传送门

很蒙蔽，不知道怎么搞。
网上看题解有说可以哈希+二分搞，也有的人说用Manacher搞，Manacher是什么鬼？以后再学。

对于这个题，可以从矩阵4个角hash一遍，然后枚举矩阵中的点

[POJ3233] Matrix Power Series（矩阵快速幂）传送门

k <= 109 暴力肯定超时
根据矩阵性质，可以发现
S(4) = A1 + A2 + A2* (A1 + A2)
S(5) = A1 + A2 +A2* (A1+ A2) + A5
所以可以递归二分求解，分别判断 Ak，k 为奇数和偶

[luoguP2801] 教主的魔法（二分 + 分块）传送门

以为对于这类问题线段树都能解决，分块比线段树菜，结果培训完才知道线段树是一种特殊的分块方法，有的分块的题线段树不能做，看来分块还是有必要学的。
对于这个题，先分块

数列分段Section II（二分）洛谷传送门
输入时处理出最小的答案和最大的答案，然后二分答案即可。
其余细节看代码


1 #include <iostream>
2 #include <cstdio>
3
4 using namespace std;
5
6