2024.9.3-CSP模拟赛2
考试：
9:00
开题：
- 第一题第一眼数据范围 \(1\le n\le 5\times 10^7\)，感觉有 T 的风险。
- 第二题 little bird，记得在以前做过这道题。
- 第三题不太会，没有给部分分的比值，感觉只能写个暴搜。
- \(O(n^2)\) 的暴力肯定会，正解先待会再想。
9:10
做 T1，直接写暴力，5 分钟写完了。
试了一下 50000000 和 2，感觉跑得很慢，考虑优化一下。
发现每次 \(i+1\) 如果没有进位的话，直接手动计算要快得多，于是就赶紧写了这种情况。
if(i%10>(i-1)%10){
cnt1=cnt1-val[(i-1)%10]+val[i%10];
}
写着写着突然发现自己写的 \(count\) 函数没有特判 0，赶紧先将 0 的情况了出来。
再试了一下 50000000 和 2，虽然快了一点，但还是超时了。
- 模拟进位
9:40
写到了 1000 的进位，感觉可以了，便将 T1 放了，转头去做 T2。
T2：little bird
我脑海里依稀记得 LJ 讲这道题的时候提到了二分，于是写了 solve 函数，但问题来了 check 怎么做？？？
心里有了一个贪心想法：
- 对于第 \(i\) 只鸟当前在第 \(j\) 棵树上，如果在 \([j,j+k_i]\) 的区间内，有 \(d_l<d_j\) 且 在这些 \(d_l\) 组成的集合中 \(X\) 是最大的，那就飞过去。
- 如果发现 \(d_l\) 组成的集合是空集，说明此时必须增加疲劳值了，那就一定去能飞到的数中最高的一棵。
问题又来了，怎么快速求出呢？
线段树吗？好像要维护的东西很杂，写又可能写不对，怎么办？
- 直接暴力。
10:20
终于写完了 check 函数，自己造的样例和 PDF 上的样例都过了，但时间不能保证。
我突然发现，如果说我在 check 中使用的是贪心策略，那么每次贪心的结果一定就是这只鸟的最小疲劳值，所以二分答案有什么用呢？
加一个 Try 函数，样例全都过了，但感觉时间复杂度还是 \(O(n^2)\)，算了，写 T3。
10:35
没什么思路，先把暴搜打出来吧。
样例最后一个直接 T 飞了。
啊啊啊，不会做啊。
10:45
回去看看 T1。
突然发现自己的优化可能会导致在出现 cnt1 叠加的情况，算了删了吧，就留一个不进位的就行了。
11:00
T4 不太会，式子推了一些：
\[a_i+a_{i+1}+...+a_j \ge k\times (j-i+1)\Rightarrow sum_j-sum{i-1}\ge k\times (j-i+1)
\]
然后就暴力了。
总分：
预计得分：80+50+10+40=180
实际得分：70+89+30+15=204
主要还是第 4 题的原因。
总结：
- 对于之前做过的题目还不够熟练，应该多练习，吃透内容。
- 要深入思考题目，多使用草稿纸和画图软件。