Blog of RuSun

OneProblemIsDifficultBecauseYouDontKnowWhyItIsDiffucult

P8365 [LNOI2022] 吃

P8365 [LNOI2022] 吃

如果确定了顺序,那么每个操作是独立的。对于一次操作如果需要选择加法需要满足:
x+b>ax(a1)x<b
a=1 时,显然成立。显然最后的结果一定是先选择若干个加法再若干个乘法,考察出现两次加法需要满足:

{(a11)x<b1(a21)(x+b1)<b2(a21)x<b2(a11)(x+b1)<b1

如果排除 a1 的部分,则有:

{0<x<b2a21b10<x<b1a11b2

使得 b2a21+b1b1a11+b2 最大,a1=a2=2b2>b1b1>b2 矛盾,如果排除 a1 的部分,不存在两次加法。

考察选择哪一个数作为加法,ans=(ai)x+bkak 。即选择最大的 x+bkakk 。如果有 (ak1)x>bk ,说明不选择加法最优。

查看代码
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
#include <cstdio>
#include <algorithm>
using namespace std;
template <class Type>
void read(Type &x)
{
char c;
bool flag = false;
while ((c = getchar()) < '0' || c > '9')
c == '-' && (flag = true);
x = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
x = (x << 3) + (x << 1) + c - '0';
if (flag) x = ~x + 1;
}
template <class Type, class ...rest>
void read(Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write(Type x)
{
if (x < 0) putchar('-'), x = ~x + 1;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
typedef long long LL;
const int N = 5e5 + 10, mod = 1e9 + 7;
int n, A[N], B[N];
int main ()
{
read(n);
for (int i = 1; i <= n; ++i) read(A[i]);
for (int i = 1; i <= n; ++i) read(B[i]);
LL cur = 1;
for (int i = 1; i <= n; ++i) if (A[i] == 1)
{
cur += B[i];
swap(A[i], A[n]), swap(B[i], B[n]);
--i, --n;
}
int t = -1;
for (int i = 1; i <= n; ++i)
if (!~t || ((cur + B[i]) * A[t] > (cur + B[t]) * A[i]))
t = i;
if ((LL)(A[t] - 1) * cur > B[t]) t = 0;
else cur += B[t];
for (int i = 1; i <= n; ++i) if (i ^ t)
cur = cur * A[i] % mod;
write(cur);
return 0;
}

Gitalk 加载中 ...