例行游记 awa
# 小引
去年曾笑说“CSP2019 可能是唯一一次我作为 OIer 参加的 CSP 了”……看来我对 CCF 的了解甚少，现在沦为弯道收费的工具的 CSP 被赋予了与去年 NOIP 的代替品不同的含义。
若说CSP2019关乎2019省选的生死大计，CSP2020 作为一次“评级”的NOIP入门券显得似乎没这么重要，仅是取得入门资格对同学们的压力也小了许多（以至于没有停课马上还要考半期）
但是正如教练所说，作为 CCF 的“官方 NOIP 模拟赛”，需要给予足够的重视。
# 分享
- 经历
大概就是一些考场经历以及较为重要的——策略吧……（希望不要扯远了 flag）
考场不在巴蜀了太开心了离学校好远……一个小时的车程基本上全程在睡觉，再加上吃完饭还没12点就继续睡觉，反正在考场上一点都不困（甚至还有些兴奋 (￣▽￣)”）。
找到座位后熟练地加上了 MinGW 路径，添加了Dev编译命令（-Wall -Wextra -Wshadow -Wconversion -Wl,--stack=2000000000 也是我比较建议加上的），解压文件包然后开考。
开始10min+还是和往常一样通读题面，特别留意了
- 每道题的时空限制，确定不卡内存，T3T4可能有点小常数。
- 编译选项，没有 C++11 没有 O2（建议平时就不用 C++11 免得改不过来，虽然现在已经 20 年了CCF还在用 C++98 说不过去）
接下来顺序做题。
当时看完题面就觉得艹什么东西好难理解，画了一张时间轴标了几个关键节点：公元元年第一天、儒略历最后一天、新历第一天。大概思考了一下决定写一个暴力计算两天之间的天数，这一点我觉得非常有帮助。
其实一开始T1写了30min+还没有写出来（后来发现是自己脑抽写错了年份），然后果断跳到T2并且装成T1已经写完了的样子。
然后T2在一开始看完题后的 定位是送分题（但是实际上这里有失误，下面再分析），而且注意到读入的数有点超级大，写了大概20min再调了10min就“做完了”。倒回去做T1，心态非常轻松，大概10min在验算的时候发现了问题，然后测过大样例就OK了。
T3的题意也比较烦，第二遍看题才完全弄懂，定位在中难档题。看懂是个DAG后果断判断要拓扑，想过离线，想过计算贡献，可惜没有找对算贡献的方法，分析数据规模发现
- 前4个点以及没有第三类函数的点可以暴力；
- 另外没有一或二函数的点可以简单拓扑算贡献。
预估 50pts，写完过后发现没有几个部分分的样例，就手改了一下样例1，用自己的暴力和优化计算对拍了一下，没有问题然后就过了。
T4 定位是压轴题，所以一开始就没想正解，只是尽可能地想结论，然后直接看部分分。其实根据博弈论的一些简单定义，比较容易想到部分分的做法。
一开始只写了 $O(n^2T)$ 的部分分，写完过后发现“我为啥要写成这样？”而且当时还很早（指≈1h20min），果断用set优化了一发改成了 $O(n\log nT)$，简单调试之后过了大样例，然后非常没有B数地试了一下手造的极限数据，果不其然地TLE了，于是预估在 70pts。
最后花了很久检查，T1 把 5e6 以内的都输出来看了，确定是连续的并且闰年没有问题；T2 测了最大输入（还是没注意到最大输出）；T3 用暴力生成小数据和特殊性质对拍；T4 好像没怎么管？（因为不知道怎么写暴力……）
- 所得
这次测试中可以说是自得的一些点。
- T1的辅助暴力写得非常及时；
- 心态极好……（指T1还没写出来然后去gan了T2）；
- T4很有觉悟，想不出来正解就拿最高的部分分；
- 所失
希望下次不失，毕竟我还有“下次”，至于有多少次“下次”就看表现怎么样了。
- T2定位虽然没错，但是有点掉以轻心了。经历过CSP2019的格雷码卡
unsigned long long，注意了读入也需要 ull，但是忽略了输出甚至可以是 $2^{64}$ 会爆 ull（卡数据类型卡得越来越过分了QwQ）；另外读漏了条件，做复杂了，而且复杂度多了个 log；总共洛谷上卡掉了 3 个点…… - T3其实有时间想得更深入，当时保险花了很久对拍检查，反正在“硬刚”和“保守”之间必须有一个平衡吧；
- 还是T3，对数据规模没有个B数，根本没想一个函数的调用次数有多大，会不会爆MOD，反正在洛谷上挂了两个点；
总体而言，即时预估分是 320pt，自测分 295pts（T2 -15pts,T3 -10pts），乐观预估分 300~310 pts，极低预估分 260pts（T2 -40pts, T3 -20pts）。
# 题解
现在写了 T1~T3……
T1 简单提一下，分成三段，公元前儒略历，公元儒略历，公元格里高利历，可以暴力跑出分段时间点；儒略历先4年为周期分段，每个周期的最后一年闰年，然后简单算算是多少个周期，周期内的哪一年月日；格里高利历再分段，分为 1600.1.1 前和 1600.1.1 开始之后，前者直接一开始暴力处理出答案然后回答，后者 400 年为周期，可以先把 400 年为周期的某一个时间点的年月日暴力跑出来，于是只需要判断在哪个周期。
T2 由于不同的数位对应的饲料不会有交集（不知道有没有人也读掉了这个条件），于是一个数位对应了哪些饲料根本不重要，重要的是它是否对应了饲料。如果一个数位不对应饲料，则这个数位当然可以选；否则当且仅当该数位出现在已有的动物中时才可以选。统计出有多少个数位可以选，记为 cnt，则答案就是 $2^{cnt}-n$，用 unsigned long long 储存。但是如果 $cnt=64$ 且 $n=0$，答案就是 $2^{64}$，ull 都存不下，只能计算器算出答案直接输出……
T3 我觉得思路挺不错。
称第一二类函数为“底层函数”，把调用关系看作有向边，则构成一个底层函数无出度的 DAG。对于函数 $i$ 定义 $t_i$ 表示它总共被调用了多少次。称调用一个函数为“一个时刻”。
如果真的模拟非底层函数的递归过程，复杂度显然不可控，考虑计算每个底层函数的贡献。这里部分分给了很好的提示：
- 如果没有加法函数，则乘法函数的贡献就是对每个数有 $\times v_i^{t_i}$ 的贡献；
- 如果没有乘法函数，则加法函数的贡献就是对 $p_i$ 有 $+v_it_i$ 的贡献。
定义函数 $M(i)$ 表示在 $i$ 时刻之后的调用的所有乘法函数的 $v_i$ 之积。
那么考虑加法和乘法之间的影响，乘法对加法的影响比较好考虑——设函数 $i$ 被调用的时刻为 $T_i=\{t_1,t_2,\dots,t_k\}$，则它对答案的贡献是 $v_i\sum M(t_j)$。
于是现在问题就是对于所有的 $i$，怎么算 $\sum M(t_j)$（记为 $g_i$），由于是 DAG，不难想到拓扑。
先来一遍拓扑跑出 $f(i)$：调用 $i$ 函数后会对答案产生 $\times f(i)$ 的贡献。然后对一个非底层函数，跑出一个“后缀乘积” $S_i(k)$：调用 $i$ 函数时，在执行它的第 $k$ 个之后的子函数会产生多少乘法贡献。
则对函数 $u$ 的第 $k$ 个子函数 $v$，可以写出转移式：
两遍拓扑就可以了。另外有个小技巧是把输入的函数调用操作新建一个函数，当作新函数的子函数，可以省点事。
THE END
Thanks for reading!
> Linked 故海潮生-网易云