P1
学了一些关于计数问题的 DP 状态设计及转移方式,比如连续段 DP,贡献提前计算。
对于排列问题得到两个小点,一是考虑顺序插入,二是
P2
做题
- 第一天模拟赛第二题接触到了连续段 DP。
- permutation oddness 和 摩天大楼 是两个很好的贡献提前计算。
- 学到了整除分块。
- 连续段 DP 既可以考虑顺序也可以不考虑,考虑顺序的话比较好处理两个边界。
模拟赛总结
- 第一次模拟赛。先冲第一题,冲了很久一直想不出来,没有抽象出关于质因子个数的问题骨干。后面冲不动了,去打暴力。第二题想了一下,发现可以写个状压,大概花了 30 min 写出来了。后面又去看 34 题,把暴力打完还剩半个小时,不是很甘心,又去冲 T1,无果,最终分数 80。
- 第二次模拟赛。还是冲第一题,最开始想不出来,因为考虑到点上了,后面想到一个类似区间 DP 的形式,但是其中细节很多,第一次有没有想全,就一直错,一直打补丁。后面做了一个多小时还做不出来,但感觉自己比较近了,所以还在写。后面到两个还是冲不出来,就心态很爆炸,打了一个第二题的暴力,T3 T4 也没有毅力去打了。
总结感觉还是说没有很好的心态,很容易崩,属于一鼓作气再而衰三而竭了。还有就是思考依旧并不全面,感觉总是缺少思维链条上的部分,然后以为自己会了,还有就是说,应该把前两题都看看,不要一头创死在 T1。
做题情况
1.small product 想出原始 DP,想不出来优化,看了题解发现是数论分块,发现并没有学过,看了一眼,很快写出来了,不记得想了多久学了多久了。
2. Potion 先想出判定可行的 DP,然后想如何找一个时间,发现可以塞进 dp 值里面,就做完了,思考加写差不多 45 min。
3. vanya and treasures 状态是好想的,但是不会转移,有人上去讲了,没听懂扫描线,自己用二维树状数组做了。
4. permutation oddness 上课讲的,回忆了一下,写完了没对,换了一下写法,交一下过了。
5. 摩天大楼 也是上课讲的,先回忆了一会,然后开写。写完一调发现小炸,调了多个地方后发现千疮百孔,而后重构,一遍过了,整个题可能花了几个小时。
6. jee you see 不是很会,有些地方不懂,更新方式很奇怪,看了看题解,改了枚举方式,然后过了样例,交上去被卡常了,改了很多地方一直不过,把组合数改成杨辉三角就过了。
7. Black and White Rooks 最开始没有想明白对于单个棋子的处理,想简单了,样例错了后,想了一会感觉有问题,试着想了个 DP 然后过了。
8. Construct a Palindrome 想到了双向广搜,但是没有想到那个很典的记录两边是哪个点,一直觉得不对,瞄一眼题解就顿悟了。
9. New Year and Rainbow Roads 自己想出来来了贪心的大概策略,差了一个减去最大边,思维路径不大一样。
10. Happy Life in University 看到这个数颜色第一时间没反应过来,但想到了在 lca 上统计,回忆了一下,看了 hh 的项链,然后就会了。
11. Earnest Matrix Complement 先想到一个结论,一行只填一种,只会最朴素的 DP,想歪了,去想优化 DP 状态,没有去想优化转移。看题解后很快写出来了。CF 炸了,没交上去,第二天代码没了,先咕掉。
12. [JOI 2025 Final] 勇者比太郎 2 / Bitaro the Brave 2 实在做不动难题了,开一道简单题,看到这个很想把他拆开,拆成一个差分形式,然后就可以线段树维护最小值,对于每个点跑一下就好了。