Content：模拟赛
Date：2025.8.9

Problem-A IEEE 754

题目描述

题目背景告诉你浮点数表示法(IEEE 754 标准)，要求你求 $5^n$ ，其中 $n < 1024$ 。

思路

赛场上是直接写的高精度，但是赛后看过题解发现有更简单的做法。

首先用 Python 计算发现， $5^1023$ 大约有 800 位，而 double 类型的存储精度有 308 位，所以可以用 double 类型计算，但是要计算的是 $5^(-n)$ ，因为是浮点数。

提交记录：Link

Problem-B 探险

题目描述

给定一个数组 $a$ ，有两个人轮流操作，每次交换一对 $i,j$ ，谁进行操作后数组 $a$ 有序（从小到大），则这个人获胜。同时有 $q$ 个修改操作，分为两类：

$1$ $i$ $j$ ：将 $a_i$ 与 $a_j$ 交换。
$2$ $k$ ：将 $a$ 循环位移 $k$ 次。
你需要对于初始状态和每一个修改后的状态，判断是先手获胜还是后手获胜。

思路

赛场上想到了逆序对，但是时间比较少，只剩 $15$ 分钟了，而且最后开的这道题，所以脑子不太好使，就没有想出来。

赛后发现赛时的思路大致是对的，但是没有继续思考下去。容易发现答案和逆序对个数的奇偶性有关，具体来说：

当逆序对个数为奇数时，先手获胜；
当逆序对个数为偶数时，后手获胜
所以问题落在了如何处理修改后的逆序对变化。

对于第一个操作是好求的，因为交换两个数，逆序对个数的奇偶性就会变化。而对于第二个操作，可以发现每一个跨过 $k$ 的两个数的逆序对都会反过来，所以对答案的影响就是 $k(n-k) \bmod 2$ （赛时就是这里没有想出来）。

提交记录：Link

Problem-C 帕奇欧

题目描述

初始时，你手上有 1 张 A 类牌和 1 张 B 类牌。每一回合你都可以从拥有的牌中等概率选取一张，然后获得一张与抽取出来的牌同类型的牌，问你经过无限轮操作后，拥有 $x$ 张 A 类牌和 $y$ 张 B 类牌的概率，对 $10^9 + 7$ 取模。

思路

手玩一下样例可以发现，答案为 $\frac{(x + y - 3)! * (x + y - 2)}{(x + y - 1)}$ (这是赛时没化简得结果)。

化简后是 $\frac{1}{x + y - 1}$ 。

提交记录：Link

Problem-D 比赛

题目描述

有一种比赛，每一次比赛有若干个小节，率先得到 $M$ 分得人赢下这个小节。给定 $x,y,M$ ，求最后总分为 $x,y$ 时不同得小节数。

思路

赛时推了下式子，没推出来 TAT。

首先可以发现的是，满足题目要求得小节数是一段连续的区间。

所以我们可以分别找到这个区间的上界和下界。容易发现上界为 $\lfloor \frac{x}{M} \rfloor + \lfloor \frac{y}{M} \rfloor$ 。而下界通过分析可以发现是 $\max(\lceil \frac{x - tx}{M} \rceil, \lceil \frac{y - ty}{M} \rceil, \lceil \frac{x + y}{M - 1} \rceil)$ ，其中 $tx = \lfloor \frac{x}{M} \rfloor, ty = \lfloor \frac{y}{M} \rfloor$ 。

提交记录：Link

Problem-E 三目运算符

题目描述

给定一个只包含 $0,1,x,?,:$ 的合法三目运算符表达式，你可以将其中的 $x$ 替换为 0/1，求所有表达式的值的和对 $10^9 + 7$ 取模的结果。

思路

赛时直接枚举 $x$ 的取值，竟然有 80pts 的暴力分，出题人还是太良心了。

正解是考虑和表达式树一样的结果，即对于每个节点，都有走向 0/1 的两条路，问题转化为了走向值为 1 的叶子节点的概率。

提交记录：Link

Problem-F 卡牌游戏

题目描述

你有三种不同类型的卡牌，其中每种卡牌的数量由给定的字符串决定。同时你拥有两个数组 $A,B$ ，你需要从卡牌中选取恰好 $k$ 张，设你选择的三种卡牌的数量分别为 $x,y,z$ ，则你的得分为 $A_x \times B_y \times 2^z$ 。求最大得分。

思路

赛时直接枚举前两种卡牌的个数，得了 20 分。

可以发现第三种卡牌的贡献最大。设最多能选 $t$ 张第三种卡牌，则所有 $z < t-60$ 的方案均更差。即使 $A_x,B_y$ 的值从 $10^9 \times 10^9$ 变为了 $1 \times 1$ ，即变为原来的 $\frac{1}{10^{18}}$ ，而 $2^60 > 10^{18}$ ，所以变化后的结果依然更优，所以只要考虑 $t - 60 \le z \le t$ 的方案即可。