• 我的：468 049 082 106 336|293 237 800 142 907|369 019 056 040 514
• 标答：468 049 082 106 336|293 237 610 149 907|113 019 248 104 240

题目链接

场切：1、2、3、4、5、6、7、10、12。共 9 题。

弱智题：1、2、3、4、5、6、7，12 和 14 比较简单但是我也写了。

难题：8、13、15。

Problem 8 (Hard, Ad-hoc)

（同余）

题目：求关于自然数 $x,y,z$ 的方程 $25x + 10y + z = n$ 的解，并且希望 $x+y+z$ 最小。 Silas 利用贪心算法解这个题，即优先使得 $x$ 最大，然后 $y$ 最大，然后解出 $z$。但是这样解出的不一定就是 $x+y+z$ 最小的解。若真的解出了最优解，则称贪心算法成功。 例：$n=42$ 时，$x=0,y=4,z=2$ 是比贪心算法得到的 $x=1,y=1,z=7$ 更好的解，所以贪心算法不成功。

求：$n \in [1,1000]$ 中，有几个 $n$ 能让贪心算法成功。

$\bmod 5$ 一下，$z$ 要么是 $n \bmod 5$ 要么是 $n \bmod 5 + 5$。

设 $n = 5k + r$，那么

直觉上说，右侧 $z$ 自带 $+5$，大概率必不优。但是我们尝试证明一下。

先看 $5x + 2y = k$，$2(x + y) = k - 3x$，说明 $x$ 要最大化。当 $k \bmod 5$ 是 $0,2,4$ 的时候直接 $x = \lfloor \frac k 5 \rfloor$，否则 $x = \lfloor \frac k 5 \rfloor - 1$（$k \ge 5$）。同理：

$x+y+z$ 算一下发现右边必不优。

也就是说，$(n \bmod 25) \bmod 10 < 5$ 进入左侧才有是最优解。

即 $n \bmod 25$ 是 $[0,4] \cup [10,14] \cup [20,24]$。占 $\frac 3 5$。

但是别忘了 $k < 5$ 要特判。$10y + z = n$，贪心必定最优。因此 $[1,24]$ 比正常比例的 $\frac 3 5$ 还多出了 $10$ 个答案。

最终答案 $1000 \times \frac 3 5 + 10 = \boxed{610}$。

Problem 9 (Normal)

（导数）

$f(x) = \sin(7 \pi \sin(5x))$ 定义在 $x \in (0,2 \pi)$ 上。 函数有 $n$ 个零点，其中 $t$ 个和 $x$ 轴相切。 输出 $n + t$。

零点：$7\pi \sin(5x) = k \pi$，即 $7 \sin(5x) = k$。当 $\sin(5x)$ 是 $\frac 1 7$ 的整数倍时成立。$\sin(5x)$ 有 $5$ 个完整的周期（特判最后的 $2 \pi$），每个周期都有 $28$ 个。$n = 28 \times 5 - 1 = 139$。

切点：$f’(x) = \cos(7 \pi \sin(5x)) \times 7 \pi \cos(5x) \times 5 = 0$。

$\cos(7 \pi \sin(5x)) = \pm \sqrt{1 - f(x)^2} = \pm 1$，总之不是 $0$。也就是说只能 $\cos(5x)$ 是 $0$（注意到此时必有 $f(x) = 0$），即 $5x$ 是 $\frac \pi 2$ 的奇数倍，即 $x$ 是 $\frac \pi {10}$ 的奇数倍，有 $t = 10$ 个。

输出 $n + t = 139 + 10 = \boxed{149}$。

Problem 10 (Normal)

（组合计数）

$16$ 个格子排成一排，选 $8$ 个格子，要求没有多于 $2$ 个格子的连通块。输出方案数对 $1000$ 取模。

官方解法

把 $8$ 拆成若干个 $1$ 和 $2$。这个方案数是很少的。

设 $1$ 有 $n$ 个，则 $2$ 有 $8-n$ 个。

输出 $\boxed{907}$。

Problem 11 (Normal)

（同余、分类讨论）

$S$ 是一个正 $24$ 边形的顶点集合，画 $12$ 根等长线段使得 $S$ 中的每个点都恰好是一个线段的端点。 求方案数。

把点编号为 $[0,23)$。

等长线段可以用隔着的点数刻画。

枚举和 $0$ 连的点 $u$。

手玩一下发现，其余所有点都被 $\bmod u$ 分类了。会形成一个 $r \to r+u \to r+2u \to \cdots$ 这样的一个环。如果这个环是奇环，那么无解。偶环则有 $2$ 种方案。（既然在这里已经算过 $2$ 种了，那么 $u$ 和 $24-u$ 就要算同一种咯。特判 $u=12$ 有 $1$ 种。）

• $u=1$，$1$ 个偶环，$2$
• $u=2$，$2$ 个偶环，$4$
• $u=3$，$3$ 个偶环，$8$
• $u=4$，$4$ 个偶环，$16$
• $u=5$，$5 \perp 24$ 所以是 $1$ 个偶环，$2$
• $u=6$，$6$ 个偶环，$64$
• $u=7$，$7 \perp 24$ 所以是 $1$ 个偶环，$2$
• $u=8$，$8$ 个奇环，$0$（我考场的答案比表达多 $256$ 就是在这）
• $u=9$，$3$ 个偶环，$8$
• $u=10$，$2$ 个偶环，$4$
• $u=11$，$11 \perp 24$ 所以是 $1$ 个偶环，$2$
• $u=12$ 特判过，$1$

$2 + 4 + 8 + 16 + 2 + 64 + 2 + 0 + 8 + 4 + 2 + 1 = \boxed{113}$

Problem 12 (Easy)

有一个十一边形 $A_1 A_2 \cdots A_{11}$。

• $\forall i \in [2,10]$，$[A_i A_1 A_{i+1}] = 1$，$\cos(\angle A_i A_1 A_{i+1}) = \frac {12} {13}$
• 十一边形的周长是 $20$。

求 $A_1 A_2 + A_1 A_{11}$。可以证明答案是 $\frac {m \sqrt n - p} q$ 的形式，输出 $m+n+p+q$。

对边长（来自周长）和余弦值一起出现，那肯定是余弦定理。

还有个面积，那肯定是余弦转正弦然后 $\frac 1 2 ab \sin C$。$\cos$ 是 $\frac {12} {13}$，对应 $\sin$ 是 $\frac 5 {13}$。注意到这个角度的意义不大，我们用 $s$ 和 $c$ 代替。

令 $a_i = A_1 A_i$，$i \in [2,11]$。

不难发现，根据这个式子有 $a_3 = a_5 = \cdots = a_{11}$ 和 $a_2 = a_4 = \cdots$，而且两者乘积是 $\frac 2 s$。

输出 $\boxed{019}$。

Problem 13 (Hard, Ad-hoc)

（注意力、先猜再证、欧拉定理+快速幂）

Ad-hoc 经验：当你知道这个地方有个 Ad-hoc 的时候，不要强化任何东西，集中在你要求的东西上，努力尝试构造。如果心中有此题式子不依赖于初值这样的信念，可以代入一些小的初值帮助发现代数恒等式。

$f(x) = \frac 1 3 (x + \frac 1 x - 1)$，求 $f^{2024}(\frac {25} {11})$ 的值。 令答案为 $\frac p q$，输出 $(p+q) \bmod 1000$。

首先打表找规律：

数值膨胀了，有点奇怪。

分母有 Pattern，发现 $275 = 11 \times 25$，$43175 = 275 \times 157$。设序列第 $k$ 项为 $\frac{p_k}{q_k}$，我们猜想 $q_k = p_{k-1} \times q_{k-1}$。

没什么眉目了，硬做一下看看：

这启示我们 $\bmod 3$ 看一下，发现分子似乎都是 $1$，分母似乎都是 $2$。刚好 $p^2 + q^2 - pq$ 是 $0$，能除掉 $3$。

也就是说：

看起来好像是正确的，但是我还没保证 $p_k$ 和 $p_{k-1} q_{k-1}$ 是不是互质。

考虑证明：$p_{k-1}$ 和 $q_{k-1}$ 是互质的，所以我分别证明互质就行了。

$\gcd(3 p_k, p_{k-1}) = \gcd(3 q_{k-1}^2, p_{k-1}) = \gcd(3, p_{k-1}) = 1$，$q_k$ 同理。

也就是说上面的递推式的确是正确的，接下来考虑怎么求。

我的支路：计算量巨大

要求 $\bmod 1000$ 下的答案，求出 $\bmod 8$ 和 $\bmod 125$ 下的答案就行了。

$\bmod 8$ 很简单，很快啊 $p_k$ 和 $q_k$ 都 $0$ 了。

$\bmod 125$ 到这一步感觉不太对劲了……借助 Mathematica 可知，$\bmod 125$ 下的循环节长度为 $20$，是个有 $2$ 个开头的项的混循环，似乎不太能考场上手算算出来……但是总之能算出来 $p=48$ 和 $q=75$。

CRT 求一下可知 $p=48$，$q=200$，答案为 $\boxed{248}$。

官方支路

注意到 $(p_k + q_k) = \frac 1 3 (p_{k-1} + q_{k-1})^2$。到这一步已经基本做完了，后面都是体力活。

令 $g(x) = \frac 1 3 x^2$，我们要求 $g^{2024}(36)$。

$3 \times 12^{2^{2024}} \bmod 1000$：$\bmod 8$ 下是 $0$，$\bmod 125$ 下是 $3 \times 12^{2^{2024} \bmod 100}$（$\varphi(125) = 100$）

$2^{2024} \bmod 100$：$\bmod 4$ 下是 $0$，$\bmod 25$ 下是 $2^{2024 \bmod 20} = 2^4 = 16$（$\varphi(25) = 20$）。

也就是说 $2^{2024} \bmod 100 = 16$。代回去：

$3 \times 12^{16}$，快速幂算一下，$12^{16} = (12^2)^8 = (19^2)^4 = (111^2)^2 = 71^2 = 41$，即 $3 \times 12^{16} \bmod 125 = 123$。

CRT 解一下，答案为 $\boxed{248}$。

Problem 14 (Easy)

$\angle A$ 是直角；$BC = 38$，$AK=BK$，$AL=CL$，$AKL$ 是等边三角形，刚才提到的 $5$ 条边都等于 $14$。求 $\frac 1 {\sqrt 3} [BKLC]$。

（忽略 $BL$ 这条边）

首先化成代数之后发现理论上能做但是实际上根本做不了，考虑一些优美的几何意义。

把三角形 $ALC$ 绕点 $A$ 逆时针旋转 $90$ 度，$K$ 和 $L$ 贴在一起，$C$ 转到 $C’$。导一下角发现 $\angle BKC’$ 是 $60$ 度，意味着 $BKC$ 是等边三角形。这么优美的转化，一定说明我做对了。

但是有漏掉的条件——斜边是 $38$。发现：$BA$ 和 $BC$ 夹直角，对边 $38$；$BA$ 和 $BC$ 夹 $30$ 度，对边 $14$。显然余弦定理可以刻画这两个很像的条件，然后两个未知数两个方程解出 $AB = 26$ 和 $AC = 16 \sqrt 3$。

接下来体力活，$K$ 向 $AB$ 作垂线长度 $3 \sqrt 3$，$L$ 向 $AC$ 作垂线长度 $2$，不难算出 $[BKLC] = 104 \sqrt 3$，输出 $\boxed{104}$。

P.S. 图上那个连 $BL$，其实做法和我本质相同，因为三角形 $BKL$ 和 $ALC$ 全等。

Problem 15 (Hard)

（多项式、高次方程、大计算量）

$f(x) = \frac {(x-18)(x-72)(x-98)(x-k)} x$（$k > 0$，定义域 $x > 0$）在恰好两个位置取到全局最小值。

可以证明这样的 $k$ 有 $3$ 个，求出它们的和。

自己的瞎想

分母恒正，分子很有穿针引线法的味道。

令 $\langle a_1, a_2, a_3, a_4 \rangle$ 为 ${18, 72, 98, k}$ 排序之后的结果。$f(x) = \frac 1 x \prod\limits_{i=1}^4 (x-a_i)$。

先不考虑 $k$ 恰好 $\in {18,72,98}$ 的平凡情况。

为了说明方便，令 $(a_k, a_{k+1})$ 这样的区间为“根区间”。

在 $(a_1,a_2)$、$(a_3,a_4)$ 这两个区间 $f(x)$ 能取到负数。

通过对数求导法可知：

极值点处：

我们惊奇地发现等式左侧在任何一个根区间上都是一个单调递减函数（这一步是穿针引线法证明中的套路）。这意味着在每个根区间上都最多只有一个极值点。

也就是说，两个极值点必须一个在 $(a_1, a_2)$，另一个在 $(a_3, a_4)$。

然后没思路了。

官方解法

既然是两个一样的全局最小值，不妨直接设为 $m$。

$(x-18)(x-72)(x-98)(x-k) - mx = 0$ 恰有两根，而且左侧恒非负。也就是说，左侧必然能被表示为 $(x - x_1)^2 (x - x_2)^2$ 的形式（其中 $x_1, x_2 > 0$ 且不等）。

把 $t \in {18,72,98,k} = A$ 挨个代进去，得 $g(t) = (t - x_1)^2 (t - x_2)^2 - mt = 0$，所以 $A$ 中的元素恰好就是 $g$ 的 $4$ 个根。

对比两侧不带 $m$ 的系数：

消掉 $x_1$ 和 $x_2$ 得到：

令 $u = \sqrt{\frac k 8}$，暴算：

解方程得到 $u \in {1,2,5,8}$ 即 $k \in {8,32,200,512}$。考场上可以参考的解法：观察不难发现 $u=1$ 是根，方程变成 $u^3 + u^2 - 46u + 80 = 0$，然后接下来 ${2,5,8}$ 能猜出任何一个（$80$ 的因数还蛮多的……好在这三个根都小），剩下两个都能解二次方程算出来。

题目说了 $k$ 有 $3$ 个很友好，接下来只要排掉一个增根。我们没有保证 $k$ 必定能让 $x_1 \ne x_2 > 0$。在这样假设的前提下我们推导出了 $()$ 式，然而发现 $k=512$ 不满足 $()$ 式，也就是它不满足 $x_1, x_2$ 要有的条件。

事实上，Mathematica 解出来的是 {x1 -> -21.6952, x2 -> 371.695}（$175 \pm \sqrt{38689}$）。这个解的性质比较奇怪：$x_2$ 处是正常的 local minimum，而 $x_1$ 处是一个 local maximum。$f(x_1) = f(x_2)$ 这点倒没变。

最终输出 $8 + 32 + 200 = \boxed{240}$。

碎碎念 Problem 8

我觉得这个题有点说法的。

令 $a’ = \frac a {\gcd(a,b)}$，$b’ = \frac b {\gcd(a,b)}$。

$z$ 不变时，最大化 $x$ 即可最小化 $x+y$。

若 $z = n \bmod \gcd(a,b)$ 是最优解的必要条件，则贪心算法正确当且仅当 $n$ 充分大且 $(n \bmod a) \bmod b < \frac a {\gcd(a,b)}$。

在 $z_0 = n \bmod \gcd(a,b)$ 的条件下，求出一组解 $(x_0, y_0)$。

$x + y + z$ 最小化，即 $t$ 最大，$t = \lfloor \frac {y_0} {a’} \rfloor$，此时 $y = y_0 \bmod a’$。

$x + y + z = x_0 + y_0 + (n \bmod \gcd(a,b)) - (a’ - b’) \lfloor \frac {y_0} {a’} \rfloor = $。

考虑 $z_1 = z_0 + \gcd(a,b)$。

$x + y + z = x_1 + y_1 + (n \bmod \gcd(a,b)) + \gcd(a,b) - (a’ - b’) \lfloor \frac {y_1} {a’} \rfloor$。

以后有点什么想法再回来吧。