Java教程

《挑战程序设计竞赛——世界一流程序设计高手的经验总结》阅读笔记(第一章 蓄势待发——准备篇)

本文主要是介绍《挑战程序设计竞赛——世界一流程序设计高手的经验总结》阅读笔记(第一章 蓄势待发——准备篇),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

第一章 蓄势待发——准备篇

竞赛相关的背景知识和本书使用方法

  1. 列举了一些知名OJ,如:POJ/AOJ(日本)/SPOJ/SGU/UVa(老牌OJ)/Codeforces(最受欢迎)
  2. 列举了一些知名比赛,ACM/ICPC(成年人没机会参加了QwQ)、TopCoder SRM(75分钟3道,总决赛85分钟3道,时间要求紧到有点变态)、GCJ(有幸参加过一次,通过了资格赛但是错过了预选赛,没印象有“大数据规模”这回事,之后需要关注一下)
  3. 本书的例题和练习题多来自于POJ(真是意外)和GCJ(作者强调过其中部分题目很难)

涉及的三道题目

  1. n个棒棒能构成的三角形中最大的周长是多少?
    答:\(O(n^3)\)做法是暴力;\(O(nlogn)\)做法是排序后遍历,枚举当前边作为最长边的三角形中周长最大的多少,向左找相邻的2个次小边判断能否构成三角形即可
  2. 知名题目Ants
    答:关键在于“蚂蚁相遇后转向”这个操作等价于“擦肩而过”
  3. \(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时间限制下,操作次数:

  1. 1000000,绰绰有余
  2. 10000000,勉勉强强
  3. 100000000,悬

跟以往认知是类似的,不过以前直接用\(1e8\)去计算了,看来这个上界还是不安全的
如果给的时间>1s,可以乘上相应的系数

由于第一章没有习题,所以内容就这么多,后续再继续更新
为啥不支持彩色字体啊?。。。

这篇关于《挑战程序设计竞赛——世界一流程序设计高手的经验总结》阅读笔记(第一章 蓄势待发——准备篇)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!