Skip to content

「LNOI2022」吃

题解约 1.2 千字
检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

小 A 很喜欢吃东西。

小 A 面前有 nn 份食物,第 ii 份有参数 aia_ibib_i。小 A 可以按照任意顺序吃掉这 nn 份食物。当她吃掉编号为 ii 的食物时,她可以选择将自己的体重乘以 aia_i 或者将自己的体重加上 bib_i。每份食物只能吃恰好一次。

小 A 的初始体重为 11,请求出她吃完 nn 份食物后能达到的最大体重。答案可能很大,你只需要输出其对 (109+7)({10}^9 + 7) 取模后的结果。

注意:你需要最大化体重并将该最大值对 (109+7)\bm{({10}^9 + 7)} 取模,而非最大化体重对 (109+7)\bm{({10}^9 + 7)} 取模的结果。

#输入格式

第一行输入一个整数 nn 表示食物的数量。第二行 nn 个整数 a1,a2,,ana_1, a_2, \ldots, a_n,第三行 nn 个整数 b1,b2,,bnb_1, b_2, \ldots, b_n,表示每份食物的参数。

#输出格式

输出一个整数,表示小 A 可以得到的最大体重对 (109+7)(10^9 + 7) 取模后的结果。

#输入输出样例

样例输入 #1

5
1 2 3 4 5
100 200 300 400 500

样例输出 #1

18060

样例解释 #1

以下方案可以达到最大体重:

  • 吃掉第一份食物并选择将体重增加 100100,体重变为 101101
  • 吃掉第二份食物并选择将体重增加 200200,体重变为 301301
  • 吃掉第三份食物并选择将体重乘 33,体重变为 903903
  • 吃掉第四份食物并选择将体重乘 44,体重变为 36123612
  • 吃掉第五份食物并选择将体重乘 55,体重变为 1806018060

样例 #2

见附加样例中的 sample/food2.insample/food2.ans

该组样例满足 n10n \le 10 和特殊性质 E。

样例 #3

见附加样例中的 sample/food3.insample/food3.ans

该组样例满足 n20n \le 20 和特殊性质 E。

样例 #4

见附加样例中的 sample/food4.insample/food4.ans

该组样例满足 n2000n \le 2000

样例 #5

见附加样例中的 sample/food5.insample/food5.ans

该组样例满足特殊性质 A。

样例 #6

见附加样例中的 sample/food6.insample/food6.ans

该组样例满足特殊性质 C。

样例 #7

见附加样例中的 sample/food7.insample/food7.ans

该组样例满足特殊性质 D。

样例 #8

见附加样例中的 sample/food8.insample/food8.ans

该组样例满足特殊性质 B。

样例 #9

见附加样例中的 sample/food9.insample/food9.ans

#数据范围与约定

对于 100%100 \% 的测试数据,1n5×1051 \le n \le 5 \times {10}^51ai,bi1061 \le a_i, b_i \le {10}^6

测试点编号 nn \le 特殊性质
11 1010 DE
22 E
33 AE
44 E
55 2020 DE
66 E
77
88
99 20002000 D
1010
1111
1212
1313 5×1055 \times {10}^5 BD
1414 B
1515 C
1616
1717 105{10}^5
1818
1919 5×1055 \times {10}^5
2020
  • 特殊性质 A:ai=1a_i = 1
  • 特殊性质 B:aibia_i \ge b_i
  • 特殊性质 C:ai,bia_i, b_i[1,106][1, 10^6] 内独立均匀随机生成;
  • 特殊性质 D:ai2a_i \ge 2
  • 特殊性质 E:ai4a_i \le 4

#思路

容易发现当 ai=1a_i = 1 时,选择将体重加上 bib_i 显然是更优的,那么可以先处理一遍这种情况,并更新答案,记为 BB

然后剩下的食物都满足 ai2a_i \geq 2,此时最多进行一次 +bi+ b_i 操作(令 b1b2b_1 \geq b_2,显然 b1×a2b1+b2b_1 \times a_2 \geq b_1 + b_2),设 A=iSaiA = \prod_{i \in S} a_iSS 为剩余食物的集合),分类讨论如下:

  1. 当不进行 +bi+ b_i 操作时,答案为 A×BA \times B
  2. 当仅进行 11+bi+ b_i 操作时,答案为 A×maxiS{B+biai}\displaystyle A \times \max_{i \in S} \{\frac{B + b_i}{a_i}\}

#代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 5e5 + 5;
const int mod = 1e9 + 7;

int n, a[N], b[N], ans = 1;

int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);

cin >> n;

for (int i = 1; i <= n; i++) {
cin >> a[i];
}

for (int i = 1; i <= n; i++) {
cin >> b[i];
}

for (int i = 1; i <= n; i++) {
if (a[i] == 1) {
ans = (static_cast<long long>(ans) + b[i]) % mod;
a[i] = -1;
}
}

long double max = ans;
int max_id = -1;

for (int i = 1; i <= n; i++) {
if (~a[i]) {
long double t = static_cast<long double>(static_cast<long long>(ans) + b[i]) / a[i];

if (t > max) {
max = t;
max_id = i;
}
}
}

if (~max_id) {
a[max_id] = -1;
ans = (static_cast<long long>(ans) + b[max_id]) % mod;
}

for (int i = 1; i <= n; i++) {
if (~a[i]) {
ans = static_cast<long long>(ans) * a[i] % mod;
}
}

cout << ans << endl;

return 0;
}