YZOJ P2049 [FJOI2013]相似基因序列问题

YZOJ P2049 [FJOI2013]相似基因序列问题

时间限制：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\)。

  • 样例输入

  • 样例输出

 

 

 …

YZOJ P2443 回文子序列

YZOJ P2443 回文子序列

时间限制：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\) 。

字符串中仅包含小写字母。

 

 

 …

YZOJ P3897 Sevenk Love Oimaster

YZOJ P3897 Sevenk Love Oimaster

时间限制：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…

YZOJ P3847 [2018省队集训]Ernd

YZOJ P3847 [2018省队集训]Ernd

时间限制：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\) 。

 

 

 …

YZOJ P3939 [HAOI2016]找相同字符

YZOJ P3939 [HAOI2016]找相同字符

时间限制：1000MS      内存限制：262144K

难度：\(6.5\)

  • 题目描述

给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。

两个方案不同当且仅当这两个子串中有一个位置不同。

  • 输入格式

两行，两个字符串 \(s_1, s_2\)，\(1 \leq \left|s_1\right|, \left|s_2\right|\leq 200000\)，字符串中只有小写字母。

  • 输出格式

输出一个整数表示答案

  • 样例输入

  • 样例输出

 

 

 

Source: BZOJ 4566…

YZOJ P2242 [ZJOI 2015]Substring

YZOJ P2242 [ZJOI 2015]Substring

时间限制：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\) 。

 

 

 

Source: BZOJ 3926…

YZOJ P3750 [校内训练20180529]字符串的频度

YZOJ P3750 [校内训练20180529]字符串的频度

时间限制：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\) 。…

YZOJ P4259 [FJWC 2019] 不同的缩写

YZOJ P4259 [FJWC 2019] 不同的缩写

时间限制：1000MS      内存限制：262144KB

出题人：E.Space      难度：\(6.1\)

  • 题目描述

在这个游戏中一共有 \(n\) 个角色。你需要编写一些关于这些角色的对话内容。

你打算用角色名字的一个非空子序列来作为它的简称。

当然，不同的角色要用不同的字符串作为简称，否则你就变量重名了。

你想确定一个简称的分配方案使得所有角色中最长的简称尽量短。

  • 输入格式

第一行一个正整数 \(n\)。

接下来 \(n\) 行，每行一个由小写字母组成的字符串，代表一个角色的名字。

不同的角色可能会有相同的名字。

  • 输出格式

如果不存在一种分配简称的方案满足条件，输出 \(-1\)。

否则第一行输出一个正整数，表示最长的简称的最小长度。

接下来 \(n\) 行每行一个字符串，按顺序表示每个角色的简称。

若有多种方案满足条件，那么你可以输出任意一种。

  • 样例输入

  • 样例输出

  • 数据规模与约定

保证 \(n \leq 300\) ，每个名字的长度不超过 \(300\)。

 

 

 …

YZOJ P3906 最长双回文串

YZOJ P3906 最长双回文串

时间限制：1000MS      内存限制：131072KB

难度：\(4.0\)

  • 题目描述

输入长度为 \(n\) 的串 \(S\) ，求 \(S\) 的最长双回文子串 \(T\)，即可将 \(T\) 分为两部分 \(X, Y\)（\(\left|X\right|, \left|Y\right| \geq 1\)），且 \(X, Y\) 都是回文串。

  • 输入格式

一行由小写英文字母组成的字符串 \(S\)。

  • 输出格式

一行一个整数，表示最长双回文子串的长度。

  • 样例输入

  • 样例输出

  • 样例说明

从第二个字符开始的字符串 aacaabbacabb 可分为 aacaa 与 bbacabb 两部分，且两者都是回文串。

  • 数据规模与约定

对于 \(100\%\) 的数据， \(2 \leq \left|S\right| \leq 10^5\)。

 

 

Source: BZOJ 2565…

YZOJ P2358 [ZJOI 2012]Naive – Matrix

YZOJ P2358 [ZJOI 2012]Naive – Matrix

时间限制：1000MS      内存限制：131072KB

难度：\(7.0\)

  • 题目描述

给出一个 \(R \times C\) 的矩阵，上面有 \(N\) 个 \(0\)，其他的都是 \(1\)，现在给出这些 \(0\) 的位置，要求求出有多少个子矩阵包含至少一个 \(0\) 。

  • 输入格式

第一行输入三个整数 \(R\)、\(C\)、\(N\) 。

接下来 \(N\) 行，每行两个整数 \(x\)、\(y\)，表示 \(0\) 的坐标。

  • 输出格式

输出一个数表示子矩阵的个数。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(100\%\) 的数据，\(R, C \leq 40000\)，\(N \leq \min\{R \times C,100000\}\)，所有 \(0\) 的位置两两不同且随机生成。

 

 

 

Source: BZOJ 2658…