YZOJ P4578 [CSP-S 2019 四校联训 Round 1]树上排列

YZOJ P4578 [CSP-S 2019 四校联训 Round 1]树上排列

时间限制: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\) 表示操作种类。

  • 输出格式

对于每一个操作 \(1\) 如果符合条件,输出 Yes ,否则输出 No

  • 样例输入


Read the rest

YZOJ P4258 [FJWC2019]原样输出

YZOJ P4258 [FJWC2019]原样输出

时间限制:4000MS      内存限制:262144KB

出题人:E.Space        难度:\(7.0\)

  • 题目描述

它会把输入按行读入,原封不动地复制到输出中去。

但是在一次更新以后,它的程序出了一些问题。

它没法输出换行符了。

并且,读入的时候,总会莫名其妙地随机漏掉开头和结尾的若干个字符,甚至整行都会漏掉。

比如 orzxxxxx 可能会变成 rzxxorzx 或者空串。

现在你找到一份输入文件丢给它,你想知道它的输出可能有多少种情况,以及每种情况分别是什么。

由于你找到的输入文件全部来自之前的福建省选,所以所有的输入文件每行只可能包含 ACGT 四种字符。

  • 输入格式

第一行一个正整数 \(n\),表示(题面中)输入文件的行数。

接下来 \(n\) 行,表示输入文件的内容。保证这 \(n\) 行中每行的每个字符是 ACGT 四种字符中的一种。

接下来一个整数 \(k, (0 \leq k \leq 1)\),具体含义详见输出格式。

  • 输出格式

若 \(k=0\),你需要输出一行,表示输出的可能情况个数模 \(10^9+7\) 的结果。

若 \(k=1\),你需要按照字典序从小到大输出所有可能的输出情况,一行一个字符串,最后一行输出输出的可能情况个数模 \(10^9+7\) 的结果。

  • 样例输入

  • 样例输出


Read the rest

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\) 。

  • 样例输入

  • 样例输出


Read the rest

YZOJ P4259 [FJWC 2019] 不同的缩写

YZOJ P4259 [FJWC 2019] 不同的缩写

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

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

  • 题目描述

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

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

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

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

  • 输入格式

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

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

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

  • 输出格式

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

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

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

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

  • 样例输入

  • 样例输出

  • 数据规模与约定

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

 

 

 …