突然想发这样一个帖子讲一讲自己在2014年里见到的比较喜欢的算法竞赛题目，也算是对于我的算法题的偏好的一个总结吧。

就先从我自己出的题目开始吧。

• biconnected and sconnect 这两个题目其实也说不上特别喜欢，不过感觉想法还是稍微有点意思的。大概的想法都是反着来，计算不满足条件的图的数量，然后注意到双联通分量和强连通分量的划分一点枚举以后可以缩成一个树/DAG，而树和DAG的计数问题都是大家所熟知的。因此就能做了。不过这里有个比较有意思的地方是如果直接用树的n^3的求det的方法，其实不能做到最好。如果使用枚举叶子然后容斥的做法，就也能做到3^n的复杂度。这是我后来才想到的。
• hero meet devil and square 这两个都是从dp of dp的想法衍生出来的题目。做法其实是很常规的，都是非常经典的：要对满足某个条件的对象计数，考虑判断这个条件是否满足的小dp，对使得小dp满足的输入数量计数，并且通过分析减少状态数量。分析以减少数量这一步在这两个题目中都比较直接。在我的冬令营讲课中有讲的一道Jigsaw的那题，它的奇偶性分析还是挺有趣的。
• MST(无连接)。我的ppt里有。这题其实还是非常有趣的。有两个方法都能推出正解也都很有趣。都用到了期望的线性性。具体来说就是得出MST的整体值还是比较困难的，但是MST这个问题不是一个非常global的问题的，对于每条边存在一个只需要部分信息的判断它是否在MST中的方法（比它小的边是否将两端点联通）。有了这个以后就能对每个边分别求他们对MST期望大小的贡献。因为现在我们只focus on 一条边，所以自然也就大大减少了需要考虑的对象。从而就能减少我们dp中需要考虑的状态。
• 紫荆花之恋。我在WC 2014中出的题目，这个题目的核心在于可以意识到替罪羊树这一技巧，能够适用于一切依靠子树大小来维持平衡的结构。那么，它必然也可以被使用于点分治这一结构。那么我们就可以用替罪羊树来维护动态的点分治。当时觉得还挺有意思的，不过现在也已经不怎么研究数据结构了>_>。

感觉自己出的还比较喜欢的题目暂时就这些了，下面列举一些比较有趣的别人出的题目：

• SRM 641 1000 不得不说我觉得这是一个神题，做法非常巧妙。核心的思想可能跟前面提到的MST一题类似，都是把需要计算的期望值分成许多个小部分，然后每次只计算一个小部分，由于每次只关心这样的一个牵涉面比原先小的问题，因此需要记录的状态数量也大大减少，从而达到降低复杂度的目的。我觉得这是我年度最喜欢的题目。
• Substrings，见我WC讲课的ppt。不得不说这个题目也十分的巧妙。做法还是比较经典的对于S和T，考虑T的哪些性质在枚举S的时候是有用的，然后将T划分成一些等价类并对等价类计数，最后再计算每个等价类的合法S数量。这样的想法是很直观的，但是令人没有想到的是，这里的等价类即使在n<=50也是很少的！
• Jigsaw 不得不说这题其实是很多想法的来源，题目见冬令营讲课的链接。这个题目其实是一个非常经典的“dp套dp”的题目。详细的之前也说过了。

先写到这里有空再补吧:)