mhlwsk的博客

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1068

这题是求二分图最大点独立集，二分图最大点独立集=n-最大匹配。
要注意的是这题没有区分两种颜色的结点，因此算出的最大匹配要除2。

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1562

求出一个满足要求的T序列比较容易想，只需要从i向加上距离后对应的点连边，然后就是一个二分图匹配问题了。
麻烦的是要输出字典序最小的T，这里要注意两点：一是连边的时候要小的数在前，二是在跑匈牙利算法的时候一定要倒着搜。

题目链接：http://poj.org/problem?id=3020

给定一个网格，网格中某些格子有点，用一些2*1的挡板覆盖，问在可以重叠覆盖的情况下覆盖掉所有的点至少需要多少挡板。

这题是二分图匹配。一开始想到了是一张图求最小边覆盖集，但却没想到怎么向二分图转化。其实这题不用转化，因为我们可以给斜行染两种颜色，相邻斜行染不同颜色，然后就会发现其实所有的边（若结点相邻则连边）都是连接的两种颜色的结点，这已经是二分图了。直接在这张图上跑匈牙利算法求解就行了。答案最小边覆盖集就是n-最大匹配。

另外需要注意的是这样连边正反各自连了一遍，匈牙利算法跑的时候也没有区分两种颜色的结点，因此最大匹配要除二。

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2565

Manachar算法，另外维护一个l数组和一个r数组，分别代表某位置作为某回文串左边界或右边界时该回文串的最长回文半径。
求出l和r之后扫一遍所有的#位置，l[i]+r[i]-2的最大值即为答案。

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2330

差分约束题，差分约束理论见这篇博文

如果给出的不等式有”<=”也有”>=”，又该如何解决呢？很明显，首先需要关注最后的问题是什么，如果需要求的是两个变量差的最大值，那么需要将所有不等式转变成”<=”的形式，建图后求最短路；相反，如果需要求的是两个变量差的最小值，那么需要将所有不等式转化成”>=”，建图后求最长路。
引用自http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html

这题还需要注意自环，因为是求最长路，某些写法的spfa可能不会让正自环无限入队，从而导致无法正确判断这类正环的情况。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3068

求最长回文子串，Manachar算法模板题，这里贴出Manachar算法模板。

题目背景：http://acm.hdu.edu.cn/showproblem.php?pid=3746

一道经典KMP题目。
出几组数据推导，可以得出一个结论，循环节长度等于len-fail[len]，另外可以观察出字符添加在开头和结尾是等价的，因此就可以减去循环节得出要加的长度了。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2594

一开始一直在纠结怎样从B串向A串构造fail指针，但其实不用这么麻烦，只需要把B串接到A串后面，对新串构造fail指针，然后在新串中找出满足长度小于两串长度的的最长前缀即可。

题目链接：https://hihocoder.com/problemset/problem/1329

Splay模板题，这里记录用set的lower_bound、upper_bound和erase的区间删除功能实现的做法。

题目链接：http://poj.org/problem?id=3481

这题可以用set水过，用两个反向的set分别维护最大值和最小值即可（找最大值或最小值这里要用lower_bound）。