山大校赛 2024 预赛 ABCDEFG 题解

H 等等再更（一周内），I 因为太菜目前不会。

按本人认为的难度顺序排序。

A

自评难度：红。

大纲（本人做法）：

• 【1】初中代数（J）

根据样例发现山大建校于 年，故将输入的年份减去 即为答案。复杂度 。

B

自评难度：橙。

大纲（本人做法）：

• 【3】贪心法（J）

对于第一问每个位置直接判断填加号大还是填乘号大即可。

对于第二问，考虑什么时候我们会放加号。发现只有乘 是不如加 的，所以只有所有的 之间，以及如果只有一个 的话 和第二个数之间放加号，其余均放乘号。由于乘法和加法都有交换律所以直接从小到大排序跑第一问的贪心就做完了，复杂度 。

C

自评难度：黄。

大纲（本人做法）：

• 【4】动态规划的基本思路（J）

很难不注意到那个小得要死的徵羽。显然将所有数都变到徵羽之外一定是不优的，于是想到对每次询问枚举最终变成的值，现在考虑快速求变成一个值的代价。仍然是因为徵羽很小，容易想到直接拿前缀和存。我们开个二维数组 表示前 个数都变成 的代价，就可以做到 枚举每一个值了。这样总复杂度是 的，其中 是徵羽。

E

自评难度：下位绿~中位绿。

大纲（本人做法）：

• 【9】构造思想（NOI）（只能找到这个了？）

结论：拿完数量为 的石子堆之后的先手必胜。

因为此时的先手只要每次把最小的那一堆拿成剩 个就可以一直先手，直到最后一堆一次拿完。注意特判一下全为 的情况。

其实想到结论的过程也比较顺畅。因为拿到最后一堆的时候先手必胜，所以倒数第二堆的时候先手就希望自己在最后一堆还是先手，然后就可以想到只留一个控制住对方，这样以此类推就是结论。

G

自评难度：中位蓝~上位蓝。（跟所涉及的内容有关，其实远没那么难。）

大纲里没有找到相关的内容。

据我校 MO 教练透露，该题结论 MOer 需要背诵。但我显然不会背，因此打出 至 的表，发现结论是除了 外均有 。于是套等差数列求和公式就做完了，复杂度 。

F

自评难度：上位蓝~下位紫。

大纲里没有找到相关的内容。

费马大定理 不存在三个正整数 使得 ，这里 为大于等于 的正整数。

这个玩意的证明困扰了数学家好几百年所以你不可能需要会，除非你也想变成那样的数学家。

枚举 并二分（或开桶）查找 预处理出 的情况，然后这道题就做完了。

吗？

发现定理中的 是正整数，而本题中的值域是从 开始的。这意味着还有 的情况需要进行特判。具体调多久就得看你造化了……

D

自评难度：下位蓝~中位蓝。

大模拟不讲。