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=AATGCCTAGGCY=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 可分为 aacaabbacabb 两部分,且两者都是回文串。

  • 数据规模与约定

对于 \(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…