NOIP冲刺之超市T2计划(upd on 1028)

发布时间 2023-10-28 10:26:32作者: 铃狐sama

超市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

很明显的一种贪心题目,甚至不用dp,排个序乱杀就彳亍。
为什么还要放在T2难度呢?毕竟贪心的这个性质还是要你自己去找(去推柿子的)

方圆幂积:T3

我觉得这道题对我而言值得放T3难度。
首先我就被诈骗了,以为是数论。
过了很久才发现,这个输入long long都不行,只能是字符串。
那就是字符串的题目了。然后发现随便乱搞hash一下就能过。

打地鼠:T1

纯粹暴力,差分前缀随便用一下就行了。太简单了。

取相片:T3

为什么放T3难度呢?因为感觉也有点像诈骗。
博弈sg函数是我第一眼想到的,但是觉得没必要,就觉得贪心。
然后分析了半天什么时候应该取,什么时候不应该取,然后wa 10 pts。
其实没必要,完全可以看成能选就选,最后减去最差情况。
那么什么时候能选就选呢?完全可以看成两个人中有选择就选择这样。(感觉说的不明不白?)
反正最后就是整体贪心做一下就好了。

总结:

(随着刷题慢慢更新)

  1. T2难度的题目需要你突破找到某种关键性质,再设计出算法