分类： 6.0 ~ 7.0

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

YZOJ P3629 [校内训练20180406]表达式

YZOJ P3629 [校内训练20180406]表达式

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

出题人：zzx         难度：\(6.5\)

  • 题目描述

本题中，我们需要计算一些“Bomb表达式”的结果。比如， “1-2+3” 的结果为 2 。和普通表达式不同的是，Bomb表达式中可能包含一些 “#” 号，会展开一些普通表达式。比如 “(1-2+3)#(3)” 表示 “1-2+3 ”出现了 3 次，将会被展开为 “1-2+31-2+31-2+3”，其结果为 60 。

为了方便理解，下面给出了Bomb表达式（bomb expression）和普通表达式（normal expression）的BNF表示。…

YZOJ P3049 [SHOI2010]Minimum Spanning Tree

YZOJ P3049 [SHOI2010]Minimum Spanning Tree

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

难度：\(6.0\)

  • 题目描述

有一个 \(n\) 个点，\(m\) 条边的无向图，每次可以对这张图进行操作：对于一条边 \((u,v)\)，可以把图中除了这条边以外的边，每一条的权值都减少 \(1\)。

对于某一条编号为 \(e\) 的边，至少需要多少次操作，才能保证其能出现在最小生成树中？

  • 输入格式

第一行输入三个整数 \(n\)、\(m\)、\(e\)。

接下来输入 \(m\) 行，每行输入三个整数，其中第 \(i+1\) 行输入的整数分别为 \(u_i\)、\(v_i\)、\(w_i\)，表示无向图的边的两个端点和边权。

  • 输出格式

输出一个整数表示答案。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(50\%\) 的数据，\(n \leq 300\)，\(m \leq 1000\) 。

对于 \(100\%\) 的数据，\(n \leq 2 \times 10^4\)，\(m \leq 2 \times 10^5\)，\(0 \leq w_i \leq 2\times 10^4\) 。

 

 

 …

YZOJ P3389 [FOI 2018 四校联训 Round 3]消息密匙

YZOJ P3389 [FOI 2018 四校联训 Round 3]消息密匙

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

难度：\(6.0\)

  • 题目描述

已知密匙与一个长度为 \(n\) 的字符串有关，字符串中的字符都来自于字符集 \(\{\text{‘a’..}\text{‘z’}, \text{‘?’}\}\)，每个 \(\text{‘?’}\) 的位置都要被填上一个小写字母，我们定义一个填好的串是合法的当且仅当它满足如下条件：

在输入的 \(m\) 次操作后与这个串操作之前的样子相比没有改变。

一次操作是翻转这个串的第 \(l_i\) 个字符到第 \(r_i\) 个字符。

求出字典序第 \(K\) 小的合法的能被填出的串，因为密码就是它。

  • 输入格式

第一行三个数 \(n,m,k\) 。

第二行一个长度为 \(n\) 的串。

接下来 \(m\) 行每行两个数 \(l_i\) 和 \(r_i\) 。

  • 输出格式

一个串，表示字典序第 \(K\) 小的合法的能被填出的串。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(100\%\) 的数据，保证 \(n,m \leq 5 \times 10^5, k \leq 1 \times 10^{18}\) 。

 

 

 …

YZOJ P3361 [校内训练20171117]数点问题

YZOJ P3361 [校内训练20171117]数点问题

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

出题人：zzx      难度：\(6.0\)

  • 题目描述

\(k\) 维空间内有两个点集 \(A=\{X_1,X_2,\ldots,X_m\}\)，\(B=\{Y_1,Y_2,\ldots,Y_n\}\)，每个点的坐标是一个 \(k\) 元组 \((x_1,x_2,\ldots,x_k)\)。我们称点 \(X(x_1,x_2,\ldots,x_k)\) 控制点 \(Y(y_1,y_2,\ldots,y_k)\) 当且仅当 \(\forall 1\le i\le k,x_i>y_i\)，记为 \(X>Y\)。数点问题是要求计算点 \(X_i\) 能控制 \(B\) 中的点数 \(c_i\)，即 \(c_i=\left| \{Y \in B\ |\ X_i > Y\} \right|\)。

  • 编程任务

对于给定的点集 \(A\) 和 \(B\)，求出对于所有 \(1\le i\le m\) 的 \(c_i\) 的值。

  • 输入格式

第一行有三个正整数\(m\)、\(n\) 和 \(k\)，分别表示集合 \(A\) 和 \(B\) 的基数及维数。接下来的 \(m+n\) 行依次给出点 \(X_1 , X_2 ,\ldots, X_m ,Y_1 ,Y_2 ,\ldots,Y_n\)，每个点的坐标用一行 \(k\) 个整数 \(x_1 , x_2 ,\ldots, x_k\) 描述，所有坐标在 \(int\) 范围内。

  • 输出格式

将计算出的 \(c_1 ,c_2 ,\ldots,c_m\) 依次输出到文件中，每个 \(c_i\) 输出 \(1\) 行。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于数据点 \(1\)，\(n,m\le 200,000\)，\(k=1\)…

YZOJ P3791 餐馆

YZOJ P3791 餐馆

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

难度：\(6.0\)

  • 题目描述

在一条东西向的街道上有 \(n\) 个餐馆，从西向东编号为 \(1\) 至 \(n\)，第 \(i\) 个餐馆和第 \(i+1\) 个餐馆的距离为 \(a_i\) 。

吃货小W喜欢到这条街道的餐馆里吃饭。现在，小W得到了 \(m\) 张餐票，每张餐票可以用于在街道上的任一餐馆里吃一餐。在第 \(i\) 个餐馆中，使用第 \(j\) 张餐票吃饭，可以获得的美味度为 \(b_{i,j}\) 。注意，每张餐票最多用一次，但在同一餐馆内可以使用任意多张餐票。

小W打算用完这 \(m\) 张餐票。他可以选择任一餐馆作为起点，每次吃饭时，可以选择一个餐馆，然后从当前位置（上次吃饭的地点，如果不存在则为起点）出发前往该餐馆并用任意一张未用过的餐票吃一餐，直到吃完 \(m\) 餐为止。小W希望最大化每次吃饭的美味度之和减去路上经过的总路程的值。

  • 输入格式

输入第一行包含两个正整数 \(n,m\) 。

第二行包含 \(n-1\) 个正整数 \(a_1,a_2,\cdots,a_{n-1}\) 。

接下来 \(n\) 行，每行包含 \(m\) 个正整数，其中第 \(i\) 行第 \(j\) 个数为 \(b_{i,j}\) 。

  • 输出格式

输出一行一个整数，表示所求的最大值。

  • 样例输入

  • 样例输出

  • 样例说明

最优方案如下：以餐馆 \(1\) 为起点，在餐馆 \(1\) 使用第 \(1\) 张餐票、第 \(3\) 张餐票，然后前往餐馆 \(2\) 使用第 \(2\) 张餐票、第 \(4\) 张餐票。

  • 数据规模与约定

对于所有数据，\(nm \leq 10^6\)，\(n \geq 2\)，\(a_i, b_{i, j} \leq 10^9\) 。

 

 

 

Source：ARC067 F – Yakiniku …