分类： 难度

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…

YZOJ P3752 序列求差问题

YZOJ P3752 序列求差问题

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

  • 输出格式

一行一个正整数，表示答案。

  • 样例输入

  • 样例输出

  • 数据规模与约定

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

 

 

 …

YZOJ P3924 [IOI2011]Race

YZOJ P3924 [IOI2011]Race

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

难度：\(7.0\)

  • 题目描述

给一棵树，每条边有权。

求一条简单路径，权值和等于 \(K\) ，且经过边的数量最小。

\(N \leq 200000, K \leq 1000000\) 。

  • 输入格式

第一行 两个整数 \(n\)，\(k\) 。

第 \(2\)~\(n\) 行 每行三个整数，表示一条无向边的两端和权值（注意点的编号从 \(0\) 开始）。

  • 输出格式

一个整数，表示最小边数量。

如果不存在这样的路径，输出 \(-1\) 。

  • 样例输入

  • 样例输出

 

 

 

Source: BZOJ 2599…

YZOJ P2872 [POJ 1637]Sightseeing tour

YZOJ P2872 [POJ 1637]Sightseeing tour

Time Limit：1000MS      Memory Limit：131072KB

Difficulty: \(6.0\)

  • Description

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.

  • Input

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, …

YZOJ P2163 [THUSC2015]解密运算

YZOJ P2163 [THUSC2015]解密运算

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

难度：\(7.0\) （自评）

  • 题目描述

对于一个长度为 \(N\) 的字符串，我们在字符串的末尾添加一个特殊的字符 “.” 。之后将字符串视为一个环，从位置 \(1,2,3,\cdots,N+1\) 为起点读出 \(N+1\) 个字符，就能得到 \(N+1\) 个字符串。

比如对于字符串 “ABCAAA”，我们可以得到这 \(N+1\) 个串：

接着我们对得到的这 \(N+1\) 个串按字典序从小到大进行排序（注意特殊字符 “.” 的字典序小于任何其他的字符）结果如下：

最后，将排序好的 \(N+1\) 个串的最后一个字符取出，按照顺序排成一个新的字符串，也就是上面这个表的最后一列，就是加密后的密文 “AAAC.AB” 。

请通过加密后的密文求出加密前的字符串。

  • 输入格式

第一行有两个整数 \(N, M\)，分别表示加密前的字符串长度和字符集大小，其中字符用整数 \(1,2,3,\cdots,M\) 编号，添加的特殊字符 “.” 用 \(0\) 编号。

第二行为 \(N+1\) 个整数，表示加密后的字符串。

  • 输出格式

输出仅一行，包含 \(N\) 个整数，用空格隔开，依次表示加密前字符串中每个字符的编号。

  • 样例输入

  • 样例输出

  • 数据规模与约定

\(N,M \leq 200000\) 。

 

 …

YZOJ P3933 [Baltic2004]sequence

YZOJ P3933 [Baltic2004]sequence

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

难度：\(6.0\)

  • 题目描述

给定一个序列 \(t_1,t_2,\cdots,t_n\)，求一个递增序列 \(z_1<z_2<\cdots<z_n\)，使得 \(R=\sum\limits_{i=1}^{n}{\left|t_i-z_i\right|}\) 的值最小。

本题中，我们只需要求出这个最小的 \(R\) 值。

  • 输入格式

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

第二行到第 \(n+1\) 行，每行一个整数，第 \(k+1\) 行为 \(t_k\)

  • 输出格式

一个整数 \(R\)

  • 样例输入

  • 样例输出

  • 样例说明

所求的 \(z\) 序列为 \(6,7,8,13,14,15,18\)，\(R=13\)

  • 数据规模与约定

对于 \(100\%\) 的数据，\(1 \leq n \leq 10^6\)，\(1 \leq t_i \leq 2\times 10^9\) 。

 

 

Source: BZOJ 1367…