Processing math: 0%

月度归档： 2019 年 5 月

YZOJ P3706 [APIO2018]新家

YZOJ P3706 [APIO2018]新家

时间限制：5000MS      内存限制：1048576KB

难度：7.0

  • 题目描述

五福街是一条笔直的道路，这条道路可以看成一个数轴，街上每个建筑物的坐标都可以用一个整数来表示。

小明是一位时光旅行者，他知道在这条街上，在过去现在和未来共有 n 个商店出现。第 i 个商店可 以使用四个整数 x_i , t_i , a_i , b_i 描述，它们分别表示：商店的坐标、商店的类型、商店开业的年份、商店关闭的年份。

小明希望通过时光旅行，选择一个合适的时间，住在五福街上的某个地方。他给出了一份他可能选择的列表，上面包括了 q 个询问，每个询问用二元组 （坐标，时间）表示。第 i 对二元组用两个整数 l_i , y_i 描述，分别表示选择的地点 l_i 和年份 y_i 。

现在，他想计算出在这些时间和地点居住的生活质量。他定义居住的不方便指数为：在居住的年份，离 居住点最远的商店类型到居住点的距离。类型 t 的商店到居住点的距离定义为：在指定的年份，类型 t 的所有营业的商店中，到居住点距离最近的一家到居住点的距离。我们说编号为 i 的商店在第 y 年在营业当且仅当 a_i \leq y \leq b_i 。注意，在某些年份中，可能在五福街上并非所有 k 种类型的商店都有至少一家在营业。在这种情况下，不方便指数定义为 -1。

你的任务是帮助小明求出每对（坐标，时间）二元组居住的不方便指数。

  • 输入格式

第一行包含三个整数 n,k 和 q ，分别表示商店的数量、商店类型的数量和（坐标，时间）二元组的数量（1 \le n, q \le 3 \times 10^5 , 1 \le k \le n）

接下来 n 行，每行包含四个整数 x_i , t_i , a_i 和 b_i 用于描述一家商店，意义如题面所述 （1 \le x_i , a_i , b_i \le 10^8 , 1 \le t_i \le k, a_i \le b_i）。

接下来 q 行，每行包含两个整数 l_i 和 y_i ，表示一组（坐标，时间）查询 （1 \le l_i , y_i \leq 10^8 ）。

  • 输出格式

输出一行，包含 q 个整数，依次表示对于 q 组（坐标，时间）询问求出的结果。…

YZOJ P1310 [省队训练][NOI模拟7]车的放置

YZOJ P1310 [省队训练][NOI模拟7]车的放置

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

难度：8.0

  • 题目描述

有 N 个 1 \times h[i] 的矩形小棋盘，底边边长为 1，在一条直线上拼成了一个畸形的棋盘。

高度 h[i] 给出，第 i 个矩形的高为 h[i]，例如 h = [3, 2, 4, 2] 的图形如下：

若两个车相互攻击仅当它们在同一列，或在同一行且在这一行它们之间棋盘格子都是存在的，例如上图中 a 与 b 是相互不攻击的，c 与 d，b 与 c 均为相互攻击的。

现在要在这棋盘上放置恰好 K 个相互不攻击的车，问有多少种方案。

  • 输入格式

输入第 1 行包括两个正整数 N，K，表示了棋盘的列数和放的车数。

第 2 行包含 N 个正整数，表示了棋盘每列的高度。

  • 输出格式

输出包括一个非负整数，表示有多少种放置的方案，输出答案 \mod 1000000007 后的结果即可。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 100\% 的数据，有 N \leq 500，K \leq 500，h[i]  \leq 1000000 。

 

 

 …

YZOJ P3384 [校内训练20171201]括号替换问题

YZOJ P3384 [校内训练20171201]括号替换问题

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

难度：5.0

  • 问题描述

这里有一个关于合法的括号序列的问题。如果插入“+” 和 “1” 到一个括号序列，我们能得到一个正确的数学表达式，我们就认为这个括号序列是合法的。例如，序列 “(())()”, “()” 和 “(()(()))” 是合法的，但是 “)(“, “(()” 和 “(()))(” 是不合法的。我们有一个仅由 “(”，“)” 和 “?” 组成的括号序列，你必须将 “?” 替换成括号，从而得到一个合法的括号序列。

对于给定仅由 “(”，“)” 和 “?” 组成的括号序列，你需要将 “?” 替换成括号，得到一个合法的括号序列，同时需要使得代价之和最小。

  • 数据输入

文件有多个测试实例（\leq 5）。每个实例的第一行有 1 个正整数 n，（1 \leq n \leq 100000），表示括号序列的长度为 n。第二行是一个长度为 n 的字符串，表示输入的括号序列，字符串仅由 “(”，“)” 和 “?” 组成。接下来 m 行，m 是字符串中 “?” 的个数，每一行包含两个整数 a_i 和 b_i（1 \leq a_i,b_i \leq 1000000），a_i 是将第 i 个 “?” 替换成左括号的代价，b_i 是将第 i 个 “?” 替换成右括号的代价。文件的最后一行有一个 0 表示结束。

  • 结果输出

将计算出的每个测试实例的答案依次输出到文件中。每个测试实例第一行输出一个整数，表示最小代价和。如果不存在合法方案，输出 -1。如果存在合法方案，第二行输出替换后的括号序列。若有多种替换方案的代价之和最小，可以输出任意一种。…

YZOJ P3195 [NOI2017]游戏

YZOJ P3195 [NOI2017]游戏

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

难度： 6.4

  • 题目描述

小 L 计划进行 n 场游戏，每场游戏使用一张地图，小 L 会选择一辆车在该地图上完成游戏。

小 L 的赛车有三辆，分别用大写字母 A、B、C 表示。地图一共有四种，分别用小写字母 x、a、b、c 表示。其中，赛车 A 不适合在地图 a 上使用，赛车 B 不适合在地图 b 上使用，赛车 C 不适合在地图 c 上使用，而地图 x 则适合所有赛车参加。适合所有赛车参加的地图并不多见，最多只会有 d 张。

n 场游戏的地图可以用一个小写字母组成的字符串描述。例如：S=\underline{\mathrm{xaabxcbc}} 表示小 L 计划进行 8 场游戏，其中第 1 场和第 5 场的地图类型是 x，适合所有赛车，第 2 场和第 3 场的地图是 a，不适合赛车 A，第 4 场和第 7 场的地图是 b，不适合赛车 B，第 6 场和第 8 场的地图是 c，不适合赛车 C 。

小 L 对游戏有一些特殊的要求，这些要求可以用四元组 (i,h_i,j,h_j) 来描述，表示若在第 i 场使用型号为 h_i 的车子，则第 j 场游戏要使用型号为 h_j 的车子。

你能帮小 L 选择每场游戏使用的赛车吗？如果有多种方案，输出任意一种方案。如果无解，输出 “-1”（不含双引号）。

  • 输入格式

输入第一行包含两个非负整数 n,d 。

输入第二行为一个字符串 S 。

n,d,S 的含义见题目描述，其中 S 包含 n 个字符，且其中恰好 d 个为小写字母 x 。

输入第三行为一个正整数 m，表示有 m 条用车规则。接下来 m 行，每行包含一个四元组 i,h_i,j,h_j ，其中 i,j 为整数，h_i,h_j 为字符 A 、B 或 C，含义见题目描述。

  • 输出格式

输出一行。

若无解，输出 “-1”（不含双引号）。

若有解，则包含一个长度为 n 的仅包含大写字母 A、B、C 的字符串，表示小 L 在这 n 场游戏中如何安排赛车的使用。如果存在多组解，输出其中任意一组即可。…

YZOJ P4258 [FJWC2019]原样输出

YZOJ P4258 [FJWC2019]原样输出

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

出题人：E.Space        难度：7.0

  • 题目描述

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

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

它没法输出换行符了。

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

比如 orzxxxxx 可能会变成 rzxx、orz、x 或者空串。

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

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

  • 输入格式

第一行一个正整数 n，表示（题面中）输入文件的行数。

接下来 n 行，表示输入文件的内容。保证这 n 行中每行的每个字符是 A、C、G、T 四种字符中的一种。

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

  • 输出格式

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

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

  • 样例输入

…

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 。

 

 

 …