CSP-S 2019，T1：使用
unsigned long longCSP-S 2020，T2：需特判 $2^{64}$
NOIP 2020，T1：需要使用简单高精度
NOIP 2021：？？？？
CSP-S 2020
T4 暂缺。
【T1】 儒略历
模拟，注意细节即可。
1 |
|
【T2】 动物园
对每一个二进制位分开考虑；明显，如果不存在一个动物编号 $a_i$ 使得此二进制位的值为 $1$，并且《饲养指南》里存在对这个二进制位的要求，那么不能饲养编号含这个二进制位的动物，反之可以。
记合法二进制位数为 $cnt$，则答案为 $2^{cnt}$。
将每个 $a_i$ 二进制分拆即可。时间复杂度 $O(n \log \max(a_i))$。
注意特判答案为 $2^{64}$ 的情况。
1 |
|
【T3】 函数调用
一道好题。
题目中提示不会出现递归，故所有函数的调用关系形成一个 DAG。
如果只有 2、3 两类函数，那么我们可以用拓扑排序或者 dfs 直接算出某个函数对答案的影响。
如果只有 1、3 两类函数，那么我们可以用拓扑排序求出每个第 1 类函数的执行次数。
接下来的讲解先鸽着，有时间来填。
1 |
|
【T4】 贪吃蛇
NOIP 2020
【T1】 排水系统
拓扑排序后，依次处理即可。
注意答案分母会达到 $60^{11}$，需要使用简单高精度。
1 |
|
【T2】 字符串匹配
一种做法是扩展 KMP，此做法时间复杂度为 $O(n)$，此处略去不讲。
枚举 $A + B$ 长度，并且每次二分其 $i$ 的最大值。这里是 $O(\sum_{i=1}^{n} \log(\frac{n}{i}))$ 的，简单分析可知这个是 $O(n)$ 的。
同时可知，在 $i$ 同为奇数时，拆分 $A$、$B$ 的方案数是一样的，偶数同理。故可以 $O(\log 26)$ 统计贡献。
故本题解决。时间复杂度 $O(n \log 26)$。
1 |
|
【T3】 移球游戏
同 Dzhao 的做法。
考虑只有两种球的情况，不难构造出一种 $5m - t_1$ 步的做法，其中 $t_1$ 为 1 号柱子中的 1 号球的个数：
- 第一步：将 2 号柱子中顶部 $t_1$ 个球移至 3 号柱子，耗费 $t_1$ 步。
- 第二步：将 1 号柱子里所有球按如下规则移至 2、3 号柱子，耗费 $m$ 步：若柱子顶部为 1 号球，则将该球移至 2 号柱子，反之移至 3 号柱子。
- 第三步：将 2、3 号柱子中原来属于 1 号柱子里的球全部移回 1 号柱子，耗费 $m$ 步。注意：这一步需要让 1 号球与 2 号球分离。
- 第四步：将 2 号柱子里的所有球移至 3 号柱子，耗费 $m - t_1$ 步。
- 第五步：将 1 号柱子顶部的所有 2 号球移至 2 号柱子，耗费 $m - t_1$ 步。
- 第六步：将 3 号柱子里所有 1 号球移至 1 号柱子，所有 2 号球移至 2 号柱子。耗费 $m$ 步。
- 总计耗费 $5m - t_1$ 步。
扩展到 $n$ 种球的情况，考虑进行分治处理：定义函数 solve(l, r) 为保证 $l$ 至 $r$ 号柱中只含有 $l$ 至 $r$ 号球时的复原过程。
为了将 solve(l, r) 退化至两种球的情况，不难想到令 $mid = \frac{l + r}{2}$，若颜色 $x > mid$，则令其为 2 号球，反之为 1 号球。
具体实现时，需要以 $mid$ 为界，两端分别枚举未被还原的柱子。注意确定好需要还原的柱子以确保有柱子能在这轮操作中被还原，且第六步中需要稍作改动。这些细节留给读者。
期望步数为 $5mn \log n$。
1 |
|