蓝桥之旅


关于这次比赛

第一次以非专业组参赛,完全出于兴趣爱好,因为喜欢数学,因为热爱编程,迷之于计算机网络技术的世界,感觉到是如此般的美妙!关于蓝桥杯大赛,很多技术大牛都看不上这个赛事,这很正常,要玩就玩程序设计大赛的奥林匹克ACM,但当你实力确实没有达到那程度又想去北京参加,蓝桥杯,PAT于我们而言也许是一次很好的锻炼机会。

1

蓝桥杯终于告一段落了,一共10道题,5个小题5个大题,小题应该对了2个,6/7/8这三个大题不知道,第10题大概能过40%的测试数据,至于能不能进入国赛,一切看缘分吧。今天愚人节是真的是给我开了一场玩笑,刚打开电脑,下载文件输入解压密码发现文件已损坏,当时考场所有人都在疯狂地敲代码,一个考场近200余人,当时我那着急的心,题目都看不到,后来考场的技术顾问来了,这问题才得以被解决。时间已经来到上午9点30左右了,我才开始做题了,旁边的键盘声已经是哗啦啦的一片响声。打开文件夹,看到的题是如下:

第1题 计算2000年的5月4日是那一年的第几天,通过excel,是第124天。但实际这是一道坑题,因为2000年是闰年,所以是31+28+31+30+4=124天。

2

第2题 是十进制转二进制输出点阵汉字,不难,思路很清晰,但不知道为啥输出的点阵我看不出这是什么汉字,结果是9的9次方=387420489,我算对了。这里需要注意到的是负数的二进制是补码不是原码!

第3题 计算乘积的末尾有多少个0,这个出题点以前做过不止一次,所以还是比较熟悉的,只需要计算所有因数的质因数中有多少个2和5,取2和5个数的和的较小值即可,答案有31个0。

​ 具体思路:有两种方法

①直接将所有数相乘,然后每乘一个数就把后面0全部去掉记一下,不过中间会爆long long,这个好办,每次乘完只保留后4位非0数字,例如216037就只保留6037

②另一理解方式就是,因为所有的0都一定是2*5产生的,所以将每个数拆成一堆2乘上一堆5再乘上一个数,之后统计下有多少个2和多少个5取少的那个就是答案

第4题 是摔手机,最多要摔多少次,首先想到的思路是二分查找的最坏情况,也就是log(2,1000),但又注意到题目说了有3部测试手机,这是算法竞赛入门经典P292例题9-20。

第5题 快速排序,没有仔细阅读代码思路,而是直接猜答案,猜到quick_select(*a,l,r,k)是可以的,但仔细一想,之所以这样填是可以的,纯粹是因为在多次递归的过程中rand()迟早会随机到 i-l+1==k,感觉不太靠谱,但能通过自己编的多组测试数据所以就还是这样填了。事后有人提醒说题目明确给定时间复杂度是O(n), emmmmm这个嘛,直接看代码。考场上做错了,哎,不应该了。

第6题递增三元组,纯暴力肯定过不了全部的测试数据,所以把三组数据都用STL中的sort排了序,然后遍历B[i]去A/C中找临界情况,并记录下来,这样到了下一个B[i]的时候可以直接从上次找到地方继续找,不必重新开始。不过这应该不是最优化的做法。

第7题 螺旋折线,只要找到规律就很好做。先设定图形中每个左上角的点为基准点,然后找规律,比如(0,0)到(-m,m)所经过的路程即为(1+2+…+2m-1)2,然后根据基准点再分别处理实际点到基准点的路程,该补路程就补上,过头了的就去掉。

第8题 日志统计,把所有的id放进STL中的set容器,遍历set中的id找出所有的ts,单独存数组然后sort排序,接着遍历这个数组,只要看索引跨度为k的ts值的大小是否比d大就行。

第9题 全球变暖,要计算有多少岛屿会被完全淹没,感觉像是需要DFS搜索,但做了的半小时后发现并不顺利,眼看时间只剩下半小时,于是乎转战最后1题。

第10题 乘积最大,像是由一道经典题“连续最大子序列”改编而来,但数据规模相当大。直接用long long处理了,能过样例和规模较小的测试数据,预计能拿到小部分的分数。

​ 仔细思考会发现其实最终答案为负数只有两种情况

​ ①k=n,这n个数都是负数并且n是奇数

​ ②k是奇数,并且这n个数都是负数

其它情况下答案一定为正,为什么呢?一个很简单的证明就是如果结果为负数,那么一定可以通过少乘一个负数多乘一个正数,或者少乘一个正数多乘一个负数把答案变成正的。然后正数的情况就好办了,一个很完美的方法就是所有负数取绝对值从大到小排序,所有正数从大到小排序然后暴力负数选多少个,中间取个最大的就行了。但是这样你肯定不能取模,因为取模就错了,然而直接乘会爆long long。

时间来到下午1点了,监考老师走到我身边说,已经为我延时了半个小时,说真不好意思,其实也不能怪组委会,我觉得这只是个意外而已。最后做完后总体还好,至于结果看运气,自我感觉还是很水,一个是考题,另一个考场纪律,有学生故意去厕所对答案,有学生考场讨论答案,确实有很大的不公平性,但教育考试制度就是这样,不能保证绝对的公平性,只有相对公平,当考完后,很多天其实很抱怨浪费三百大洋,但不觉得亏,至少你收获了考场经验!


文章作者: Hoganbin
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Hoganbin !
评论
评论
 上一篇
关于博主与博客 关于博主与博客
博主简介 八一:男,90后的奋青,没什么特殊爱好,无非就是数学、计算机、旅游与音乐,不逛街,更不会抽烟,但上知天文地理,下晓鸡毛蒜皮。喜欢数学,热爱编程,在自己所研究的领域愿意花更多的时间专研。 16年刚入大学,又是重新开启了新的一段奋历程
2018-04-18
下一篇 
基于hexo搭建博客的心得过程 基于hexo搭建博客的心得过程
在搭建博客过程中,确实让我学到了很多以前不知道的前端开发知识,虽然我有看到很多高中生都有了自己的博客,可能他们是全国高中生信息竞赛的学生,这我不觉得足以为奇,或许是因为他们的兴趣爱好。 目前搭建博客最受欢迎又是免费的还就是hexo与gith
2018-04-17
  目录