NOIP2022 总结
考前
早上主要看了点随机化和部分分写法什么的
感觉有点脱离了大纲,图论那块一直不是很好也没怎么复习
有点紧张,尽管不是现场赛,但是还是有点怕分数太低 QAQ
考试
考试题目来的有点慢,干坐板凳好急
大概13:30来了题目,看着貌似还可以做
先开T1不是很难,先花20min把暴力写了
发现直接枚举左上角点,然后二维前缀和统计就好了
45min左右写出正解,大样例寄了
大概在1h发现是二维前缀和写挂,调完就好了
看了T2,常常的一坨题面看起来很恶心
理解了之后看了数据范围,发现有k=2n-2和k=2n-1两档
当时就觉得是分类讨论,然后只想出了k=2n-2怎么构造,1h15min写完
然后推了30min发现,k=2n-1不会构造,心态有点崩了 QAQ
果断放弃看T3,是道图论题,先写了暴力
由于是无向图,就没往tarjan去想,稍微推了几种情况,感觉有点像路径计数?
在2h20min左右时放弃了T3,开了T4,发现T4好像可以分治
然后就先写了一个每次跳后继的做法,时间复杂度O(nq)~O(n^2q)
然后把两个数组化成曲线,两张图和起来,好吧很抽象,花了很大力气才看懂
发现如果左指针从右往左移动,后面有一段贡献是重合的,也就是只要更改前面一小段
估计复杂度在O(nq)~O(nqlogn)之间徘徊
比较难调,但是52pts太多了,就直接上了
大概在3h10min时过样例(最后因不知名原因寄调了),顺便再写个暴力
再回去看了看T3,发现树的不好做,但链的可以
yy了一个链的做法,O(n^2)
太麻烦,就打个表看了下前几项,暂时没找到规律
抱着试一试的心态去干了T2,尝试几种构造,都不对wwww,干脆直接把k=2n-2之接照搬,事实证明有点用
最后十几分钟,尝试看了下T3的链,比较急,写完差不多就交了
结果因为平时习惯,没看返回值,最后RE了
总体来说感觉思维还不够,两个操作系统的差别不是很适应,导致了挂分
考后
咕了一波大概是100+15+25+8=148
最后infoj是100+30+15+0=145
一个是return值没注意,一个是因为没注意到linux下使用uint缩写会重复(考试环境windows)
挂了18分,本来应该有145+18=163的,还是差点
总的来说平时还是要补补图论,做做构造题提升思维,然后注意代码细节(return值,数组清空,两个系统编译不同)
还有就是心态的调整,做不出题目不应该先那么急,还是要冷静分析,不然越想越遭
平时训练不应过度依赖编辑器,最好保持和正式考试相同的配置环境,悉知linux与windows的不同
(ps:uint我是真的不知道啊)
标签:有点,发现,T3,NOIP2022,2n,考试 From: https://www.cnblogs.com/Maraschino/p/16933461.html