Part 1 题目列表
- P7075 [CSP - S2020] 儒略日
- P7076 [CSP - S2020] 动物园
- P7077 [CSP - S2020] 函数调用
- P7078 [CSP - S2020] 贪吃蛇
Part 2 考试时间线
8:02 开题， 仅仅读了 10 分钟 T1 题目，就得出结论，大模拟。
9:20 在与 T1 长达 ···（数不过来了） 的搏斗后，成功过了大样例，快速开 T2。
9:50 十分钟看题，十分钟写题，十分钟调题（算多了一点），一遍过大样例。
11:00 当时一看，这不明显的数据结构大水题吗（看看我那惊人的判断力），最终没调出来。
11:20 只好写了一个超级大暴力。但当我把视野望向那仿佛遥不可及的 T4 时，却发现这不是 贪吃蛇 吗，我以前可是做过的，但是没调出来。
12:00 结束，开始担心未删调试。
Part 3 题目分析
T1
都说了是 超级打分讨，当然要加一点二分。
错因：
有一个 1582 写成了 1982
T2
最简单的一道，就不再多说了，要注意的是，答案最大值为：
开 unsigned long long 都会爆。
所以要特判。
T3
考完后成功发现时间复杂度是伪的。
首先这怎么看都像是一个图论，因为通过函数的调用关系，可以很轻松的建立一个 DAG 出来
比如这组数据：
【输入】
1
0
5
1 1 1
2 2
2 4
3 2 1 2
3 2 1 3
2
4 5
【输出】
12
可以建出如下图：
这里补了一个 0 号节点作为主函数，相当于只是调用一个主函数
首先我们发现：
所以我们只需要分别知道原数组乘的倍数，和每一个加数乘的倍数即可。
第一个十分简单，一个反向建边，加一个拓扑即可。
而第二个有一点需要注意，我们要反向枚举边，因为是后面的影响前面的。
T4
这里做一个分类讨论：
-
最大的蛇吃了最小的蛇不是最小的蛇
【策略】
应当吃掉，如何都不亏（证明略）
-
最大的蛇吃了最小的蛇是最小的蛇
【策略】
最开始我们头脑简单的认为这当然不能吃，因为吃了自己下一轮也得死，但是当我们再往下面枚举一层：
-
下一轮最大的蛇吃了自己不是最小的蛇
因为这条蛇会选择吃你，因而你在这一轮不能吃
-
下一轮最大的蛇吃了自己是最小的蛇
这里又要看下下一轮的蛇
-
我们发现这是一个递归的过程，一但要考虑第二种情况就会递归到：
- 蛇的数量为 2
- 这条递归到的蛇吃了后不是最小的蛇
且满足：
- 上个蛇要吃则这一个蛇不吃
- 上一个蛇不吃则这一个蛇吃
（满足奇偶性）
Part 4 总结
| 题目 | 预估分数 | 实际得分 | 核心算法 | 错因 | 改进方案 |
|---|---|---|---|---|---|
| 儒略日 | 100 | 70 | 模拟+分类讨论+二分 | 1582写成了1982（luogu上出现了一些TLE，但LemonLime没有） | 在检查时检查一些特殊情况（边界，如这道题的1582年） |
| 动物园 | 100 | 95 | 位运算 | 未考虑 ans=(1<<64) 的情况 | 检查特殊情况，查看是否越界 |
| 函数调用 | 45 | 45 | DAG拓扑+思维 | 方法选错了，且特殊性质没调出来 | 当发现不能在短时间内找到正解的话，先保证打满部分分 |
| 贪吃蛇 | 20 | 20 | 贪心+优先队列 | 时间不够，只能打完20分 | 节约时间 |
总分：70 + 95 + 45 + 20 = 230
预期得分： 100+100+45+20=265
改进方案：
- 在检查时检查一些特殊情况
- 当发现不能在短时间内找到正解的话，先保证打满部分分
- 节约时间