More
或许是人品不错，最近两天接连刷到三道排列组合相关的题。在此作简单整理。
AtCoder ABC226 F – Score of Permutations
题意参见原题面。
很自然地想到，对于一个排列，有条的连边。因为排列中正整数恰好出现仅有一次，所以等价于每个点有且仅有一条出边、一条入边的图。容易发现这个图由若干个有向环构成（包括自环——即的情况）。例如排列代表由和两个环组成的图。
是的，又是一道考试时想出正解没有打出来的题目
根据题意，我们很容易想到一个朴素的类区间DP——令表示现在将第件货物划分到第箱中，且作为箱内的最后一件货物，所需最小花费。容易写出转移：，初值有，应求得。
Problem D – Codeforces Round #127 (Div. 1)
多模式串匹配，是不是又是AC自动机啊？
显然，每个文本串中，模式串的排列构成的子序列的逆序对数量只和模式串有关。所以我们可以对模式串建立Trie树，每扫入一个文本串的单词就进行匹配。可以做到，K为文本串总长（虽然单个字符串的长度极小可以）。这样就构建出一个由到构建的数列。
枚举的全排列然后暴搜显然不可行。我们注意到，如果钦定一个数，只要知晓当前的排列中前位分别是哪些数，就可以立刻算出加入排列后新增的逆序对数量。则我们考虑状压DP。 （更多…）
唉，还是没有考虑清楚细节。
容易发现，一个双倍回文串必定是一个回文串，同时前半段也是一个回文串。那么在使用Manacher算法求取每个字符对应的最长回文串时，就可以同步更新答案。
但一开始我写出这样的判断：
- 1
- 2
- 3
// 完成第i个字符的最长回文的更新后 if (len[i] % 4 == 0 && len[i - (len[i] >> 1)] == len[i] / 2) ans = max (ans, len[i]);
想看正解请直接跳过文章前半段。
不知道到底错没错的错解
这是一道树的直径的必经边问题。
单单求树的直径是非常简单的。可以通过两次DFS/BFS或一次树形DP完成的求解。显然，树的直径长度唯一，但构成该长度的链的方案可能不唯一。
