Educational Codeforces Round 95 (Rated for Div. 2)
A. Buying Torches
题目大意
在一个游戏中你需要做 (k) 个火把，其中每个火把由 (1) 个木棍和 (1) 个煤炭组成
游戏开始时你拥有 (1) 个木棍，可以执行任意次以下两种操作之一
- 用 (1) 个木棍换 (x) 个木棍
- 用 (y) 个木棍换 (1) 个煤炭
请给出制造 (k) 个火把最小需要的操作数
(2 leq x leq 10^9)
(1 leq y, k leq 10^9)
math *1000
思路分析
这题样例错了，WA 死我了！！！
这题的坑点在于 ceil 函数的精度不足以覆盖这个题目的数据范围
首先，我们总共需要 k * y + k 个木棍，我们每次进行操作一可以获得 x - 1 个木棍。设操作一的操作数为 cnt
，则存在关系：
故答案为：
注意 ceil 应为： ceil(x, y) = (x + y - 1) / y
代码
void solve(){
LL x, y, k;
cin >> x >> y >> k;
LL need = k * (y + 1) - 1;
cout << (need / (x - 1)) + k + !(need % (x - 1) == 0) << endl;
}
int main(){
int t = read();
while (t--) solve();
return 0;
}
有如下注意点：
- 假如出现了完全不可预知的错误，请考虑精度问题，不要完全相信
api。
B. Negative Prefixes
题目大意
给定一个有 (n) 个元素的序列 (arr) ，并给定序列 (arr) 中各元素是否被锁定（能否移动，修改）。
请你输出 (k) 值最小时对应的序列。
其中， (k) 值为：(max j ightarrow where { p_j <0 },p_j = sum_{i=1}^{j}a_i)，换一句话说，使得序列前缀和小于 (0) 的最大索引。若不存在这样的索引则 (k = 0) 。
- (1 leq n leq 100)
- (-10^5 leq arr_i leq 10^5)
greedy sortings *1300
思路分析
很简单，他不需要你输出 (k) 值，只需要你输出对应的序列。贪心的去想，显然我们希望所有未被锁定的元素能从大到小排。
代码
const int maxn = 1e2 + 50;
int f[maxn], ilock[maxn], can[maxn]; // ilock -> 是否锁定， can -> 未被锁定的序列
void solve(){
int n = read(), cnt = 0;
for (int i = 0; i < n; ++ i) f[i] = read();
for (int i = 0; i < n; ++ i) {
ilock[i] = read();
if (ilock[i] == 0) can[cnt++] = f[i];
}
sort(can, can + cnt, greater<int>());
int pt = 0;
for (int i = 0; i < n; ++ i)
if (!ilock[i]) f[i] = can[pt++];
print(f, n); // 自定义输出函数
}
int main(){
int t = read();
while (t--) solve();
return 0;
}
有如下注意点：
- 没有看清楚输出要求就做题了，实际上要求的可能比较想象的更简单，别着急！！
C. Mortal Kombat Tower
题目大意
你和你的朋友需要闯关打 boss ，你们有一定数量的无敌火箭炮！，可以直接秒杀任何 boss。已知有两种 boss，简单 boss 和 困难 boss。
你们需要协助通过 (n) 关（这意味着你们需要共杀死 (n) 个 boss)。你和你的朋友都可以选择击杀 (1) 或者 (2) 个 boss。需要注意的时：
- 你可以击杀所有 boss
- 你的朋友只能击杀简单 boss
- 你的朋友先进行闯关
请输出闯关所需的使用无敌火箭炮的最小数量。
- (1 leq n leq 2cdot 10^5)
dp greedy 1500
思路分析
好像有贪心算法的题解，但是显然这题是个裸的 dp。定义 dp ：dp[i][j] := 第 i 关由 j 完成的最小开销，其中 j 只有 0 or 1 代表你和你的朋友。
代码
const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 50;
int dp[maxn][2], a[maxn];
void solve(){
int n = read();
for (int i = 1; i <= n; ++ i) a[i] = read();
dp[0][0] = dp[0][1] = 0;
dp[1][0] = a[1], dp[1][1] = inf;
dp[2][0] = a[1] + a[2];
dp[2][1] = dp[1][0];
for (int i = 3; i <= n; ++ i){
dp[i][0] = min(dp[i - 1][1] + a[i], dp[i - 2][1] + a[i] + a[i - 1]);
dp[i][1] = min(dp[i - 1][0], dp[i - 2][0]);
}
cout << min(dp[n][0], dp[n][1]) << endl;
}
int main(){
int t = read();
while (t--) solve();
return 0;
}
有以下注意点：
dp思路混乱，代码过于暴力，不够优美- 不过写的很快，这是长处
- 需要学习贪心算法！！
D. Trash Problem
题目大意
Vova 决定打扫房间。可以将房间表示为坐标轴 OX 。房间里有 (n) 堆垃圾，第 (i) 堆的坐标是整数 (p_i) 。所有桩具有不同的坐标。
让我们将总清理定义为以下过程。此过程的目标是将所有桩收集至不超过两个且互不相同的 (x) 坐标下。为了实现此目标，Vova 可以执行几次（可能为零）移动。在移动期间，他可以选择一些 (x)，并使用扫帚将所有堆（无法控制数量）从 (x) 移动到 (x + 1)或 (x-1)。
此外会有 (q) 个询问，共两种查询类型：
0 x- 从坐标 (x) 移除一堆垃圾。确保此时在坐标 (x) 中有一个桩。1 x- 将一堆垃圾添加到坐标 (x) 。可以确保此时在坐标 (x) 中没有桩。请注意，有时房间中的垃圾堆为零。
Vova 想知道，在所有询问前完成总清理和每次询问后完成总清理的最小移动次数，请注意，总清理实际上并没有发生，也不会改变堆的状态。它仅用于计算移动次数。
- (1 leq n, q leq 10^5)
- (1 leq p_i leq 10^9)
data structures hashing *2100
思路分析
题目贼长 ，实际上意思还算比较简单，需要我们按照规律进行垃圾清理，保证操作次数最小且符合垃圾清理的要求。给定了 (q) 个询问，且 (q) 的数量级还不低，所以肯定需要我们使用较为高效的数据结构来解决问题。
题目需要我们将所有堆移动到最多两个位置，不妨定义 (x_i, x_j) 分别为最后移动的两个位置且 (x_i < x_j) 。
上述序列，(x_{min}, x_{max}) 代表最左最右的堆，定义 (x_k) 归于 (x_i) 侧，(x_{k + 1}) 归于 (x_{j}) 侧。所以最终答案为：
经过分析发现，实际上答案可以定义为 最大x - 最小x - 最大间隔gap，由于(x_{max} - x_{min}) 是固定的，gap 越大答案越小。
因此：本题需要解决，高效获取序列中最大间隔值（差值），和最大最小值。
当然，自己写数据结构是不太明智的，我们可以通过已有的数据结构例如： set multiset 或 map进行解决。
代码
代码借鉴了红名大佬的代码（手上的电脑只能写 py , 特别麻烦遂作罢）
#include <bits/stdc++.h>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, q;
std::cin >> n >> q;
std::set<int> p; // pos arr
std::multiset<int> d; // dist arr
// 添加节点
auto add = [&](int x) {
auto it = p.insert(x).first;
auto r = std::next(it);
if (it != p.begin() && r != p.end())
d.erase(d.find(*r - *std::prev(it)));
if (it != p.begin())
d.insert(x - *std::prev(it));
if (r != p.end())
d.insert(*r - x);
};
// 删除节点
auto del = [&](int x) {
auto it = p.erase(p.find(x));
if (it != p.begin())
d.erase(d.find(x - *std::prev(it)));
if (it != p.end())
d.erase(d.find(*it - x));
if (it != p.begin() && it != p.end())
d.insert(*it - *std::prev(it));
};
for (int i = 0; i < n; ++i) {
int x;
std::cin >> x;
add(x);
}
// 返回询问
auto get = [&]() {
if (p.size() <= 1)
return 0;
return *p.rbegin() - *p.begin() - *d.rbegin();
};
std::cout << get() << "
";
while (q--) {
int t, x;
std::cin >> t >> x;
if (t == 0) {
del(x);
} else {
add(x);
}
std::cout << get() << "
";
}
return 0;
}
有如下注意点：
- 我不熟悉
set的用法，很致命，需要熟悉set - 不存在
prev(iter) = arr.rbegin()的用法，其中rbegin()是反转迭代器！！！ - 这类题目很长的题目往往需要实现的只是一个比较简单的事情，因此在比赛时请认真读题。
- 关于迭代器的操作，我不太熟练，面对不太熟练的题请，先在草稿纸上做好笔记。
E. Expected Damage
题目大意
计算期望 (E)，你拥有一个耐力值为 (a) ，防御值为 (b) 的盾牌，你将遇到 (n) 个怪兽，每个怪兽的力量值为 (d_i)。
满足如下规律：
- 如果 (a == 0)，你会收到 (d) 的伤害。
- 如果 (a >0 land d geq b)，你不会收到伤害，但是盾牌的耐力值减一：(a leftarrow a-1)。
- 如果 (a > 0land d < b)，你不会收到伤害。
总共需要处理 (m) 个盾牌的情况。请计算每个盾牌给定 (a_i,b_i) 下的收到伤害的期望。
其中，预期一定是一个不可约分数 (frac{x}{y})，(y) 于 (998244353) 互素。你需要输出 (xcdot y^{-1} mod ;998244353) 的值。其中(y^{-1})为(y)的逆元。
- (1 leq n,m leq 2cdot 10^5)
- (1 leq a_i leq n)
- (1 leq b_i, d_i leq 10^9)
probabilities combinatorics binary search *2400
思路分析
首先，怪兽分为大怪兽和小怪兽两种，设大怪兽数量为 (k)。当 (a ge k) 时答案为 (0)。
对于大怪兽，能造成伤害的概率为 (P_1= 1 - frac{a}{k}) （最多抵消 (a) 个）。
对于小怪兽，我们可以将 (k) 个大怪兽固定好，因此具有 (k + 1) 个间隔，前 (a) 个间隔都无法造成伤害，因此能造成伤害的概率为：(P_2= 1 - frac{a}{k + 1})。
因此，答案为:
对于求和，可以用二分查找 + 前缀和优化
然后按照费马小定律求逆元即可。
代码
import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline # 快读
import bisect
mod = 998244353
def fpow(a, b):
ans = 1
while b:
if (b & 1): ans = (ans * a) % mod;
b >>= 1;
a = (a * a) % mod;
return ans
n, m = map(int, input().split())
d = list(map(int, input().split()))
d = sorted(d)
pre = [0 for _ in range(n + 1)]
for i in range(n):
pre[i + 1] = pre[i] + d[i]
for _ in range(m):
a, b = map(int, input().split())
k = bisect.bisect_left(d, b) # 二分查找
low = max(0, n - k - a)
upp = max(0, n - k - a + 1)
# 1 - (a / k)
print((low * fpow(n - k, mod - 2) * (pre[n] - pre[k] + mod) % mod + upp * fpow(n - k + 1, mod - 2) * pre[k] % mod) % mod)