背景
我是广东省赛区的pythonB组大一选手,这次拿到了省二第四名的成绩。拿到排名也是被自己笑到了,大致算了下172个省一,我排在176,只能说是一种遗憾吧,没能晋级国赛。自己也是投入了三个月左右的时间备赛吧,刷了差不多六七百题,感觉有点可惜了。
血的教训
其实这次pythonB组的题目还是比较简单的,但不知道是状态的原因还是这OI赛制给的压力,做题明显没有平时那么顺手,失误频出。
先简单分析我每道题的不足之处:
第一道:
这是一个基础的进制转换题,数据量很小,遍历判断就可以过。但不知道是不是当时脑子不清醒,进制转换最后一步应该返回剩余的数n,我写成了1,最离谱的是我写完之后还带了3个数验算刚好符合。考完出来看群里聊答案为六十几的我已经懵了,因为记得我的答案是一百多的。(后面还安慰自己不就5分而已,现在看来,这5分已经可以帮我冲到省一了................)
第二道:
一开始拿到这题时,数据范围看错了,以为数最大为1e5,看到不包含什么什么数字的数,最先想的还是数位dp,但感觉填空不会考这个,又再看一下数据范围,发现是长度1e5,确实不应该是这个方法。随后又想字符串,或者暴力循环求解,但想了一下差不多十几次方的数据量,比赛结束都跑不完。然后又刚好想到之前做过题目是用容斥原理解题,其实理解之后感觉跟高中那种求排列组合问题有点像。但第一次求解过程我主观臆断地把并集的值减去,到最后检查再推一遍的过程也是把这个错误找到了。
第三道:
这其实是一个简单的模拟题,就对每个位置的两条对角线进行一个计数统计。一开始我看成了就对该坐标的四个对角方向的位置进行判断统计,然后又刚好满足给的样例。不过还好最后检查的时候又仔细理解了一下题目的含义,明白了是对角线的所有位置,而非仅仅四个角。也是让我挽回了一点损失
第四题:
这是一道让我久久不能平息的一道题。这题是关于日期的计算。在比赛前本来想复习一些关于日期的内置datetime函数,但是想了想感觉也就填空题会遇到,实在不会用可以看一下帮助文档。但没想到会出在大题,看到题目感觉可以用函数简化一下代码,但是真不清楚哪些函数有用,就只能用字符串模拟一下了,为简化时间复杂度,还预处理了一些日期的情况。但最最最最最让我没想到的是这题答案输出是有格式的,我写了差不多一个小时,最后因为格式问题一分都没有,实属破防了。
第五题:
实话说,第一眼看着很复杂,但是当我看到数据范围1e18,询问次数1e5的时候,就知道这题不是用什么算法来解题的了,绝对是一个数学方法或者找规律。但但但是又让我没想到的是,读题的时候没看到人物的位置是处于环形,把他位置当作是一排来找规律解题。结果可想而知,还是0分。
第六题:
看到题目意思后感觉和那种跳格子挺像的,觉得是那种动态规划的思路,但在那个条件判断上面又是读错了题目,要找到至少包含一个特定元素,也是忘记考场上读的题意是什么了,反正能过样例,但后面的状态转移方程条件肯定错了,又是白给
第七题:
这题是一个类似于求路径花费小于一定值的路径数量。其实当时印象中好像是做过类似的题目,但是有些条件变动也不是很清楚。一开始想套Dijkstra算法,但发现好像条件不太适合,样例也没过去,就pass掉这个思路了。然后又想了一下感觉可以用并查集写,写了一大半后发现有些细节条件又不好处理又给pass掉。无奈只能回Dijkstra算法继续处理。调了半个小时发现样例能过就放一边了。之后检查时造了一个样例,然后发现并不能过去,找了半天bug之后选择了用多源bfs的方法暴力计算,虽然不知道最后拿了多少分,但应该还是能过一大半的
第八题:
这题其实没抱多大希望能做出来的,凭着自己的理解和感觉写了一个满足样例的解法。感觉自己的理解过于简单了,应该不能过去,赛后也懒得去看正解了。
总结:
读题不仔细,好几题因为题意读错或没理解到位,导致细节处理不行,只是能过样例,并不能过完全部例子
心得感受:
正如传闻所言,蓝桥杯获奖确实不难,但完全不学算法想拿奖还是有点难度的。
蓝桥杯的题目大致分为这些类型(好拿分的):
1.暴力计算(填空):适用于第一个填空,数据量不大的题,通过题目给的条件筛选答案,一般也就跑个几分钟就出答案。
2.技巧计算(填空):适用于第二个填空,数据量一般能达到1e15往上。我们知道,程序1s大概能跑1e8的操作,1e15就要10000000s了,直接比赛结束都跑不完,还可能给电脑整崩溃了,所以需要我们观察出一下数学技巧之类的能走捷径得出答案。
3.模拟题:适用于3-4题:这类题目通常数据量不大,根据题意的要求模拟,就是那种写几个for循环和if判断,然后计数得答案的那种,一般也用不到什么算法,就算数据量大,暴力模拟也是能拿分的。
4.简单算法模板题:这类题目有很明显的特征,就是能感受到这题做过,知道用什么方法去解决,但又和印象中的不同。这是因为有条件的变动,所以不只是套模板就能解决的,但是理解了题意之后稍加修改一些条件就能通过。
5.有难度的思维题:遇到动态规划这类题目就不会太简单,涉及有状态定义和状态转移方程,这类题目就需要有一定的题目累积,不然几乎无从下手,因为dp本身也算是一种暴力,要加强难度还可以结合各种算法才能完成优化。
结合上述题型来看,如果想在短时间内拿奖其实也是不难的。如果有语法基础并懂得各类函数的使用,基本上稳一点拿个二三十分也是可以的。能再把各类模板都学一遍,懂得如何运用,也是能突破四五十分。如果想拿高分,就需要留出充裕的时间去系统地学习了。有一说一,蓝桥杯获奖容易,但题目确实是不好做的,后面题目不会只考套路的,更多的是思维:题目算法难度<题目理解。
后续安排:
经过这次的比赛也是暴露了自己的缺点。平时一直在那种ACM,IOI赛制下写题时很难保证一次把题目写对,都是wa一下才能看清题目意思,所以后续也是要注重这方面的学习了。
虽然没能晋级蓝桥国赛,但后续也是有很多的比赛。天梯赛(GPLT),GDCPC(CCPC广东省赛),百度之星,CCPC(网络赛),CCPC(区域赛),这些比赛都是有相当难度的,但可以当作历练刷经验吧。
然后也是尽量每天刷个几题保持手感,在力扣,蓝桥,牛客平台参加周赛,等有能力了再参与cf的周赛。