A.A Multiply（贪心）
题意：
给你一个长度为
N
N
N 、
A
=
(
A
1
,
A
2
,
…
,
A
N
)
A=(A_1,A_2,\dots,A_N)
A=(A1,A2,…,AN) 和整数
C
C
C 的整数序列。
在进行最多一次以下操作后，求
A
A
A 中元素的最大可能和：
- 指定整数 l l l 和 r r r ，并将 A l , A l + 1 , … , A r A_l,A_{l+1},\dots,A_r Al,Al+1,…,Ar 分别乘以 C C C 。
分析：
分类讨论：
-
C > 0 C>0 C>0，求出最大子段和，乘上 C C C，再加上原来非最大子段和的部分即可。
-
C ≤ 0 C \le 0 C≤0，求出最小子段和，乘上 C C C，再加上原来非最小子段和的部分即可。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e5 + 5;
int a[N];
int n, c;
int main() {
cin >> n >> c;
for (int i = 1; i <= n; i++)
cin >> a[i];
if (c > 1) {
LL now = 0, ans = 0, sum = 0;
for (int i = 1; i <= n; i++) {
now = max(now, 0LL) + a[i];
ans = max(ans, now);
sum += a[i];
}
cout << sum + ans * (c - 1) << endl;
} else {
LL now = 0, ans = 0, sum = 0;
for (int i = 1; i <= n; i++) {
now = min(now, 0LL) + a[i];
ans = min(ans, now);
sum += a[i];
}
cout << sum + ans * (c - 1) << endl;
}
return 0;
}
B.Bought Review（贪心）
题意：
给出 T T T 个测试用例，解决以下问题。
在美食评论网站 E a t C o c o d e r EatCocoder EatCocoder 上，您可以用从 1 1 1 到 5 5 5 的整数颗星来评论餐馆。
最初，厨师 B B B 管理的餐厅有 A i A_i Ai 条评论， i i i 颗星。 ( 1 ≤ i ≤ 5 ) (1 \le i \le 5) (1≤i≤5)
厨师可以向 E a t C o c o d e r EatCocoder EatCocoder 管理部门支付 P i P_i Pi 日元的贿赂，以获得额外的 i i i 星级评论。 ( 1 ≤ i ≤ 5 ) (1 \le i \le 5) (1≤i≤5)
通过贿赂增加 k k k 条评论后，总共会有 A 1 + A 2 + A 3 + A 4 + A 5 + k A_1+A_2+A_3+A_4+A_5+k A1+A2+A3+A4+A5+k 条评论。
厨师 B B B 希望这些评论的平均分至少为 3 3 3 星。请确定实现这一目标所需的最低贿赂总额。
分析：
观察发现只有 A 4 , A 5 A_4,A_5 A4,A5对答案有贡献，只需要比较 2 × A 4 2 \times A_4 2×A4和 A 5 A_5 A5的大小即可。之后贪心地进行选择，分三种情况： 1 1 1.全选 A 4 A_4 A4， 2 2 2.全选 A 5 A_5 A5， 3 3 3.选一个 A 4 A_4 A4，其他的选 A 5 A_5 A5
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a[6], p[6];
int main() {
int t;
cin >> t;
while (t--) {
for (int i = 1; i <= 5; i++)
cin >> a[i];
for (int i = 1; i <= 5; i++)
cin >> p[i];
int res = a[1] + a[1] + a[2] - a[4] - a[5] - a[5];
if (res <= 0)
cout << 0 << endl;
else if (p[4] + p[4] <= p[5])
cout << p[4] * res << endl;
else if (p[5] <= p[4])
cout << (res + 1) / 2 * p[5] << endl;
else
cout << res / 2 * p[5] + res % 2 * p[4] << endl;
}
return 0;
}
C.Catastrophic Roulette（期望 dp）
题意：
问题陈述
有一个轮盘，它能以相等的概率从 1 , 2 , … , N 1,2,\dots,N 1,2,…,N 中产生一个整数。
两个玩家用它玩下面的游戏：
-
玩家轮流转动轮盘。
-
如果产生的整数之前没有出现过，则不会发生任何事情。
-
否则，转动轮盘的玩家要支付 1 1 1 日元的罚款。
-
-
当所有 N N N 个整数都至少出现过一次时，游戏立即结束。
请分别求出第一位和第二位玩家在游戏结束前支付的罚款金额的期望值，取模 998244353 998244353 998244353 。
分析：
f
i
,
g
i
f_i,g_i
fi,gi表示已经抽了
i
i
i个数，当前是
A
l
i
c
e
Alice
Alice 或
B
o
b
Bob
Bob 抽的，期望罚款。
期望
d
p
dp
dp进行倒推处理，
f
n
=
g
n
=
0
f_n=g_n=0
fn=gn=0，
p
=
i
n
p=\frac{i}{n}
p=ni表示抽到已经有的概率。那么有转移方程：
f
i
=
(
1
−
p
)
×
g
i
+
1
+
p
×
g
i
f_i=(1-p) \times g_{i+1} + p \times g_i
fi=(1−p)×gi+1+p×gi
g
i
=
(
1
−
p
)
×
f
i
+
1
+
p
×
(
f
i
+
1
)
g_i=(1-p) \times f_{i+1} + p \times (f_i+1)
gi=(1−p)×fi+1+p×(fi+1)
将
f
i
f_i
fi带入
g
i
g_i
gi，并通过移项得到：
f
i
=
(
1
−
p
)
×
g
i
+
1
+
p
×
(
1
−
p
)
×
f
i
+
1
+
p
2
1
−
p
2
f_i = \frac{(1-p) \times g_{i+1}+p \times (1-p) \times f_{i+1} + p^2}{1-p^2}
fi=1−p2(1−p)×gi+1+p×(1−p)×fi+1+p2
求得
g
i
g_i
gi带入求
f
i
f_i
fi即可。答案为
f
1
,
g
1
f_1,g_1
f1,g1。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 5;
const int mod = 998244353;
LL f[N], g[N];
LL inv(LL x, LL y = mod - 2) {
x = (x % mod + mod) % mod;
LL ans = 1;
while (y) {
if (y & 1)
ans = 1ll * ans * x % mod;
x = 1ll * x * x % mod;
y >>= 1;
}
return ans;
}
int main() {
int n;
cin >> n;
for (int i = n - 1, p; i; i--)
p = 1ll * i * inv(n) % mod,
f[i] = ((g[i + 1] * (1ll - p) + 1ll * f[i + 1] * p % mod * (1ll - p) + 1ll * p * p) % mod *
inv(1ll - 1ll * p * p) % mod + mod) % mod,
g[i] = ((f[i + 1] * (1ll - p) + (f[i] + 1ll) * p) % mod + mod) % mod;
cout << f[1] << ' ' << g[1] << endl;
return 0;
}
D.Digit vs Square Root （打表）
题意：
为
T
T
T 个测试用例解决以下问题。
给定整数
N
N
N ，求满足以下所有条件的整数
x
x
x 的个数：
- 1 ≤ x ≤ N 1 \le x \le N 1≤x≤N
- 让 y = ⌊ x ⌋ y = \lfloor \sqrt{x} \rfloor y=⌊x⌋ .将 x x x 和 y y y 用十进制表示（不带前导零）， y y y 是 x x x 的前缀。
分析：
通过打表发现，若 x x x满足条件，那么 x x x是以下两种形式之一：
- x = 10 0 k − 2 × 1 0 k x=100^k-2 \times 10^k x=100k−2×10k
- x ∈ [ 10 0 k − 1 0 k , 10 0 k + 1 0 k ) x \in [100^k-10^k,100^k+10^k) x∈[100k−10k,100k+10k)
枚举 k k k，计算区间交集即可。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 998244353;
int main() {
int t;
cin >> t;
while (t--) {
LL n;
cin >> n;
LL ans = 1;
for (LL i = 10; i <= 1000000000; i *= 10) {
LL tmp = i * i;
if (n >= tmp - i - i)
ans++;
if (n >= tmp - i)
ans += min(tmp + i - 1, n) - tmp + i + 1;
}
cout << ans << endl;
}
return 0;
}
E.Existence Counting （树状数组）
题意：
给你整数 N N N 和 K K K 。考虑长度为 K K K 的序列 a = ( a 1 , a 2 , … , a K ) a=(a_1,a_2,\dots,a_K) a=(a1,a2,…,aK) ，它满足以下所有条件：
-
a i a_i ai 是一个整数，使得 1 ≤ a i ≤ N 1 \le a_i \le N 1≤ai≤N .
-
a a a 中的所有元素都不同。
让我们把所有可能的序列 a a a 按词典顺序排列，形成一个 “序列的序列”，称为字典 s s s 。
给定一个存在于字典 s s s 中的序列 P P P ，针对每个整数 t = 1 , 2 , … , N t=1,2,\dots,N t=1,2,…,N 回答下面的问题：
-
求满足以下所有条件的序列 b b b 的个数（模为 998244353 998244353 998244353 ）：
-
字典 s s s 中存在序列 b b b 。
-
整数 t t t 包含在序列 b b b 中。
-
序列 b b b 在词法上小于或等于序列 P P P 。
-
分析：
首先不考虑必须出现某个数 t t t的限制，只计算 P P P之前有多少排列。和计算排列的时候一样，我们从前往后枚举每个位置 i i i，通过树状数组计算这个位置上能填多少个比现在填的数 P i P_i Pi小的数，再乘上后面的填法数，填法数为 ( n − i ) ! ( n − k ) ! \frac{(n-i)!}{(n-k)!} (n−k)!(n−i)!。那么 P P P之前有 ∑ i = 1 k ( n − i ) ! ( n − k ) ! ( P i − 1 − ∑ i = 1 j [ P j < P i ] ) \sum\limits_{i=1}^{k}\frac{(n-i)!}{(n-k)!}(P_i-1-\sum_{i=1}^{j}[P_j < P_i]) i=1∑k(n−k)!(n−i)!(Pi−1−∑i=1j[Pj<Pi])个序列。
再考虑 t t t不出现的序列有多少个。实际上就相当于在序列的值域 [ 1 , n ] [1,n] [1,n]中直接去掉了 t t t这个数，那等价于直接把值域当成 [ 1 , n − 1 ] [1,n−1] [1,n−1]，然后把所有 P i > t P_i>t Pi>t减 1 1 1。这样，在 [ 1 , n − 1 ] [1,n−1] [1,n−1]中，修改过的 P P P之前出现的序列，就和不含 t t t的序列对应。用上面的式子计数即可。
其中 P i = t P_i=t Pi=t的情况需要特殊考虑。由于这个 P i P_i Pi实际上在值域中并不存在，而是一个比 [ 1 , t − 1 ] [1,t−1] [1,t−1]大比 [ t + 1 , n ] [t+1,n] [t+1,n]小的神秘数，所以 i i i后面的所有数都不会造成贡献，需要用另一个树状数组维护每个位置 i i i造成的贡献，然后减掉后面不会造成贡献的一段。另外我们统计的是 P P P之前的序列有多少个含 t t t，所求的范围是包含 P P P本身的，所以此时还需要给答案额外加一。
对于 n n n个询问，我们从小到大处理每个询问，一开始每个 P i P_i Pi都有 P i > t P_i>t Pi>t，所以都要减掉 1 1 1。处理询问的时候每次碰到有 P i = t P_i=t Pi=t就把 1 1 1加回来。体现在答案上就是减去 ( n − i ) ! ( n − k ) ! \frac{(n-i)!}{(n-k)!} (n−k)!(n−i)!
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int n, k;
int p[N], c[N], d[N], q[N];
const int mod = 998244353;
int tmp[N], invf[N];
int binpow(int x, int y) {
int ans = 1;
while (y) {
if (y & 1)
ans = 1LL * ans * x % mod;
x = 1LL * x * x % mod;
y >>= 1;
}
return ans;
}
int cal(int x, int y) {
return 1LL * tmp[x] * invf[x - y] % mod;
}
void add(int x) {
for (; x <= n; x += (x & -x))
c[x]++;
}
int query(int x) {
int ans = 0;
for (; x; x -= (x & -x))
ans += c[x];
return ans;
}
void change(int x, int val) {
for (; x <= k; x += (x & -x))
d[x] = (d[x] + val) % mod;
}
int ask(int x) {
int ans = 0;
for (; x; x -= (x & -x))
ans = (ans + d[x]) % mod;
return ans;
}
int main() {
cin >> n >> k;
tmp[0] = 1;
for (int i = 1; i <= n; i++)
tmp[i] = 1LL * tmp[i - 1] * i % mod;
invf[n] = binpow(tmp[n], mod - 2);
for (int i = n; i >= 1; i--)
invf[i - 1] = 1LL * invf[i] * i % mod;
for (int i = 1; i <= k; i++)
cin >> p[i];
for (int i = 1; i <= k; i++)
q[p[i]] = i;
int tot = 0;
for (int i = 1; i <= k; i++) {
tot = (tot + 1LL * (p[i] - 1 - query(p[i] - 1)) * cal(n - i, k - i)) % mod;
add(p[i]);
}
if (n == k) {
for (int i = 1; i <= n; i++)
cout << tot + 1 << endl;
return 0;
}
int sub = 0;
for (int i = 1; i <= n; i++)
c[i] = 0;
for (int i = 1; i <= k; i++) {
sub = (sub + 1LL * (p[i] - 2 - query(p[i] - 1)) * cal(n - 1 - i, k - i)) % mod;
change(i, 1LL * (p[i] - 2 - query(p[i] - 1)) * cal(n - 1 - i, k - i) % mod);
add(p[i]);
}
for (int i = 1; i <= n; i++) {
if (q[i])
sub = (sub + cal(n - 1 - q[i], k - q[i])) % mod;
int ans = (tot - sub + mod) % mod;
if (q[i])
ans = (ans + ask(k) - ask(q[i]) + 1) % mod;
if (q[i])
change(q[i], cal(n - 1 - q[i], k - q[i]));
cout << (ans + mod) % mod << endl;
}
return 0;
}
赛后交流
在比赛结束后，会在交流群中给出比赛题解，同学们可以在赛后查看题解进行补题。
群号： 704572101，赛后大家可以一起交流做题思路，分享做题技巧，欢迎大家的加入。
