25暑假day2测试题解
T1¶
知识点：数学
根据已知条件可以得出 乙仓库有 $x-2\times z$ 升啤酒。
一辆车最多运输 $c$ 升啤酒。则至少需要运输
次。
$\lceil x \rceil$ 表示向上取整，例如：$\lceil 1.1 \rceil = 2$，$\lceil 2 \rceil = 2$。
计算向上取整的结果可以使用 ceil 函数。
-
向下取整可以用
floor函数。 -
定义
ans = ceil((x - 2 * z) / c)。
注意数据范围需要 long long 和 double 类型。
long long x, z;
cin >> x >> z;
double c;
cin >> c;
long long ans = ceil((x - 2 * z) / c);
cout << ans;
T2¶
知识点：数学
错误方法
算出 $n!$ 的值以后判断值是不是 $12$ 的倍数。这显然不对，因为 $n!$ 的值会非常大，无法直接计算。
正确思路
注意到 $4!$ 是最小的满足 $n!$ 是 $12$ 的倍数的值。
由于 $i!$ 必然是 $(i-1)!$ 的倍数，因此只需要判断 $n$ 是否大于等于 $4$ 即可。
$i!=i\times(i-1)!$ 因此 $i!$ 必然是 $(i-1)!$ 的倍数。
时间复杂度为 $O(1)$。
T3¶
知识点：分支语句
可以用一个 long long 存储菜品金额，两个 char 变量存储点的两道菜。
long long x;
char a, b;
cin >> x >> a >> b;
然后分别讨论 a 和 b 是 B 或 C 的情况即可。一个小技巧是，不妨假设 a 是两个菜品中编号较小的那个，可以通过交换两个数完成这个假设。然后可以减小一半的讨论情况。
用一个变量 y 记录折扣力度。
int y = 10;
if (a > b)
swap(a, b); // 这句话保证了 a 是较小的。
if (a == 'B')
{
if (b == 'C')
{
y = 6;
}
else
{
y = 8;
}
}
else if (b == 'C')
{
y = 7;
}
cout << x / 10 * y;
T4¶
题目大意
小 F 和小 B 玩游戏。小 F 有一个数字 $x$，小 B 有一个数字 $y$。
从小 F 开始，双方轮流操作。在某次操作中，如果自己手上的数比对方的数小，就把自己的数加一，否则把自己的数改为除以二并向下取整。
当一方的数字为 $0$ 时，游戏结束。求结束时双方手里的数字。
解析
依照题意模拟即可。这是一个轮数不固定的循环，可以采用 while 循环来处理。
在本题中，循环继续的条件是 $x$ 和 $y$ 均不为 $0$，应把两数不为零的语句用逻辑与（&&）链接。可以用一次 while 循环来模拟一轮（双方各操作一次）游戏。
while (x != 0 && y != 0)
{
if (x < y)
x++;
else
x /= 2;
if (x == 0)
break; // 注意小 F 操作完以后数字为 0 就停下
if (y < x)
y++;
else
y /= 2;
}
T5¶
知识点：思维题
如果把 $a$ 序列从小到大排序，那么 $a_i-a_{i+1}\leq 0$，否则一定有一项 $>0$ ，因此我们从小到大排序，求相邻两项差的最大值即可。
这样保证相邻两项差值都是 $\leq 0$ 的，必然可以使得进步最小。
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + n + 1);
int ans = -1e9;
for (int i = 1; i < n; i++)
ans = max(ans, a[i] - a[i + 1])
T6¶
知识点：思维，计数。
暴力做法
对于每次操作，遍历整个数组，将满足 $a_i=x$ 的值全部改为 $y$。然后累加求和。
注意求和变量需要 long long。
时间复杂度：$O(qn)$，其中 $q$ 是操作次数，$n$ 是数组长度。
#include <bits/stdc++.h>
using namespace std;
long long n, q, a[100005];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
cin >> q;
while (q--)
{
int x, y;
cin >> x >> y;
long long ans = 0;
for (int i = 1; i <= n; i++)
{
if (a[i] == x)
{
a[i] = y;
}
ans += a[i];
}
cout << ans << '\n';
}
return 0;
}
优化
每次操作只有 $a_i=x$ 的元素会被修改，因此可以使用一个计数数组统计每个数字的出现次数。
定义 int cnt[100005]，其中 cnt[i] 表示数字 i 在数组中出现的次数。
那么每次操作对于数组总和的影响为：
设 $ans$ 为上一次的序列元素总和，则本次操作后序列总和会更新为：
即减去原本 数组中 x 的出现次数乘以 x，加上 x 的出现次数乘以 y。
然后更新 cnt[x] 和 cnt[y] 的值。
cnt[y] += cnt[x]，表示y的出现次数增加x的出现次数。cnt[x] = 0，表示x的出现次数为 $0$。
这样做每次可以 $O(1)$ 的时间复杂度内维护出一次操作带来的影响。最终整体时间复杂度为 $O(n+q)$。
注意 long long 即可。