《挑战程序设计竞赛——世界一流程序设计高手的经验总结》阅读笔记(第一章 蓄势待发——准备篇)
2021/8/2 1:05:45
本文主要是介绍《挑战程序设计竞赛——世界一流程序设计高手的经验总结》阅读笔记(第一章 蓄势待发——准备篇),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
第一章 蓄势待发——准备篇
竞赛相关的背景知识和本书使用方法
- 列举了一些知名OJ,如:POJ/AOJ(日本)/SPOJ/SGU/UVa(老牌OJ)/Codeforces(最受欢迎)
- 列举了一些知名比赛,ACM/ICPC(成年人没机会参加了QwQ)、TopCoder SRM(75分钟3道,总决赛85分钟3道,时间要求紧到有点变态)、GCJ(有幸参加过一次,通过了资格赛但是错过了预选赛,没印象有“大数据规模”这回事,之后需要关注一下)
- 本书的例题和练习题多来自于POJ(真是意外)和GCJ(作者强调过其中部分题目很难)
涉及的三道题目
- n个棒棒能构成的三角形中最大的周长是多少?
答:\(O(n^3)\)做法是暴力;\(O(nlogn)\)做法是排序后遍历,枚举当前边作为最长边的三角形中周长最大的多少,向左找相邻的2个次小边判断能否构成三角形即可 - 知名题目Ants
答:关键在于“蚂蚁相遇后转向”这个操作等价于“擦肩而过” - \(n\)个带点数的卡牌,是否存在一种策略可以从中找到4张卡牌点数和为\(m\),4张卡牌可以重复
答:\(O(n^4)\)做法是暴力;\(O(n^3logn)\)做法是3重for循环枚举,最后一个点数二分查找;\(O(n^2logn^2)\)(记得log中的指数常数可以直接提出来,等价于\(O(n^2logn)\))做法类似于“中途相遇法”,枚举2张卡牌点数和\(sum\)并排序,然后遍历这个结果并且二分查找剩下的\(m-sum\)是否存在
其中第三题可以扩展一下,如果4张卡中不能有重复的,如何求解?
二分查找“左闭右开”写法
卡牌那题突然开窍了二分查找的左闭右开写法,之前二分查找的时候我习惯于使用“左闭右闭\([l, r]\)”的写法:
int left = 0, right = n-1; while(left <= right) { int m = (left + right) >> 1; if(x < a[m]) { right = m - 1; } else if(x > a[m]) { left = m + 1; } else { break; } }
这么写貌似没什么不妥,而且也很直观容易理解,可能我短时间内做题还是会这么写;但是这次我仿佛领悟到了“左闭右开\([l, r)\)”的优雅之处:
bool binary_search(int x) { int l = 0, r = n; // 注意r这个下标实际上不属于区间内 while(r - l >= 1) { // 区间不为空 int i = (l + r) / 2; // 因为 (l + l) / 2 = l,(r + r) / 2 = r,又因为l < r,即((r-1) + r) / 2 = (r-1),所以(l + r) / 2 属于[l, r - 1],一定是一个有效的下标 if(k[i] == x) return true; else if(k[i] < x) l = i + 1; else r = i; // 再次强调r不属于区间内,因此当前这个i实际上是被排除在外的 } return false }
关于复杂度
关于复杂度,书中同样避开了太过数学的解释(是的,我刚从《具体数学》的阴影中走出来),简单来讲,复杂度是:
用来描述算法的运行时间的,与数据规模有关的的数学表达式
将数据规模代入复杂度表达式,可以计算出来一个操作次数,在1s时间限制下,操作次数:
- 1000000,绰绰有余
- 10000000,勉勉强强
- 100000000,悬
跟以往认知是类似的,不过以前直接用\(1e8\)去计算了,看来这个上界还是不安全的
如果给的时间>1s,可以乘上相应的系数
由于第一章没有习题,所以内容就这么多,后续再继续更新
为啥不支持彩色字体啊?。。。
这篇关于《挑战程序设计竞赛——世界一流程序设计高手的经验总结》阅读笔记(第一章 蓄势待发——准备篇)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)