分类： 背包

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 P3754 Gab数列

YZOJ P3754 Gab数列

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

难度： \(4.5\)

  • 题目描述

给定数列 \(a_1,a_2,\cdots,a_n\)，定义数列 \(b_1,b_2,\cdots,b_m\) 为 Gab数列 当且仅当它满足：

1，\(\forall 1\le i\le m\) 满足 \(b_i\in\mathbf{N^*}\) 且 \(1\le b_i\le n\)

2，\(\sum_\limits{i=1}^{m}b_i\le k\)

求 \(\sum_\limits{i=1}^{m}a_{b_i}\) 的最大值。

  • 输入格式

第一行三个整数 \(n\)，\(m\) 和 \(k\) 。

第二行 \(n\) 个整数 \(a_i\) 。

  • 输出格式

输出仅一行，为最大值。

  • 样例输入

  • 样例输出

  • 样例说明

对应的 Gab数列 可以为 \(\{1,5,5,1,1,1\}\) 。

  • 数据范围

对于 \(15\%\) 的数据，\(n,m\le 8\)，\(k\le 50\)；

对于 \(40\%\) 的数据，\(n,m,k\le 200\)；

对于另外 \(5\%\) 的数据，满足 \(m=k\)；

对于另外 \(5\%\) 的数据，对于 \(1\le i\le j\le n\)，\(a_i\ge a_j\)；

对于 \(100\%\) 的数据，\(n\le 3000\)，\(k\le 8000\)，\(m\le 1000\)，\(1\le a_i\le 10^9\)，\(m\le k\)。

 

 

 …

[2017-2018 Petrozavodsk WC] J. Subsequence Sum Queries

[2017-2018 Petrozavodsk WC] J. Subsequence Sum Queries

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

难度：\(5.2\)

  • 题目描述

给定一个长度为 \(n\) 的非负整数序列 \(a\) 和一个正整数 \(m\) 。

现在有 \(q\) 组询问，每组询问给定两个正整数 \(l, r\) ，每次可以选择满足 \(l \leq i \leq r\) 的若干个 \(a_i\) （也可以一个都不选），使得这些 \(a_i\) 的和是 \(m\) 的非负整数倍，并输出满足条件的选择方案数对 \(10^9+7\) 取模后的余数。

  • 输入格式

第一行为两个正整数 \(n\) 和 \(m\) 。

第二行为序列 \(a\) ，共 \(n\) 个元素，用一个空格隔开。

第三行为询问数 \(q\) 。

接下来的 \(q\) 行，每一行都有两个正整数，分别为 \(l\) 和 \(r\) 。

  • 输出格式

共 \(q\) 行。

第 \(i\) 行为第 \(i\) 组询问的答案。

  • 样例输入

  • 样例输出

  • 样例说明

对于第一组询问 \(l=1, r=2\) ，有 不选、选择 \(5, 1\) ，共 \(2\) 种情况。

对于第二组询问 \(l=1, r=3\) ，有 不选、选择 \(5, 1\) 、选择 \(5, …

YZOJ P2202 Legend VII – Ornament

YZOJ P2202 Legend VII – Ornament

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

难度：\(5.0\)

  • 题目描述

  • 输入格式

第一行有两个整数 \(N\) 和 \(Q\)，表示商店有 \(N\) 个装饰品，一共有 \(Q\) 个询问。

第二行有 \(N\) 对整数，每 \(i\) 对整数 \(p_i, b_i\) 表示第 \(i\) 个装饰品的价格和好看度。

接下来 \(Q\) 行，每行两个整数 \(a, c\)，分别描述 \(Q\) 个询问。

  • 输出格式

对于每个询问输出一行，一个整数表示最大好看度。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(30\%\) 的数据，\(N \leq 100, Q \leq 1000\) 。

对于 \(100\%\) 的数据，\(N \leq 1000, Q \leq 100000, 1 \leq a \leq N, c \leq 1000\) 。

 

 

 …