算法清单

清单

位运算优化

• [SCOI2016]美味
• [NOI2014]起床困难综合症

Kruskal重构树(真TM具有优美性质)

• [NOI2018]归程
• Network

网络流(戳我有知识讲解)(戳我有知识扩展)

• Arietta

最大流:

• 魔术球问题
• [CQOI2015]网络吞吐量(最短路+网络流)
• [HNOI2013]切糕
• [国家集训队]happiness(超经典最小割问题)
• [国家集训队]圈地计划(happiness的升级版)
• [八省联考2018]劈配

最小割:

• 拍照

最大点权独立集:

• [HDU1569]方格取数(2)
• 8.8考试T3

最小路径覆盖

• [国家集训队]部落战争(最小不相交路径覆盖)
• [模板]最小路径覆盖问题
• [POJ2594]Treasure Exploration(最小可相交路径覆盖,传递闭包)

费用流

• [SCOI2007]修车
• 洞穴遇险
• [Noi2012]美食节
• 8.10 考试T2，很好的一个套路qwq

尽量从奇数偶数点入手，分开建图，优化边的数目和复杂度

二分图

• [HNOI2006]超级英雄 BZOJ

2-SAT

• Peaceful Commission
• [JSOI2010]满汉全席

平面图-对偶图(戳我有知识讲解)

• [BJOI2006]狼抓兔子
  ((戳我有题解)[http://www.cnblogs.com/cjoieryl/p/8418877.html])

莫队(戳我有例题)

• [国家集训队]小Z的袜子
• Rmq Problem / mex(戳我有题解)
• [国家集训队]数颜色(带修改)
• Machine Learning(Mex的带修改版)
• 美好的每一天

点分治(戳我有知识讲解)(戳我寻找更多题目)

• Tree
• [国家集训队]聪聪可可
• [模板]点分治1
• [NOI2014]购票
  (戳我有题解)(戳我试试)
• [IOI2011]Race
• 树上游戏
• 小清新数据结构题

总结

其实点分治是求解树上路径一个很优秀的方法，但是不能带修改
其实最经典的就是dp优化子树信息
考虑到dp顺序是有影响的，所以我们先"找根"->"修改根的所有子树信息"->"统计答案"->"修改回去"->"进入下一步分治"，因此一定要修改回信息！(复杂度貌似是O(n^logn)的)
所以策清楚路径信息是否会被覆盖的是很重要的

动态点分治(戳我有知识讲解)

• [ZJOI2007]捉迷藏
• SPOJ QTREE4
• [ZJOI2015]幻想乡战略游戏
• 8.9 考试T3

CDQ分治(戳我有知识讲解)

• [模板]树状数组1(没错，你没有看错)
• [模板]三维偏序(陌上花开)
• [NOI2007]货币兑换
• [HZOI 2016]偏序 I
• [HZOI 2015]偏序 II

总结

所以貌似可以用CDQ分治来优化dp,关键是要对性质理解

整体二分

• [HNOI2015]接水果

线性基(戳我有简易版知识讲解)(戳我有提高版知识讲解)

• [模板]线性基
• [BeiJing2011]元素
• nim游戏(好吧，这是假的，但是为下一题做铺垫)
• [CQOI2013]新Nim游戏
• [WC2011]最大XOR和路径
• [BJWC2011]元素
• 4.5考试T1

总结

如何保证插入的元素始终异或和始终为0？那么就在插入前Find一下就好了，至于若需要保证选入元素价值最大，那么价值就按从大到小排序就好了(贪心)
有时会与博弈论一起食用，对于这一类问题接触并不多

AC自动姬(戳我有知识讲解)

预备算法Tri树

• 于是他错误的点名开始了
• [HNOI2004]L语言(Trie树上运用dp思想)
• [NOI2014]动物园(KMP乱入)

正式的了

• [模板]AC自动机(简单版)
• [模板]AC自动机(加强版)
• [USACO12JAN]视频游戏的连击Video Game Combos(关于初值的设定)
• [JSOI2007]文本生成器(关于失配到底有什么用？具体定义)
• [模板题 USACO]AC自动机(技巧一)
• [USACO15FEB]审查（黄金）Censoring (Gold)(论栈的巧妙结合)
• [TJOI2013]单词(玄学统计答案方式)
• [SCOI2012]喵星球上的点名
• [SDOI2014]数数
• [HNOI2008]GT考试
• [POI2000]病毒
• [NOI2011]阿狸的打字机

可能是一些技巧吧
一.$fail$指针是一棵树，建议先构出树再在$dfs$中跑$query$，不然直接遍历的话，每次要把$fail$都遍历一遍太慢，是无意义操作

题型总结
玄学空间不会开
1.若干个模式串匹配一个文本串求
总共出现次数，是否出现，各个出现了多少次
2.已知模式串，求定长的文本串
只要包含一种模式串的方案数
包含最多的模式串的个数
3.已知模式串，求在文本串中的操作
支持删除（栈维护）

EXkmp(戳我有知识讲解)

• [GDOI2014]Beyond(戳我有题解)

Manacher(戳我有知识讲解，重点是复杂度证明)

• [模板]manacher算法
• 回文串

最小表示法(戳我有知识讲解)

• BZOJ1398
• 工艺(最小后缀)

后缀数组(戳我有知识讲解,09论文,04论文,戳我有题目推荐)

• [模板]后缀排序
• 后缀数组一·重复旋律(最长可重叠重复子串问题)
• 后缀数组二·重复旋律2(最长不可重叠重复子串问题)
• 后缀数组三·重复旋律3(A和B最长公共子串)
• 后缀数组四·重复旋律4(重复次数最多的连续字串)
• Long Long Message
• [NOI2015]品酒大会(一句话:对于所有lec(lcp)>=i的后缀串个数和方案中的最大价值)
• 统计不同子串个数
• 8.7考试T3

后缀自动机

感觉太难肝不动啊

高斯消元(戳我有异或方程组讲解)(戳我有加减题目推荐)(戳我有异或题目推荐)

• [模板]高斯消元法
• [JSOI2008]球形空间产生器
• 赶小猪
• [HNOI2013]游走
• [HNOI2011]XOR和路径
• 4.10考试T1 30分

博弈论

• nim游戏
• [SDOI2009]E&D
• [HEOI2014]人人尽说江南好
• [SHOI2008]小约翰的游戏
• [HAOI2015]数组游戏
• [SDOI2011]黑白棋
• [ZJOI2009]染色游戏(二维翻棋，值得回味)
• [HNOI2007]分裂游戏(真的♂)
• [HNOI2014]江南乐(真的♂)

构造(这应该是一个大坑)

• [TJOI2017]异或和
• CF #499 F.Tree

拉格朗日插值(戳我有知识讲解)

• [模板]拉格朗日插值
• [JLOI2016]成绩比较(支持O(n)区间插值)

坑

什么最小独立集子团，最小点权覆盖集，FFT之类的