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\) 组(坐标,时间)询问求出的结果。

  • 样例 1 输入


Read the rest

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\)。如果存在合法方案,第二行输出替换后的括号序列。若有多种替换方案的代价之和最小,可以输出任意一种。

  • 输入示例

  • 输出示例


Read the rest

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\) 场游戏中如何安排赛车的使用。如果存在多组解,输出其中任意一组即可。

  • 样例输入


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

 

 

 …