书上有些好题，经典套路，全部看看不过来，选择性记录一下，打星号*是自己认为的重点
0x00
例题
最短Hamilton路径 状压dp，主要注意阶段递推问题
*NOI2014 起床困难综合症 位运算相关题目常用的:各位分离，贪心高位往低填
货仓选址 典中典，一个最小化绝对值和式的问题，选中位数
七夕祭 行列分开，接下来同习题中的糖果传递问题
奇数码问题 有解判定:目标状态和起始状态分别写成一行(空格当0)，逆序对数奇偶性相同
*NOIP2012提高组 国王游戏 邻项交换经典题，按左右手乘积排序
习题
袭击 平面最近点对，标算是1log分治，这题卡了我2log所以摆烂用究极人类智慧大法了(随机旋转，按x*y排序，根据数学直觉，最近点对不会挨得太远，取50为区间长，一个区间一个区间地更新答案)
*糖果传递 一眼费用流 环形的“均分纸牌”问题，分析详见提交记录
0x10
例题
*直方图中最大的矩形 单调栈经典题目，做法也很经典，维护高度单调，栈内存每个子矩形的长宽。这个做法其实还挺广，与子矩形/子矩阵有关题目可以考虑使用单调栈(有的题要做一遍“下缀和”转化为直方图，例如习题里的城市游戏优化遍历每个子矩阵。做法来源于对“从高度最高的矩形开始，向外扩展”的暴力做法的优化。
NOIP2016提高组 蚯蚓 关键在于发现蚯蚓长度的单调性后用队列维护，这种有单调性的问题都可以用队列，包括合并果子
双端队列 关键在于发现排序后下标单谷可以构成双端队列，然后拼出最少单谷即可。找性质建议手玩。
雪花雪花雪花 这种先hash一下排除绝对不同构的情况的方法考虑记一下，没准哪天用上了。
回文子串马拉车，后缀数组有倍增法，最小表示法可以复制一遍然后在SAM上走。至于周期问题就离不开kmp了一般。
最长异或路径 根据异或运算自反律(a xor a = 0)，两点间路径异或值就是 根节点 到两点 前缀异或值 异或起来，lca以上的抵消了。最后在01trie上贪心，对于每个点的前缀异或值，从高位到低位，树上尽量走相反的，走不了再走相同的，答案取max即可。
数据备份 链表+二叉堆，合并距离的做法
还有个霍夫曼树不想写了，想补就上oiwiki去复习喽。。。
习题
NOIP2008提高组 双栈排序 发掘一个性质，得出两个数不能在同一个栈的条件，最后二分图染色判定即可
NOI1999 内存分配 链表+二叉堆模拟，先释放内存再判断，最后释放所有内存即可。(写得巨大复杂，原本还是luogu最优解，后面被超2ms，呜呜呜。)
矩阵 二维hash，注意不同维度用不同base(进制)即可。
树形地铁系统 乱造了一个树哈希，最后过了
生日礼物 二叉堆+链表+贪心
0x20
详见搜索
0x30
例题
CQOI2007 余数之和 mod展开，除法分块
可见的点(同SDOI2008 仪仗队) 欧拉函数的基础应用，考虑到对称性即可，可以用线性筛求欧拉函数
中间有exgcd、excrt、矩阵乘法板子，不记了。
石头游戏 算是矩阵表达修改向量?用到了经典套路，多种矩阵按周期转移，取周期最小公倍数，套路应用于ZJOI2005 沼泽鳄鱼
中间俩高斯消元，异或高斯消元，懒得记了。
JLOI2015 装备购买 实数线性基+排序贪心，就模仿线性基的方式用加减乘除把高位消掉就可以了，这个题为了防止卡精度要换逆元
下一道是线性基第k大，注意0的处理和化最简形就可以了，可以在模板里查看。
计数交换离谱巨大找规律题目，洛谷题解里和有标号无根树映射的方法有点难理解，还是打表得了。。。
*SDOI2010 古代猪文 1.欧拉定理降幂 2.质因数分解模数最后CRT合并起来，以便于预处理阶乘和逆求组合数，用lucas定理
*Devu和鲜花 多重集组合数:经典正难则反+容斥原理+状压
期望dp正着来难就反着推，概率dp也一样(参考JLOI2013 卡牌游戏)，因为最终态唯一，更好反推
习题
矩阵幂求和 奇偶讨论分治求等比数列之和+矩阵乘法，之前还在想这题能不能直接错位相减矩阵求逆
*WC2011 最大XOR和路径(就书上XOR一题) 对一个题完全没想法的时候，一定要注意特殊化问题。分析详见提交记录，主要讨论到链和环的做法，然后就可以上线性基了
CQOI2013 新NIM游戏 发掘性质，最后发现是求和极大的线性基，也是贪心排序插入线性基
SDOI2016排列计数就是错位排列模板，容斥原理和二项式反演都可以解决，不贴了。
天码 约数有关容斥，虽然但是当时没想到莫比乌斯函数，是自己嗯造了个容斥约数的过程，发现只有质因数分解后所有质因子幂次为1的参与容斥
NOIP2016 换教室 之前状态整大了，直接记录换没换成就可以了，其他两维度时间，换了多少次显然
最后俩玩意一个有向图博弈，一个台阶Nim，以后再学了。。。
0x40
例题
区间最大公约数 利用gcd性质，线段树维护区间差分数组gcd即可
窗内的星星 这个题要转化成扫描线，移动0.5解决不能在边界上的问题，主要注意结束边向右移，先处理结束边再处理起始边的问题
*蒲公英 在线区间众数的经典做法，主要是想到预处理块内区间众数，每种数出现次数，ynoi那个卡空间，要用扫vector的做法，摆了
磁力块 比较神的一个技巧，大段按一个数值排序，然后分块，小段内按另一个东西排序
时刻准备复习点分治写法，不熟练
随时准备复习fhqtreap写法
习题
真正的骗子 并查集，发现要凑数，考虑背包
IOI1998 矩形周长picture 推一下矩形周长怎么贡献的，扫描线模板即可，注意先处理结束边
作诗 都什么年代还在用传统分块做法。我们要注意到一个转化:区间偶数个数 = 区间总数 - 区间奇数个数，考虑bitset维护，数出现就在自己对应bitset位置上取1，总数就是区间bitset or和的count，奇数个数就是xor和的count。要快速处理的话，xor运算逆元存在，所以考虑前缀和。or是区间可重复贡献问题，所以考虑ST表。但是预处理时间有点长，空间也危，我们要牺牲一下单次询问的时间复杂度来平衡上面这俩玩意，分块一下，连续块用上面的前缀和、ST表做法，散块暴力即可。(时空复杂度懒得算了，大概预处理和空间都除以块长，询问时间变为块长)
超级备忘录 在平衡树写题记录内有这一类题目的套路，就多个轮换操作，就是裂了并回去就好了。(据说splay写这个很麻烦，直接吊打了)
*流星(POI2011 MET-Meteors) 断环成链+整体二分，这个题给了一个启示就是二分答案都可以应用于整体二分，应不只局限于求第k大
0x50
一开始好像提了一嘴杨表，有时间去了解
陪审团 经典的01背包，最小化两团体价值之和差值最小的问题
坏掉的机器人 高斯消元优化成环的期望dp，为啥说是“优化”呢，因为洛谷上有个题解这个题dp50次直接冲过去了，由此可见求期望dp成环是可以迭代收敛的(?)
NOIP2017 宝藏 关键是想到以扩展层为阶段划分
开车旅行 倍增优化dp，不容易想到的一种
裁剪序列 不是纯粹的“滑动窗口”式单调队列优化dp，这题要结合贪心排除可能决策
*任务安排2 斜率优化，分析详见提交记录，同时SDOI对应题不保证x坐标单调递增，需要在单调队列上二分
*诗人小G 决策单调性优化dp，书上那个构造同构然后求导证明实在是太难搞了，一般打表发现决策单调性
连通图 (同时似乎是经典的生成函数例题)套路:枚举1号点所在联通块大小
*启示录 AHOI2009 同类分布(月之谜) 数位dp求方案数，前面一题考虑试填，后面一题考虑前缀和相减
数位dp一般以数位为阶段，再设计其他状态来转移，同时边界处理有点难，一般多用记忆化搜索实现
习题
NOI2001 陨石的秘密 经典套路，钦定最左一串匹配就能不重不漏
NOI1999 棋盘分割 方差经典变形平方的平均减平均的平方，然后从记忆化搜索入手，容易发现是二维区间dp
消木块 神秘的状态设计，要考虑一下未来的情况
*HNOI2011 XOR和路径 看到有小数，显然直接做不好做，分位讨论，高斯消元
芯片 高进制状压，注意一开始放的时候就加上价值
估算 对顶堆预处理价值，直接大力dp
干草堆 参考严格升级版CSP-S2019 划分 通过贪心想到单调队列优化
股票交易 关键在于想到从i-1-w天转移一定最优，大胆猜结论
*K匿名序列 贪心+斜率优化
*IOI2000 邮局 二维决策单调性优化，不过被wqs二分+二分队列爆标了?(反正不会)
0x60
通信线路 二分答案+01bfs/分层图最短路
道路与航线 dijkstra+拓扑排序
*排序 有向传递闭包
野餐规划 最小度限制生成树，拆成几个联通块，连起来再替换(生成树重要思想)
APIO2010 巡逻 有一种反悔贪心的感觉，取反代价代表撤销
*NOIP2016 天天爱跑步 注意到 子树和=当前所有遍历到的点总和-根到该节点路径总和
次小生成树 找一条边替换，树上树剖维护最大值和严格次大值即可
*NOIP2012 疫情控制 二分答案，贪心，策略性较强，下回树上跳再也不写树剖了......
IOI2008 Island基环树直径，要么过环要么不过环，过环就dp一下，单调队列优化就好了
【模板】静态仙人掌(某个题确实是这玩意没错吧)广义圆方树，小粉兔的写的挺好，不多介绍了，注意要魔改tarjan存一下fa防止返回去。lca圆点直接求，方点环上绕。
圆桌骑士 发掘点双性质
【模板】2-SAT 那几个题确实大同小异不如直接学模板
网络流二分图相关的书上不完全，不记录了
习题
升降梯上 分层图最短路，其实就是节点状态多带一个维度
会合 基环树上分类讨论
*HNOI2012 矿场搭建 点双+分类讨论，不算难
*杀人游戏 题面爆!考虑特殊化这个题目，因为不好下手，考虑到链怎么做，强连通分量怎么做就好了
标签：指南,二分,进阶,算法,单调,习题,排序,dp,贪心 From： https://www.cnblogs.com/woshilaji/p/17520173.html