第 16 届 Python A 组（国赛）

Tip

国赛没有把代码带出来，所以就简单回忆了一下。最后二等奖收尾。

T1

显然，4052。

双重循环，外层枚举 a，内层枚举 2025 的倍数，及时 break，用 C++ 瞬间算出来 190000。

显然的贪心，数位之和为最高优先级进行考虑，那么除了 100...00 的形式不用改变，其余全部贪心为 100...00 的形式即可。

显然的递推，每次只需与前一个状态进行比较，从次高位考虑补 0 即可。

熟悉的 n-gram，缓存查询的所有 n-gram 之后枚举原始文档逐个匹配即可，时间复杂度约 \(O(nm^2)\)，其中 n 为文档数，m 即窗口大小，约 20。

树上距离最大一眼直径，注意到直径长度为偶数时中点一定存在，易证直径长度为奇数时无法找到中点，因此直径长度为奇数时减一即可。

结点数规模为 5×103，每个点都跑一遍 DFS 统计一下即可。

暴力了，单星号 split('/') 之后诸位比较即可，双星号 split('/') 之后分别比较前缀与后缀即可。大约可以拿 60% 的分。

暴力了，直接预处理一部分的杨辉三角然后统计结果，在 n 不超过 1000 的情况下可以保证结果正确。大约可以拿 40% 的分。

暴力了，暴力就很显然了， \(O(n^2)\) 可以拿 50% 的分。