分类： 6.0 ~ 7.0

YZOJ P4643 [BJOI2018] 链上二次求和

[BJOI2018] 链上二次求和

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

难度：\(6.2\)

  • 题目描述

YJC 有一棵 \(n\) 个节点的树， \(i\)、\(i+1\) （\(1 \leq i < n\)）节点间有一条边，第 \(i\) 个点的权值为整数 \(a_i\) 。

现在他有 \(m\) 个询问：

操作 \(1\)（修改）：给定树上两个节点 \(u\)、\(v\) 和一个整数 \(d\)，表示将树上 \(u\) 到 \(v\) 唯一的简单路径上每个点权值都加上 \(d\)。

操作 \(2\)（询问）：给定两个正整数 \(l\)、\(r\) ，表示求树上所有节点个数大于等于 \(l\) 且小于等于 \(r\) 的简单路径节点权值和之和。由于答案很大，只用输出对质数 \(1000000007\) 取模的结果即可。

一条节点个数为 \(k\) 的简单路径节点权值和为这条上所有 \(k\) 个节点（包括端点）的权值之和，而本题中要求是对所有满足要求的简单路径，求这一权值和的和。

树边是无向的，所以路径也是无向的，即点 \(1\) 到点 \(2\) 的路径与点 \(2\) 到点 \(1\) 的路径是同一条，不要重复计算。

  • 输入格式

输入第一行包含两个正整数 \(n\)、\(m\)，分别表示节点个数和操作次数。

第二行包含 \(n\) 个整数，其中第 \(i\) 个数 \(a_i\) 为第 \(i\) 个点的初始权值。

接下来 \(m\) 行，每行为 1 u v d  或 2 l r  的形式，分别表示进行一次操作 \(1\)（修改）或操作 \(2\)（询问）。

  • 输出格式

对于每次询问，输出一行一个整数，表示答案对 \(1000000007\) 取模的余数。…

YZOJ P4637 [CSP-S 2019 五校联训 Round 2]由比滨结衣(sqrt)

YZOJ P4637 [CSP-S 2019 五校联训 Round 2]由比滨结衣(sqrt)

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

难度：\(6.5\)

  • 题目描述

给定一个长度为 \(n\) 的正整数序列 \(\{a_i\}\)，有 \(m\) 次操作。格式如下：

1 l r x 将区间 \([l,r]\) 中的所有数变为 \(x\)。

2 l r x 查询区间 \([l,r]\) 中数字 \(x\) 的出现次数。

  • 输入格式

第一行两个正整数 \(n,m\)，表示序列长度和操作次数。

第二行 \(n\) 个正整数，第 \(i\) 个数为 \(a_i\)，表示序列初始值。

接下来 \(m\) 行每行四个正整数，表示操作，含义如题目所示。

  • 输出格式

对于每个询问，输出一行一个正整数表示答案。

  • 样例 1 输入

  • 样例 1 输出

  • 数据规模与约定

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

YZOJ P4587 斐波那契数列

YZOJ P4587 斐波那契数列

时间限制：1234MS      内存限制：43210KB

难度：\(6.5\)       （既然是自己搬的题还是正常一点吧w）

  • 题目描述

定义模意义下的递推数列 \(\displaystyle f_n=\left\{ {\begin{array}{*{20}{c}} 1&{,n \le 2}\\ {{f_{n – 1}} + {f_{n – 2}}}&{,n > 2} \end{array}} \right.\)，其中模数为 \(1000000009\) 。

给定整数 \(c\)（\(0 \leq c < 1000000009\)），求出它最早出现在数列的哪个位置，并输出下标。

若 \(c\) 永远不会出现在此数列的任一位置，则输出 \(-1\) 。

  • 输入格式

多组数据。

第一行一个正整数 \(T\) （\(0 < T \leq 100\)） 表示 \(T\) 组数据。

接下来 \(T\) 行每行一个数表示每组数据的 \(c\) 。

  • 输出格式

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

  • 样例输入

  • 样例输出

 

 

 

Source： BZOJ 5104…

YZOJ P3451 [SDOI2013]随机数生成器问题

YZOJ P3451 [SDOI2013]随机数生成器问题

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

难度：\(6.0\)

  • 题目描述

有一个随机数生成器，可以生成 \(0\) ~ \(p-1\) 之间的伪随机整数。在生成之前，需要设定一个随机数种子 \(k\) （\(0 \leq k < p\)），则生成器第 \(1\) 次生成的整数为 \(k\)。该随机数生成器有 \(2\) 个参数 \(a, b\)，如果第 \(i\) 次生成的整数为 \(x\)，则第 \(i+1\) 次生成的整数为 \((ax+b) \bmod p\) 。

现给定整数 \(t\) ，我们的问题是，该随机数生成器至少需要生成多少个数，才能生成得到 \(t\)？

对于给定的 \(p,a,b,k,t\) ，请计算要使随机数生成器生成整数 \(t\)，所需生成数的次数的最小值。

  • 输入格式

多组数据。第一行一个整数 \(T\) 表示数据组数，\(T \leq 50\) 。

接下来 \(T\) 行，每行五个整数 \(p,a,b,k,t\) 表示一组数据，其中 \(0 \leq a,b,k,t < p\) 。

  • 输出格式

对于每组数据，将随机数生成器的最小生成次数输出到文件中。

如果该随机数生成器无法生成整数 \(t\)，输出 \(-1\) 。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(20\%\) 的数据，\(p \leq 100\) 。

对于另外 \(30\%\) 的数据，\(a=1\) 。

对于另外 \(30\%\) 的数据，\(b=0\) 。

对于 \(100\%\) 的数据，\(p \leq 10^9\) 且 \(p\) 是质数。

 

 …

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 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 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 P3939 [HAOI2016]找相同字符

YZOJ P3939 [HAOI2016]找相同字符

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

难度：\(6.5\)

  • 题目描述

给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。

两个方案不同当且仅当这两个子串中有一个位置不同。

  • 输入格式

两行，两个字符串 \(s_1, s_2\)，\(1 \leq \left|s_1\right|, \left|s_2\right|\leq 200000\)，字符串中只有小写字母。

  • 输出格式

输出一个整数表示答案

  • 样例输入

  • 样例输出

 

 

 

Source: BZOJ 4566…