时间限制：4000MS 内存限制：524288KB
难度：7.0
给定一颗 n 个点的树。每个点都一个正整数点权 A_i，你需要支持以下两种操作：
1、询问点 x 和点 y 之间的路径上的所有点（包括点 x 和点 y ）的点权是否构成一个从 1 开始的排列。
2、将 A_x 修改为 y。
第一行一个正整数 T 表示数据组数。
接下来一行输入两个正整数 n,q 表示数的点数和询问个数。
接下来一行 n 个正整数，第 i 个正整数表示 A_i 的初值。
接下来 n-1 行每行两个正整数 u,v 表示树上的一条边 (u,v) 。
接下来 n 行每行三个正整数 tp,x,y 表示一个操作，其中 tp 表示操作种类。
对于每一个操作 1 如果符合条件，输出 Yes ，否则输出 No 。…
时间限制：4000MS 内存限制：262144KB
出题人：E.Space 难度：7.0
它会把输入按行读入，原封不动地复制到输出中去。
但是在一次更新以后，它的程序出了一些问题。
它没法输出换行符了。
并且，读入的时候，总会莫名其妙地随机漏掉开头和结尾的若干个字符，甚至整行都会漏掉。
比如 orzxxxxx 可能会变成 rzxx、orz、x 或者空串。
现在你找到一份输入文件丢给它，你想知道它的输出可能有多少种情况，以及每种情况分别是什么。
由于你找到的输入文件全部来自之前的福建省选，所以所有的输入文件每行只可能包含 A、C、G、T 四种字符。
第一行一个正整数 n，表示（题面中）输入文件的行数。
接下来 n 行，表示输入文件的内容。保证这 n 行中每行的每个字符是 A、C、G、T 四种字符中的一种。
接下来一个整数 k, (0 \leq k \leq 1)，具体含义详见输出格式。
若 k=0，你需要输出一行，表示输出的可能情况个数模 10^9+7 的结果。
若 k=1，你需要按照字典序从小到大输出所有可能的输出情况，一行一个字符串，最后一行输出输出的可能情况个数模 10^9+7 的结果。
时间限制：1000MS 内存限制：262144KB
难度：6.0
给定 2 个长度分别为 m 和 n 的 DNA 序列 X 和 Y，以及一个长度为 p 的模式子序列 P。带有子序列包含约束的最长公共子序列问题就是要找出 X 和 Y 带有包含子序列 P 约束的最长公共子序列的长度。
例如，如果给定的 DNA 序列 X 和 Y 分别为 X=AATGCCTAGGC，Y=CGATCTGGAC，模式子序列 P=GTAC，则子序列 ATCTGGC 是 X 和 Y 的一个无约束的最长公共子序列，而包含 P 为其子序列的最长公共子序列是 GCTAC。
第一行中给出正整数 m,n,p，分别表示给定序列 X 和 Y 以及模式子序列 P 的长度。m,n,p<300 。
接下来的 3 行分别给出序列 X 和 Y 以及模式子序列 P 。
将计算出的 X 和 Y 带有包含子序列 P 约束的最长公共子序列的长度输出。如果 X 和 Y 不存在包含子序列 P 的公共子序列，则输出 -1。
时间限制：1000MS 内存限制：131072KB
难度：5.0
求一个字符串的回文子序列个数。
如果 p_1p_2 \cdots p_m 满足 1 \leq p_1<p_2<\cdots<p_m \leq n，则称 a_{p_1}a_{p_2}\cdots a_{p_m} 是序列 a_1a_2\cdots a_n 的一个子序列。
如果对于所有 1 \leq i \leq n 都满足 a_i=a_n-i+1，则 a 是一个回文串。空串也是回文串。
一个字符串
回文子序列个数 \mod 10^9+7
样例中所有回文子序列按照字典序如下：
“”（空串）、”a”、”aa”、”aka”、”f”、”ff”、”k”、”kak”、”kk”、”t”
对于 100\% 的数据，n \leq 5000 。
字符串中仅包含小写字母。
时间限制：1000MS 内存限制：131072KB
难度：7.5
有 n 个大串和 q 个询问，每次给出一个字符串 s 询问在多少个大串中出现过。
输入的第一行有两个整数分别代表 n 和 q 。
接下来的 n 行，分别给出题中所述的 n个只包含小写字母的字符串。
再接下来的 q 行，每行给出一个询问只包含小写字母的字符串。
对于每一个询问，输出一行答案。
n \leq 10000, q \leq 60000 。
原串总长度 \leq 100000 。
询问串总长度 \leq 360000 。
Source: BZOJ 2780 && SPOJ 8093…
时间限制：1000MS 内存限制：131072KB
难度：8.0
给定一个长度为 n 且仅包含小写英文字母的字符串 S。你有一个字符串 T，初始为空串。
你可以进行 n 次操作，每次操作你可以在 T 的前端或末尾加入一个任意字母。记第 i 次操作后 T 在 S 中的出现次数为 f_i，你需要最大化 ans=\sum\limits_i f_i 。
第一行一个正整数 n 。
第二行一个长度为 n 的字符串 S 。
一行一个整数，表示 ans 的最大值。
对于 100\% 的数据，1 \leq n \leq 2\times 10^5 。
时间限制：1000MS 内存限制：524288KB
难度：8.0
给出一棵 n 个节点、叶子不超过 20 个的树，每个节点上有 0 到 c-1 的数字。
树上任意两点 A、B 间的有向路径 A \rightarrow B 形成了一个字符串（A \rightarrow B 和 B \rightarrow A 构成的串相反）。
求总共有多少个互不相同的字符串。
第一行两个数，n, c 。
第二行 n 个 0~c-1 间的数，表示每个节点的颜色。
接下来 n-1 行，每一行表示一条树边。
保证叶子个数不超过 20。
一个整数，表示不同的字符串数。
1 \leq n \leq 10000, 1 \leq c \leq 10 。
时间限制：1000MS 内存限制：524288KB
出题人：zzx 难度：6.0
给定字符串 s 。你需要回答 n 个询问，第 i 个询问给出一个正整数 k_i 和一个字符串 m_i，请求出 s 的所有子串 t 中，满足 m_i 在 t 中出现至少 k_i 次的字符串 t 的长度的最小值。
一个字符串的子串是该字符串中的连续一段字符。
保证任意两个询问的 m_i 不相同。
第一行包含一个字符串 s（1 \leq \left|s\right| \leq 10^5）。
第二行包含一个正整数 n（1 \leq n \leq 10^5）。
接下来 n 行，每行一个正整数 k_i（1 \leq k_i \leq \left|s\right|）和一个非空字符串 m_i，表示第 i 个询问。
所有字符串仅包含小写英文字母，且所有询问字符串的总长度不超过 10^5 。
对于每个字符串输出一行表示答案。
如果 m_i 在 s 中出现次数小于 k_i，输出 -1 。…
时间限制：1000MS 内存限制：262144KB
出题人：E.Space 难度：6.1
在这个游戏中一共有 n 个角色。你需要编写一些关于这些角色的对话内容。
你打算用角色名字的一个非空子序列来作为它的简称。
当然，不同的角色要用不同的字符串作为简称，否则你就变量重名了。
你想确定一个简称的分配方案使得所有角色中最长的简称尽量短。
第一行一个正整数 n。
接下来 n 行，每行一个由小写字母组成的字符串，代表一个角色的名字。
不同的角色可能会有相同的名字。
如果不存在一种分配简称的方案满足条件，输出 -1。
否则第一行输出一个正整数，表示最长的简称的最小长度。
接下来 n 行每行一个字符串，按顺序表示每个角色的简称。
若有多种方案满足条件，那么你可以输出任意一种。
保证 n \leq 300 ，每个名字的长度不超过 300。