时间限制：1000MS 内存限制：262144K
难度：\(6.5\)
给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。
两个方案不同当且仅当这两个子串中有一个位置不同。
两行，两个字符串 \(s_1, s_2\)，\(1 \leq \left|s_1\right|, \left|s_2\right|\leq 200000\)，字符串中只有小写字母。
输出一个整数表示答案
|
1 2 |
aabb bbaa |
|
1 |
10 |
Source: BZOJ 4566… Read the rest
时间限制：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\) 。
Source: BZOJ 3926… Read the rest
时间限制：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\) 。… Read the rest
时间限制：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\)。
Source: BZOJ 2565… Read the rest
时间限制：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\) 的位置两两不同且随机生成。
Source: BZOJ 2658… Read the rest
时间限制：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 |
Source: BZOJ 2599… Read the rest
Time Limit：1000MS Memory Limit：131072KB
Difficulty: \(6.0\)
The city executive board in Lund wants to construct a sightseeing tour by bus in Lund, so that tourists can see every corner of the beautiful city. They want to construct the tour so that every street in the city is visited exactly once. The bus should also start and end at the same junction. As in any city, the streets are either one-way or two-way, traffic rules that must be obeyed by the tour bus. Help the executive board and determine if it’s possible to construct a sightseeing tour under these constraints.
On the first line of the input is a single positive integer n, telling the number of test scenarios to follow. Each scenario begins with a line containing two positive integers m and s, … Read the rest
时间限制：1000MS 内存限制：131072KB
难度：\(7.0\) （自评）
对于一个长度为 \(N\) 的字符串，我们在字符串的末尾添加一个特殊的字符 “.” 。之后将字符串视为一个环，从位置 \(1,2,3,\cdots,N+1\) 为起点读出 \(N+1\) 个字符，就能得到 \(N+1\) 个字符串。
比如对于字符串 “ABCAAA”，我们可以得到这 \(N+1\) 个串：
|
1 2 3 4 5 6 7 |
ABCAAA. BCAAA.A CAAA.AB AAA.ABC AA.ABCA A.ABCAA .ABCAAA |
接着我们对得到的这 \(N+1\) 个串按字典序从小到大进行排序（注意特殊字符 “.” 的字典序小于任何其他的字符）结果如下：
|
1 2 3 4 5 6 7 |
.ABCAAA A.ABCAA AA.ABCA AAA.ABC ABCAAA. BCAAA.A CAAA.AB |
最后，将排序好的 \(N+1\) 个串的最后一个字符取出，按照顺序排成一个新的字符串，也就是上面这个表的最后一列，就是加密后的密文 “AAAC.AB” 。
请通过加密后的密文求出加密前的字符串。
第一行有两个整数 \(N, M\)，分别表示加密前的字符串长度和字符集大小，其中字符用整数 \(1,2,3,\cdots,M\) 编号，添加的特殊字符 “.” 用 \(0\) 编号。
第二行为 \(N+1\) 个整数，表示加密后的字符串。
输出仅一行，包含 \(N\) 个整数，用空格隔开，依次表示加密前字符串中每个字符的编号。
|
1 2 |
6 3 1 1 1 3 0 1 2 |
|
1 |
1 2 3 1 1 1 |
\(N,M \leq 200000\) 。