Day1
枚举和搜索
某些题的正解其实就是暴力，但加了一些优化
三连击：暴力枚举即可
DNA序列： \(O(nk)\) 做法可以直接过；因为字符集大小只有 \(4\)，也可以使用哈希转为四进制统计 \(O(n)\)
栅栏：二分答案+搜索+剪枝
k短路：
A*：启发式搜索的一种，定义起点 \(s\)，终点 \(t\)，从起点（初始状态）开始的距离函数 \(g(x)\)，到终点（最终状态）的距离函数 \(h(x)\)，以及每个点的估价函数 \(f(x)=g(x)+h(x)\)。
\(k\) 短路的前置：设 \(g(i)\) 为到达某点已经付出的代价，\(g(i)\) 为该点到终点的估计代价,则估价函数则为两者之和，放入优先队列中，将会先处理估计总代价最小的状态，以取得 \(k\) 短路。
实现（求 \(s\) 到 \(e\) 的第 \(k\) 短路）：首先考虑怎么求 \(h(i)\)，即预处理出图中每个点到终点 \(e\) 的估计代价（最短路径），我们都会求单起点多终点的最短路，多起点单终点的最短路可以转化为单起点多终点的最短路，只需要建一张反向图跑一遍最短路即可。得到反向图中的 \(dist(i)\) 即原图中的 \(h(i)\)。
下面是bfs部分，也就是 A* 的主体：用一个结构体（三元组）记录搜索的三个状态 {\(to,g(i),f(i)\)}，根据估价函数的定义，重载运算符时应把 \(f(i)\) 作为第一关键字、\(g(i)\) 作为第二关键字从小到大入队（小根堆）或从大到小入队（大根堆）。以类似bfs的方法，从起点 \(s\) 开始搜索，以优先队列作为搜索队列。维护一个值 \(cnt\) 表示算出了起点到终点的第 \(cnt\) 短路，每当搜索到一次 \(e\) 点，就表明找到了一条最短路，更新 \(cnt\)，当 \(cnt=k\) 时说明已经求出了第 \(k\) 短路，停止循环。
若在队列为空前均没有返回，说明不存在第 \(k\) 短路
水壶：进行多源 BFS，处理出每一个城市的管辖范围，接着求城市间的最小生成树，然后查询路径最大值。
骑士精神：A* 或 IDA*，也可以暴力搜索+剪枝。
分治：
分而治之
把一个问题分为两个或多个相似的子问题，再把每个子问题分为更小的子问题，直到分出的子问题可以简单地求解。
三维偏序：
前置知识：二维数点->定义：在一个平面中有若干个点，每次询问给你一个矩形，求出在矩形内的点的数量。做法：将点和矩形记录下来按 \(x\) 轴排序，然后用树状数组离线处理。
解决三维偏序可以用CDQ分治+树状数组
序列：dp+三维数点
三元上升子序列：
二分
割绳子：实数域上二分，用一个 check 计算按照长度 \(mid\) 切的绳子条数并和k比较，小了就更新r，大了就更新l
跳石头：原则是能保留就保留，二分答案求最大的最小值，check 函数算 \(mid\) 距离需要移动多少石头，再跟m比较进行调整
汽车拉力比赛：二分答案+人类智慧dfs/bfs。
包裹快递： 实数域二分答案+简单模拟，check 中算时间 \(<x_i\) 则更新 \(>y_i\) 则说明不可行，然后更新
自学：如果 \(b_i>a_i\) 那就完全自学，否则分类讨论：如果上课就能达到锁定 \(mid\) 那就全用来上课，否则先计算上课剩下自学，并统计学习的时间，跟 \(n \times m\) 比较并更新
拯救小云公主：不会
贪心
合并果子：直接用堆每次取最小值和次小值合并即可
最大乘积：用小学奥数的结论（一个数分成 \(2\) 和 \(3\) 的乘积可以保证分成的数最多）拆分，高精度求乘积
关押罪犯：好题，考虑二分答案最小的最大值，把边权大于 \(mid\) 的边“建成”一个无向图并判断他是否为二分图（染色法），并对 \(l,r\) 做出更新。
标签：二分,cnt,终点,NOIP,短路,笔记,寒假,搜索,起点 From： https://www.cnblogs.com/FinderHT/p/18004013