或许是人品不错，最近两天接连刷到三道排列组合相关的题。在此作简单整理。
题意参见原题面。
很自然地想到，对于一个排列$P = (p_1, p_2, \dots, p_n)$，有$n$条$i \rightarrow p_i$的连边。因为排列中正整数$1, 2, \dots, n$恰好出现仅有一次，所以等价于每个点有且仅有一条出边、一条入边的图。容易发现这个图由若干个有向环构成（包括自环——即$p_i = i$的情况）。例如排列$P = (1, 3, 4, 2)$代表由$1 \rightarrow 1$和$2 \rightarrow 3 \rightarrow 4 \rightarrow 2$两个环组成的图。
是的，又是一道考试时想出正解没有打出来的题目
根据题意，我们很容易想到一个朴素的类区间DP——令$dp(i, j)$表示现在将第$i$件货物划分到第$j$箱中，且作为箱内的最后一件货物，所需最小花费。容易写出转移：$$dp(i, j) = \min\limits_{k \in [0, i) \land \sum\limits_{p=k+1}^{i} a_p \leq W } dp(k, j-1) + \sum\limits_{p=k+1}^{i} a_p + \textrm{极差}\{a_t \mid t \in [k + 1, i]\}$$，初值有$dp(0, 0) = 0$，应求得$\min\limits_{j \in [1, n]} dp(n, j)$。
Problem D – Codeforces Round #127 (Div. 1)
多模式串匹配，是不是又是AC自动机啊？
显然，每个文本串中，模式串的排列构成的子序列的逆序对数量只和模式串有关。所以我们可以对模式串建立Trie树，每扫入一个文本串的单词就进行匹配。可以做到$\mathrm{O}(K)$，K为文本串总长（虽然单个字符串的长度极小可以$\mathrm{O}(NK)暴跳$）。这样就构建出一个由$1$到$n$构建的数列。
枚举$15!$的全排列然后暴搜显然不可行。我们注意到，如果钦定一个数$x$，只要知晓当前的排列中前$j$位分别是哪些数，就可以立刻算出$x$加入排列后新增的逆序对数量。则我们考虑状压DP。 （更多…）
根据题意，这是一道多模式串多文本串匹配问题。容易想到AC自动机。易知第一行的输入可以用递归/栈的形式模拟并且构建一棵Trie，可以在$\mathrm{O}(|S_0|)$的时间内完成。可以同时构建Fail失配树，时间复杂度$\mathrm{O}(P)$，$P$为Trie的节点总数。
唉，还是没有考虑清楚细节。
容易发现，一个双倍回文串必定是一个回文串，同时前半段也是一个回文串。那么在使用Manacher算法求取每个字符对应的最长回文串时，就可以同步更新答案。
但一开始我写出这样的判断：
// 完成第i个字符的最长回文的更新后
if (len[i] % 4 == 0 && len[i - (len[i] >> 1)] == len[i] / 2)
ans = max (ans, len[i]);想看正解请直接跳过文章前半段。
这是一道树的直径的必经边问题。
单单求树的直径是非常简单的。可以通过两次DFS/BFS或一次树形DP完成$\mathrm{O}(N)$的求解。显然，树的直径长度唯一，但构成该长度的链的方案可能不唯一。
This volume contains 3 passages in total. One from BBC Future, the others from BBC News.
Information below may be out of date. All following passages are extracted for means of learning and reading only. 请注意，下方信息可能已过时。所有截取的文章仅作学习阅读之用。