YZOJ P2905 [PA2014]Druzyny

YZOJ P2905 [PA2014]Druzyny

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

难度：\(8.0\)

  • 题目描述

在之前的某次校内训练中，zzx 出了一道神奇的题目：给出 \(n\) 个人，要求将所有人分成若干个组，第 \(i\) 个人所在的组的人数必须在 \([l_i, r_i]\) 之间，判断是否存在可行解。

OI组的神犇们决定把这题改造一下：

dick32165401：改成只有编号连续的的一段才可以分一组。

runzhe2000：判定可行解可能会被爆搜水过，最大化分的组数就不那么容易水过了。

E.Space：不仅要最大化组数，还要求出最大化组数的方案数。

ct：数据范围就出100万好了。

于是这题就被这么造好了。

  • 输入格式

第一行 \(n\)，\(1 \leq n \leq 1000000\) 。

接下来 \(n\) 行，每行 \(l_i,r_i\)，\(1 \leq l_i \leq r_i \leq 1000000\) 。

  • 输出格式

若不存在合法的方案，仅输出一行 \(-1\) 。

否则输出一行两个整数，分别表示组数的最大值和组数取最大值的方案数模 \(10^9+7\) 。

  • 样例输入

  • 样例输出

 

 

 

Source: BZOJ 3711

膜拜上方所有dalao %%%%%%%%%%%%%%%%%%

像我这种菜鸡看到这种神仙题只会爆零QAQ…

YZOJ P3098 [JLOI2016]成绩比较

YZOJ P3098 [JLOI2016]成绩比较

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

难度：\(6.0\)

  • 题目描述

G系共有 \(n\) 位同学，\(m\) 门必修课。这 \(n\) 位同学的编号为 \(0\) 到 \(n-1\) 的整数，其中B神的编号为 \(0\) 号。

这 \(m\) 门必修课编号为 \(0\) 到 \(m-1\) 的整数。一位同学在必修课上可以获得的分数是 \(1\) 到 \(U_i\) 中的一个整数。如果在每门课上 A 获得的成绩均小于等于 B 获得的成绩，则称 A 被 B 碾压。

在B神的说法中，G系共有 \(k\) 位同学被他碾压（不包括他自己），而其他 \(n-k-1\) 位同学则没有被他碾压。D神查到了B神每门必修课的排名。这里的排名是指：如果B神某门课的排名为 \(R\)，则表示有且仅有 \(R-1\) 位同学这门课的分数大于B神的分数，有且仅有 \(n-R\) 位同学这门课的分数小于等于B神（不包括他自己）。

我们需要求出全系所有同学每门必修课得分的情况数，使其既能满足B神的说法，也能符合D神查到的排名。这里两种情况不同当且仅当有任意一位同学在任意一门课上获得的分数不同。

你不需要像D神那么厉害，你只需要计算出情况数模 \(10^9+7\) 的余数就可以了。

  • 输入格式

第一行包含三个正整数 \(n, m, k\)，分别表示G系的同学数量（包括B神），必修课的数量和被B神碾压的同学数量。

第二行包含 \(m\) 个正整数，依次表示每门课的最高分 \(U_i\) 。

第三行包含 \(m\) 个正整数，依次表示B神在每门课上的排名 \(R_i\) 。保证 \(1 \leq R_i \leq n\)。

数据保证至少有 \(1\) 种情况使得B神说的话成立。\(n \leq 100, m \leq 100, U_i \leq 10^9\) 。

  • 输出格式

输出仅包括一行一个整数，表示成绩情况数对 \(10^9+7\) 取模的结果。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(30\%\) 的数据，\(n, m \leq 20\)，\(U_i \leq 100\)；

对于 \(100\%\) 的数据，\(n,m \leq 100\)，\(U_i \leq 10^9\)，\(1 \leq R_i \leq n\)，\(0 \leq k < n\) …

YZOJ P3527 [FJOI2018D1T3]城市路径问题

YZOJ P3527 [FJOI2018D1T3]城市路径问题

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

难度：\(6.5\)

  • 题目描述

给出一张 \(n\) 个点的有向图 \(G(V, E)\) 。对于任意两个点 \(u, v\) （\(u\) 可以等于 \(v\) ），\(u\) 向 \(v\) 的连边数为：\(\sum\limits_{i=1}^k {out[u, i] \times in[v, i]}\) 。

给定 \(k\) 和数组 \(out, in\) ，现在有 \(m\) 个询问，每次询问给出三个参数 \(u, v, d\)，你需要回答从节点 \(u\) 出发，经过不超过 \(d\) 条边到达节点 \(v\) 的路径有多少种。

答案对 \(10^9+7\) 取模。

  • 输入格式

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

接下来 \(n\) 行，第 \(i\) 行有 \(2k\) 个整数，前 \(k\) 个整数描述 \(out[i][]\)，后 \(k\) 个数描述 \(in[i][]\) 。

接下来一行一个整数 \(m\) 。

接下来 \(m\) 行，每行三个整数 \(u, v, d\)，描述一组询问。

  • 输出格式

对于每个询问，输出一个方案数。由于答案可能太大，输出其除以 \(10^9+7\) 后的余数。…

YZOJ P3033 背包

YZOJ P3033 背包

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

出题人：chj2001             难度：\(5.4\)

  • 题目描述

存在 \(n\) 种物品，其中第 \(i\) 种物品的价值为 \(a_i\) ，最多可以用 \(b_i\) 件，求从这些物品中选取若干件（不能为 \(0\) 件），得到的总价值为 \(9\) 的倍数的方案。

需要分别计算每种物品中，每件之间有区别的方案数和没有区别的方案数。

（即每种物品按照 \(1,2,3, \cdots ,b_i\) 编号的方案数和不编号的方案数。）

  • 输入格式

第一行输入一个数 \(n\) 。

接下来 \(n\) 行，每行两个数 \(a_i, b_i\) 。

  • 输出格式

输出共两行，每行各包括一个数，分别表示对于每种物品视为不同的时的方案数和视为相同的时的方案数。有的时候方案数可能很大，你需要将它对 \(10^9+7\) 取模。

方案数均不考虑顺序，如 \(2, 3, 4\) 和 \(4, 3, 2\) 是同一种方案。

如果无法做到则输出 \(0\) 。

  • 样例输入

  • 样例输出

  • 样例说明

不考虑同种物品之间的区别，一共有 \(2\) 种不同的方案凑出 \(9\) 的倍数，即 \(3, 2, 2, 2\) 和 \(3, 3, 3\) 。

考虑同种和果子的区别时，一共有 \(C_3^1 \times C_3^3 = 3\) 种不同的方案凑出 \(3, 2, 2, 2\)，\(C_3^3=1\) 种方案凑出 \(3, 3, 3\)，因此总共有 \(4\) 种方案。

  • 数据规模与约定

对于 \(40\%\) 的数据，\(n \le 1000 , a_i \le 100 , b_i \le 100\) 。

对于 \(100\%\) 的数据，\(1 \le n \le 10^5 , 1 \le a_i \le 90000 , 1 \le b_i \le …

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\) 的结果。

  • 样例输入

…