时间限制：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\) 表示操作种类。
时间限制：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\) 的结果。
|
1 2 3 4 5 |
3 AC CC AA 1 |
时间限制：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\)。
|
1 2 3 4 |
11 10 4 AATGCCTAGGC CGATCTGGAC GTAC |
|
1 |
5 |
时间限制：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\)
|
1 |
akakfft |
|
1 |
10 |
样例中所有回文子序列按照字典序如下：
“”（空串）、”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\) 行，每行给出一个询问只包含小写字母的字符串。
对于每一个询问，输出一行答案。
|
1 2 3 4 5 6 7 |
3 3 abcabcabc aaa aafe abc a ca |
|
1 2 3 |
1 3 1 |
\(n \leq 10000, q \leq 60000\) 。
原串总长度 \(\leq 100000\) 。
询问串总长度 \(\leq 360000\) 。
时间限制：1000MS 内存限制：131072KB
难度：\(8.0\)
给定一个长度为 \(n\) 且仅包含小写英文字母的字符串 \(S\)。你有一个字符串 \(T\)，初始为空串。
你可以进行 \(n\) 次操作，每次操作你可以在 \(T\) 的前端或末尾加入一个任意字母。记第 \(i\) 次操作后 \(T\) 在 \(S\) 中的出现次数为 \(f_i\)，你需要最大化 \(ans=\sum\limits_i f_i\) 。
第一行一个正整数 \(n\) 。
第二行一个长度为 \(n\) 的字符串 \(S\) 。
一行一个整数，表示 \(ans\) 的最大值。
|
1 2 |
6 abcabc |
|
1 |
9 |
对于 \(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 2 3 4 5 6 7 8 |
7 3 0 2 1 2 1 0 0 1 2 3 4 3 5 4 6 5 7 2 5 |
|
1 |
30 |
\(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\) 。
对于每个字符串输出一行表示答案。
时间限制：1000MS 内存限制：262144KB
出题人：E.Space 难度：\(6.1\)
在这个游戏中一共有 \(n\) 个角色。你需要编写一些关于这些角色的对话内容。
你打算用角色名字的一个非空子序列来作为它的简称。
当然，不同的角色要用不同的字符串作为简称，否则你就变量重名了。
你想确定一个简称的分配方案使得所有角色中最长的简称尽量短。
第一行一个正整数 \(n\)。
接下来 \(n\) 行，每行一个由小写字母组成的字符串，代表一个角色的名字。
不同的角色可能会有相同的名字。
如果不存在一种分配简称的方案满足条件，输出 \(-1\)。
否则第一行输出一个正整数，表示最长的简称的最小长度。
接下来 \(n\) 行每行一个字符串，按顺序表示每个角色的简称。
若有多种方案满足条件，那么你可以输出任意一种。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
11 night nealchen beimingyouyu echo rankinf dntcrybecthlev lagoon cyc alphagem leehwincing clin |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
1 g a m e r b o y l w c |
保证 \(n \leq 300\) ，每个名字的长度不超过 \(300\)。