超市T2计划总结
目录声明:
本贴用于总结对于csps-noip T2左右难度的题目。
会选择一些NOIP的题目,或者是codeforces过的人数在1500~3000的题目。
然后分为了 T1-T6 6个级别
也是为了超市NOIP T2
这种题目简单的话就只考察思维和简单算法,中等的话可能会让你自己设计某种和常见算法思想的算法(如dp),难的话可能涉及到容斥计数啊什么的。
刷题:
三国游戏:T1
发现性质题目,简单到爆
尼克的任务:T2
首先你要想得到dp。
我个人说实话没想到倒着dp,正着dp倒是想到了,但是用了个vector记录某个值前面可以由什么转移过来这里可以简化。
具体的话等过了这道题可以luogu上搜索LingHusama看我的思路(写在代码里的),讨论区我和青白大佬也讨论了我的70pts问题
都找到前面哪些情况可以转移到此,那么直接从前往后递推给贡献就好了。
还有要注意初始化数组问题
卖萝卜:T1
最开始以为是dp,但是存的状态可能会很多,然后想到了商店情况一定是选择购买。所以就发现可以贪心。
但还是没有一遍过,原因在于找front的时候没有看是否为空的,然后RE。
剔除多余括号:T2
简单是简单,但是有坑,代码也比较难写
坑:a-(b-c)不能去掉
引水入城:T3
为什么放在T3难度呢?因为你要发现区间覆盖的性质。
感觉还是有点难的,关键在于看你能不能发现如果成功的话,就变成了贪心区间覆盖问题。
如果你能覆盖的话,一定是覆盖了连续的一段区间。
其次还要记忆化搜索,这个确实没想到。
Medium Design :T3
这个就是纯粹的发现性质题了。
为什么放在T3难度呢?因为我写假了,最开始思路错的
性质就是:你最小值一定会出现在1或者m处。
然后呢,只要我不覆盖1/m就好了。
然后两种分类讨论下,做个离散化、差分找最大值就好了。
总结:
(随着刷题慢慢更新)
- T2难度的题目需要你突破找到某种关键性质,再设计出算法