分类： 数学

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

YZOJ P3846 [2018省队集训]Yist

YZOJ P3846 [2018省队集训]Yist

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

难度： \(7.0\)

  • 题目描述

有一个 \(n\) 个点 \(m\) 条边的无向图，结点从 \(1\) 到 \(n\) 标号，点 \(u\) 的初始权值为 \(w_u\)。你可以对任意结点 \(u\) 进行操作，将你的得分（初始为 \(0\)）加上 \(\sum_\limits{(u,v) \in E}w_v\) ，并将 \(w_u\) 除以 \(2\) 。

给定一个长度为 \(k\) 的结点序列 \(s_1,s_2,\cdots,s_k\) （\(1 \leq s_i \leq n\)），在一轮操作中，你需要依次对 \(s_1,s_2,\cdots,s_k\) 进行操作。你想知道，在进行了无限轮操作后，你得分的极限是多少。

显然答案一定可以表示成 \(P/Q\) 的形式，你需要输出 \(P \times Q^{-1}\) 在模 \(998244353\) 意义下的值。特别的，如果得分并不收敛，输出 \(-1\) 。

  • 输入格式

本题有多组数据，请读入到文件结束。

对于每组数据，第一行三个整数 \(n,m,k\) ，含义如题所述。

第二行 \(n\) 个整数 \(w_1,w_2,\cdots,w_n\)，表示结点的初始权值。

第三行 \(k\) 个正整数 \(s_1,s_2,\cdots,s_k\) 。

接下来 \(m\) 行，每行两个整数 \(u,v\)，描述了一条无向边。

  • 输出格式

对于每组数据，输出一行一个整数，表示答案。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(20\%\) 的数据，\(n,m \leq 5\)，\(k \leq 10\)；

对于 \(40\%\) 的数据，\(n,m \leq 1000\)，\(k \leq 2000\)；

对于另外 \(20\%\) 的数据，数据为随机生成；

对于 \(100\%\) 的数据，\(1 \leq …

YZOJ P2697 画圆

YZOJ P2697 画圆

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

难度： \(5.1\)

  • 题目描述

在初中数学课上，\(Alkri\) 学习了圆的相关知识，他对与圆有关的问题更加感兴趣了。

\(Alkri\) 想在平面直角坐标系的第一象限中依次画 \(n\) 个与两坐标轴均相切的圆，其中，第 \(1\) 个圆的半径为 \(r\)，之后的每个圆都比上一个圆大，且与上一个圆相切，也就是说，对所有整数 \(2 \leq i \leq n\)，第 \(i\) 个圆的半径大于第 \(i-1\) 个圆的半径且与第 \(i-1\)个圆相切。

例如当 \(n=3\) 时，三个圆 \(C_1, C_2, C_3\) 如下图所示（由于 \(C_3\) 比较大，未画完整）：

现在，\(Alkri\) 很好奇：第 \(n\) 个圆的半径 \(R\) 到底有多大？他知道 \(R\) 不一定是整数（真聪明！），并且可能非常大，所以只需要你保留 \(R\) 的整数部分（向下取整）的末尾 \(p\) 位数字即可。

  • 输入格式

输入仅一行，包含三个整数 \(n\)，\(r\)，\(p\)，意义如题目所述。

  • 输出格式

输出仅一行一个整数，表示第 \(n\) 个圆的半径 \(R\) 的整数部分的末尾 \(p\) 位。注意当 \(R\) 的整数部分实际位数超过 \(p\) 时需要输满 \(p\) 位（即需要保留前导0），如果实际位数不满 \(p\) 位则不用补前导 0 。

  • 输入样例

  • 输出样例

  • 样例说明

第 \(10\) 个圆的半径整数部分为 \(38808989\)，要求输出整数部分的末尾 \(5\) 位数，因此输出 \(08989\) 。注意保留前导 0 。

  • 数据规模与约定

 

 

 …