Menci

「Codeforces 808G」Anthem of Berland - KMP + DP

给一个含有字母以及 ? 的 $s$ 串和一个含有字母的 $t$ 串，其中 ? 可以匹配任何字符，求 $s$ 串最多匹配 $t$ 串多少次。

「APIO2013」TOLL - 搜索 + 最小生成树

幸福国度可以用 $N$ 个城镇（用 $1$ 到 $N$ 编号）构成的集合来描述，这些城镇最开始由 $M$ 条双向道路（用 $1$ 到 $M$ 编号）连接。城镇 $1$ 是中央城镇。保证一个人从城镇 $1$ 出发，经过这些道路，可以到达其他的任何一个城市。这些道路都是收费道路，道路 $i$ 的使用者必须向道路的主人支付 $c_i$ 分钱的费用。已知所有的这些 $c_i$ 是互不相等的。最近有 $K$ 条新道路建成，这些道路都属于亿万富豪 Mr. Greedy。

Mr. Greedy 可以决定每条新道路的费用（费用可以相同），并且他必须在明天宣布这些费用。

两周以后，幸福国度将举办一个盛况空前的嘉年华！大量的参与者将沿着这些道路游行并前往中央城镇。共计 $p_j$ 个参与者将从城镇 $j$ 出发前往中央城镇。这些人只会沿着一个选出的道路集合前行，并且这些选出的道路将在这件事的前一天公布。根据一个古老的习俗，这些道路将由幸福国度中最有钱的人选出，也就是 Mr. Greedy。同样根据这个习俗，Mr. Greedy 选出的这个道路集合必须使所有选出道路的费用之和最小，并且仍要保证任何人可以从城镇 $j$ 前往城镇 $1$ （因此，这些选出的道路来自将费用作为相应边边权的 “最小生成树”）。如果有多个这样的道路集合，Mr. Greedy 可以选其中的任何一个，只要满足费用和是最小的。

Mr. Greedy 很明确地知道，他从 $K$ 条新道路中获得的收入不只是与费用有关。一条道路的收入等于所有经过这条路的人的花费之和。更准确地讲，如果 $p$ 个人经过道路 $i$，道路 $i$ 产生的收入为乘积 $c_i \cdot p$。注意 Mr. Greedy 只能从新道路收取费用，因为原来的道路都不属于他。

Mr. Greedy 有一个阴谋。他计划通过操纵费用和道路的选择来最大化他的收入。他希望指定每条新道路的费用（将在明天公布），并且选择嘉年华用的道路（将在嘉年华的前一天公布），使得他在 $K$ 条新道路的收入最大。注意 Mr. Greedy 仍然需要遵循选出花费之和最小的道路集合的习俗。

你是一个记者，你想揭露他的计划。为了做成这件事，你必须先写一个程序来确定 Mr. Greedy 可以通过他的阴谋获取多少收入。

「APIO2014」Split the sequence - 斜率优化 DP

你正在玩一个关于长度为 $n$ 的非负整数序列的游戏。这个游戏中你需要把序列分成 $k + 1$ 个非空的块。为了得到 $k + 1$ 块，你需要重复下面的操作 $k$ 次：

1. 选择一个有超过一个元素的块（初始时你只有一块，即整个序列）
2. 选择两个相邻元素把这个块从中间分开，得到两个非空的块。

每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。

「CTSC2012」Cheat - SAM + 二分 + 单调队列 DP

给出 $m$ 个串组成的「标准作文库」。对于任意一个串，如果它的长度不少于 $L$ 且在标准作文库中出现过，则它是「熟悉」的。对于任意一个串，如果能将它划分为若干个串，使「熟悉」的串的长度超过总长度的 $90\%$，则称这个串是「熟悉的文章」，定义 $L_0$ 为使这个串成为「熟悉的文章」的最大的 $L$。给出若干个串，求每个串的 $L$ 值。

「BZOJ 2555」SubString - SAM + LCT

1. 在当前字符串的后面插入一个字符串；
2. 询问字符串 $s$ 在当前字符串中出现了几次？（作为连续子串）

「TJOI2015」弦论 - SAM

对于一个给定长度为 $n$ 的字符串，求它的字典序第 $k$ 小的子串。

「BZOJ 1396」识别子串 - SAM + 线段树

对于一个字符串 $S$，和 $S$ 中的第 $i$ 个字符 $x$，定义子串 $T = S(i \ldots j)$ 为一个关于 $x$ 的识别子串，当且仅当：

1. $i \leq x \leq j$；
2. $T$ 在 $S$ 中只出现一次。

求 $S$ 关于每一位字符的最短识别子串长度。

「SDOI2010」古代猪文 - 费马小定理 + Lucas + CRT

远古时期猪王国有 $n$ 个文字，现有的文字数量为远古时期的 $1 / k$（$k$ 是 $n$ 的一个正约数），剩余的 $n / k$ 个文字有很多种情况，假设有 $p$ 种情况，则研究这些文字的代价为 $g ^ p$，求这个代价对 $999911659$ 取模后的结果。

「SDOI2013」随机数生成器 - 数学 + BSGS

给定 $p$、$a$、$b$、$x_1$，现有一数列

求最小的 $i$ 满足 $x_i = t$。

「SDOI2008」Sandy 的卡片 - 差分 + SAM

相同的定义为：两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串。给 $n$ 个串，求它们相同的子串最大长度。