时间限制：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\)。
时间限制：1000MS 内存限制：131072KB
难度：\(4.0\)
输入长度为 \(n\) 的串 \(S\) ，求 \(S\) 的最长双回文子串 \(T\)，即可将 \(T\) 分为两部分 \(X, Y\)（\(\left|X\right|, \left|Y\right| \geq 1\)），且 \(X, Y\) 都是回文串。
一行由小写英文字母组成的字符串 \(S\)。
一行一个整数，表示最长双回文子串的长度。
|
1 |
baacaabbacabb |
|
1 |
12 |
从第二个字符开始的字符串 aacaabbacabb 可分为 aacaa 与 bbacabb 两部分，且两者都是回文串。
对于 \(100\%\) 的数据， \(2 \leq \left|S\right| \leq 10^5\)。
时间限制：1000MS 内存限制：131072KB
难度：\(7.0\)
给出一个 \(R \times C\) 的矩阵，上面有 \(N\) 个 \(0\)，其他的都是 \(1\)，现在给出这些 \(0\) 的位置，要求求出有多少个子矩阵包含至少一个 \(0\) 。
第一行输入三个整数 \(R\)、\(C\)、\(N\) 。
接下来 \(N\) 行，每行两个整数 \(x\)、\(y\)，表示 \(0\) 的坐标。
输出一个数表示子矩阵的个数。
|
1 2 3 4 |
5 5 3 1 1 1 4 4 4 |
|
1 |
103 |
对于 \(100\%\) 的数据，\(R, C \leq 40000\)，\(N \leq \min\{R \times C,100000\}\)，所有 \(0\) 的位置两两不同且随机生成。
时间限制：2000MS 内存限制：131072KB
出题人：Night 难度：\(6.0\)
有一个序列 \(x_1,x_2,\cdots,x_n\) 。
求有多少个从 \(1,2,\cdots,n\) 中取三个元素的排列 \((a,b,c)\) 满足 \(x_a=x_b-x_c\) 。
由于是排列，所以 \((a,b,c)\) 与 \((c,b,a)\) 视为两组解。
第一行一个整数 \(n\) 表示序列长度。
第二行为 \(n\) 个整数表示序列里的 \(n\) 个数。
一行一个正整数，表示答案。
|
1 2 |
10 1 6 2 9 5 9 2 5 0 5 |
|
1 |
26 |
对于 \(20\%\) 的数据，\(1 \leq n \leq 500\)；
对于 \(45\%\) 的数据，\(1 \leq n \leq 5000\)；
对于 \(100\%\) 的数据，\(1 \leq n \leq 1000000\)，\(0 \leq \left|x_i\right| \leq 100000\) 。
时间限制：2000MS 内存限制：131072KB
难度：\(7.0\)
给一棵树，每条边有权。
求一条简单路径，权值和等于 \(K\) ，且经过边的数量最小。
\(N \leq 200000, K \leq 1000000\) 。
第一行 两个整数 \(n\)，\(k\) 。
第 \(2\)~\(n\) 行 每行三个整数，表示一条无向边的两端和权值（注意点的编号从 \(0\) 开始）。
一个整数，表示最小边数量。
如果不存在这样的路径，输出 \(-1\) 。
|
1 2 3 4 |
4 3 0 1 1 1 2 2 1 3 4 |
|
1 |
2 |