2024.10.2 模拟赛

题目：2024.10.2 题目

躲避技能

有一棵 $n$ 点 $n-1$ 条边的树，第 $i$ 条边连接 $u_i\rightleftarrows v_i$，边权为 $w_i$。现在树上有 $m$ 个小人，编号为 $i$ 的小人在 $a_i$ 处。同样有 $m$ 个目标，第 $i$ 个目标结点为 $b_i$，小人要走到 $b_i$ 上。问你经过边权的最小值。

---

对于一个在点 $u$ 上、需要走到点 $v$ 小人，假如有最小的、祖先为 $x$ 的子树能包括这两个点，那么这个小人就不会走到子树的外面，但是一定会经过子树最上面的那一条边。因此，我们以那条边为单位，计算需要经过多少次即可。

由于边权达到了 $10^{100}$，经过次数估个 $10^{10}$，因此要写一个最少 $110$ 的高精度。需要实现高精度加高精度、高精度乘低精度，还有题目当中反着输入的边权不要忘记了。时间复杂度 $\mathcal{O}(nk)$，其中 $k$ 为位数，为了保险好渴鹅开到了 $120$ 位。

奶茶兑换券

有价值为 $m$ 的代金券无数张，现有 $n$ 种奶茶要购买，第 $i$ 种奶茶购买数量为 $a_i$，单价为 $b_i$。每次你必须选择两倍奶茶，然后使用代金券购买，并且不找零。问你比直接购买亏了多少钱。

---

首先，我们将每一个 $b_i$ 都对 $m$ 进行取模，这不影响答案的求解，但能为我们的处理带来许多方便。然后，可以以 $b_i$ 分成小于 $\frac{m}{2}$ 的和大于 $\frac{m}{2}$ 的，不难发现小的与大的匹配达到尽量大但小于 $m$ 的方案是最优的，因此以 $b_i$ 为关键字对所有奶茶从小到大排序，然后使用双指针求出答案。

还要注意一下，可能会有剩余的小的找不到大的匹配，那就自己匹配自己。时间复杂度 $\mathcal{O}(n{\log }_{2}n)$。

帮助

采用暴力。首先枚举 $i$ 和 $j$ $(i\ne j)$，判断一下 $i$ 能否帮助 $j$ 做题，如果可以的话就让 $j$ 的题目数量累加上 $i$ 的，最后输出。时间复杂度 $\mathcal{O}(n^2)$，成功获得 $30$ 分。

神奇的变换

没时间写了，敲了一个针对于 $n=q=1$ 的解法，成功获得 $20$ 分。

总结

• 排名：$2$；
• 比赛分数：$250/400$；
• 情况：相比 2024.10.1 模拟赛，一般；
• 问题：思考时间太短。