优秀的拆分「NOI2016」

题目描述如果一个字符串可以被拆分为$\text{AABB}$的形式,其中$\text{A}$和$\text{B}$是任意非空字符串,则我们称该字符串的这种拆分是优秀的。例如,对于字符串$\texttt{aabaabaa}$,如果令$\text{A}=\texttt{aab}$,$\text{B}=\texttt{a}$,我们就找到了这个字符串拆分成$\text{AABB}$的一种方式。 一个...

SvT[BZOJ3879]

【题目描述】有一个长度为n的仅包含小写字母的字符串$S$,下标范围为$[1,n]$. 现在有若干组询问,对于每一个询问,我们给出若干个后缀(以其在$S$中出现的起始位置来表示),求这些后缀两两之间的LCP(LongestCommonPrefix)的长度之和.一对后缀之间的LCP长度仅统计一遍. 【输入格式】第一行两个正整数$n,m$,分别表示$S$的长度以及询问的次数. 接下来一行有一个字符...

差异「AHOI2013」

【题目描述】给定一个长度为$n$的字符串$S$,令$T_i$表示它从第$i$个字符开始的后缀,求: $\sum\limits_{1\le i<j\le n}\operatorname{len}(T_i)+\operatorname{len}(T_j)-2*\operatorname{lcp}(T_i,T_j)$ 其中,$\operatorname{len}(a)$表示字符串$a$的长度...

Samjia和矩阵[LOJ6173]

【题目描述】给你一个只包含大写字母的矩阵,求有多少本质不同的子矩阵。 【输入格式】第一行包含两个整数$n$,$m$,表示矩阵$n$行$m$列 。接下来$n$行描述这个矩阵。 【输出格式】只含一个整数,为本质不同的子矩阵个数。 先枚举长度$l$,然后将每个串压位哈希(哈希提前处理好就行)盗用一张图然后从上到下,从左到右,生成一个这样的串:ac$bc 对于每个长度$l$生成的新串 将这个新串的本...

跳蚤[BZOJ4310]

【题目描述】很久很久以前,森林里住着一群跳蚤。一天,跳蚤国王得到了一个神秘的字符串,它想进行研究。首先,他会把串分成不超过$k$个子串,然后对于每个子串$S$,他会从$S$的所有子串中选择字典序最大的那一个,并在选出来的$k$个子串中选择字典序最大的那一个。他称其为“魔力串”。现在他想找一个最优的分法让“魔力串”字典序最小。 【输入格式】第一行一个整数 k,$k\leq 15$接下来一个长度...

产奶模式「usaco2006」

【题目描述】农夫John发现他的奶牛产奶的质量一直在变动。经过细致的调查,他发现:虽然他不能预见明天产奶的质量,但连续的若干天的质量有很多重叠。我们称之为一个“模式”。 John的牛奶按质量可以被赋予一个$0$到$1000000$之间的数。并且John记录了$N(1\le N\le 20000)$天的牛奶质量值。他想知道最长的出现了至少$K(2\le K\le N)$次的模式的长度。比如1 ...

队列变换「usaco2007」

【题目描述】FJ打算带他的$N(1 \leq N \leq 30,000)$头奶牛去参加一年一度的“全美农场主大奖赛”。在这场比赛中,每个参赛者都必须让他的奶牛排成一列,然后领她们从裁判席前依次走过。 今年,竞赛委员会在接受队伍报名时,采用了一种新的登记规则:他们把所有队伍中奶牛名字的首字母取出,按它们对应奶牛在队伍中的次序排成一列(比如说,如果FJ带去的奶牛依次为Bessie、Sylvia...