华师一附中OI组

标题: 2016年国庆清北学堂学习后邓迅同学的总结 [打印本页]

作者: admin 时间: 2018-5-12 22:56
标题: 2016年国庆清北学堂学习后邓迅同学的总结
清北学堂十一学习报告

前札

想起写这篇报告的时候，已经是10月6号晚上了。现在在回程的火车上，于是就只能随手写一点想法，请读者见谅。

这是我第一次参加外地的信息学竞赛培训，也是第一次真正意义上的竞赛培训，甚至是是我人生中第一次为了学习出这么远的门，在出发的时候就充满了期待。一个星期以来，友善幽默的同学们，可爱的学霸属性开满的学长老师们都给我留下了良好的印象，还有特别感谢杨易龙的妈妈和其他几位家长，虽然也没说上几句话，但是有他们做我们的后盾就特别的放心。

这次是在华北电力大学的地下机房进行的培训，跟刷题班的大神和普及组的学弟都隔得比较远，再加之地下室没有手机信号，可谓是闭门读圣贤书的感觉。不过我必须要吐槽的是机房里有大量整天玩游戏看视频聊天的闲杂人等，还有一个自以为厉害的”83号”,除此就没有什么煞风景的事啦。

下文中提到的题目和部分代码及代码模板都随此文打包，大部分是PPT和代码文件，可以自己查看，在此就不用代码说话了。

第一天清华大学何家傲

第一天的早上，要对孙老师说抱歉。因为头天说早上7点集合，我也是早上7点就已经整装待发了，但是并不知道是直接出去在门口吃饭的地方集合，所以就呆在房里等有人喊，但是一直都没有人喊，所以就晚了一些。

第一天跟我们上课的是来自清华的何家傲学长，刚开始的时候就十分友善的跟我们讲笑话，然后就开始讲考试的技巧(就是些被称为骗分导论的东西，貌似还有专门的文章讲这些东西，听说有必要在考试之前研读)。接着就讲的是STL(standard template libraries)，基本上都是自己零星学过的内容，他对STL系统的介绍让我从另一个方面了解到了这些，加深了认识，而且可喜的是竟然在后来的模拟考试中骗到了不错的分数。

然后下午就是讲一些基本的算法:分治法，贪心方法，简单的搜索和时间复杂度的分析方法，被何家傲大神称之为”杂七杂八的东西”。

分治法主要讲快速幂模板和归并排序。其中值得研究的就是他讲的逆分治的二进制快速幂，此前没有听过逆分治，所以也打开了一部分思路：这种看起来递归的方法(二分)有时候可以通过特殊的方式来完成非递归；也从另一个方面说明了二进制在算法竞赛中独特而重要的意义。

贪心方法一直都是一种神奇的玄学方法，没有用它的时候永远都没有办法了解到出题人或者std是怎么想出来推理贪心方法，知道这题要用贪心的时候反而不知道要怎样才正确而高效，总之就是除了做过的贪心，其他的就不知道怎么下手……记忆深刻的就是他讲的钩码称重问题，这道题郑义君和王司恺都和我讨论过怎么证明，我大概只能领会他前三步的意思，而之后的就也解释不清楚了。直到今天，虽然可以说出来这题是按称重减去重量排序解决，但是在证明上还存在漏洞，回武汉之后需要找刷题班的大神来解决这个问题。

然后就是简单的搜索模型，即深度优先搜索，宽度优先搜索，包括双向BFS等。两种都是平时训练很多的题目，所以听讲和做题难度也都不大，在此就不赘述了。而真正有难度的是搜索剪枝，不过这种东西对于我这种NOIP水平的选手只能按题分析，没有办法掌握一整套理论及其应用，只是大概听一听，没有期望听明白。

最后提到了时间复杂度的分析，这是对每一位算法竞赛的选手都是必须熟练掌握的东西。对于基本的循环和有些算法的时间复杂度的分析诸位也略知一二，于是就不献丑了，只是需要记住如果数据范围大的话一定不能大于O(N2)。

晚上在openjudge上有相关习题的练习(比如HJA的妹子有n个什么的)，但是基本上都没有做的很好的题，没有AC的，三题WA，不过大家都是这个水平也就还好了。

第一天总结:STL，分治，贪心，搜索，时间复杂度计算，openjudge0AC(平均拿分的题有60左右)，洛谷12AC

第二天北京大学黎才华

第二天基本上是复制第一天的过程，不过黎才华学长讲课比较迷，不是那么清楚，然而一整天都是极其重要的动规，所以感觉有一点可惜。

上午的时候从记忆化搜索讲起，然后就是DP的基本概念。个人感觉重要的就是他讲的动规的特性，要素和优化的基本思路——动规的基本特性是最优解有用最优子结构和无后效性，三个要素是状态，边界，状态转移方程，而动规的优化在于节省状态和优化状态转移方程。平时做了不少的动规题，但是都没有这样总结过，所以这对我很有用。其次就是完全背包和部分背包问题中的二进制背包转换(表示二进制又派上用场了，真是神奇的东西)，于是就把这一步中的O(N)变为O(log2N)。下午就是深入的介绍区间动规(虽然是讲了，但是还是回来要好好理解)，树形动规，以及一点点斜率优化的内容。大致上就是一些简单的习题的思路以及代码的讲解，没有什么有启发的地方，不过也是对既有知识的加深理解倒是了。(自动忽略斜率优化，因为求凸包可以说基本不会……)

因为他讲课比较迷，所以就算是一直在讲，最后发现那些动规的题还是只能在理论上解决，要是靠他讲的基本上是没有办法应用在考试题目上的，事实上之后考试的动规就没提升啊。

晚上在做poj练习题的时候杨乐过来坐到了我后面的地方，表示大家的欢迎很热烈，他只是安静的在看书。

第二天总结:各种动规，poj4AC，洛谷10AC

第三天清华大学杨乐

第三天讲的是数据结构，就是昨天晚上来的那个学长。不过他开场讲的东西让我认识了什么是真正的学霸(像我这种伪学霸就不说什么了，只能安静的膜拜)。他提到他的学习经验，主要有几点:多打草稿，多做尝试(前提是手速够快)，然后就是一定要经常整理，复习代码！

上午讲的是线性数据结构和树形数据结构中的堆，顺带一提并查集。线性数据结构就是可以通过一个点，并且访问其相邻的位置(单向或双向都可以)。其中重要的就是链表，这里大概只讲了单向链表，就是存储一系列指针，可以从队首单向访问；其实还是有双向链表的，不过要写两个及以上辅助指针数组和几个函数，还需要时间消化。关于树形数据结构，主要在于掌握键值与值的区别，二叉树的线性储存方法(表示还是二进制和位运算，神奇)。

下午就很难了，也十分重要，一旦想NOIP突破400的话就是必备技能(然而我的目标只是300+)，即是ST表，线段树(包括建立，区间查询，区间修改，特别是懒标记！！！这里用三个感叹号就是说就算听过还是不会，越不会就越想会的东西)，树状数组(即二叉索引树，又跟二进制有密不可分的关系，简直是无所不能的二进制)。这里没有办法很完整的总结到底听懂了什么，所以就只是推荐诸位膜拜大神的标程代码，然后努力继续学习了。

晚上就是codevs上有几道题联系，和他亲自写的银河英雄传说代码，还有一个给力的资源文档。同昨天，次日的老师，可爱的黄天老师也来了。

第三天总结:栈，队列，优先队列，链表，并查集，堆，ST表，线段树，树状数组，codevs5AC，poj5AC，洛谷19AC(多到难以置信)

第四天清华大学黄天

今天是唯一的女老师，所以大家的热情也很高，不过可能是因为大家过于热情，她有点紧张，有些地方会有一些小错误，不过她自己也都可以发现，倒也无所谓了。一整天的图论，和昨天一样充实，有点难。

引入是基本的图论，就是七桥问题什么的。然后就是链表储存图，这里她讲了很长时间，而且也没有讲的很清楚，不过从代码风格看得出她是水平很高但是没有办法描述出来罢了，也可见这简单的链表也不是那么容易。接着就是拓扑排序，最短路，最小生成树算法。具体而言就是有SPFA,Dijkstra,Floyd,Prim,Kruskal算法，其中比较不同的是她讲的SPFA的优化:新松弛的距离如果比队首还要小的话就先更新(具体是用deque维护)，然后队首取出的元素大于队列中距离平均值的话就去队尾等待，这两点都是基于启发式搜索和宽度优先搜索的基本原理确定的——先拓展较优的。

到了下午就是先介绍无向图有向图的概念，然后就是Tarjan算法，求桥，割点，强连通分量什么的；不过还是代码比人讲的清楚，只能回武汉再深入研究了。讲完之后就来到了听不懂时间，如果不是带了刘汝佳的书，估计都不敢写接下来讲了些什么东西。

其实也没什么很高深莫测的东西，就是倍增算法求最近公共祖先！！！不过以前没有接触过这一类问题，连模板是什么都不清楚，再加之那是用ST树维护，这段代码前一天才接触，只是大概明白是干什么的，但是离自己实现还有差距吧。

晚上就是习题加vj上的考试，大概到最后是第三名(具体是因为最开始的时候交错了考试，于是比第二名多了几百分钟，但是其他的都一样，不服，明明用时比较短才对)。不过晚上好冷，感觉有点感冒，效率比较低，vj考试完之后就没怎么自己做习题了。

第四天总结:拓扑排序，最短路，最小生成树，Tarjan，最近公共祖先，vj8AC，poj8AC，洛谷20AC(为什么感冒了比昨天还多题啊……)

第五&六&七天清华大学钟皓曦

这个老师可以给我们带三天的课，足以说明他是这几个里面最有经验，效率最高和综合能力最强的老师了。表示这个老师的题目名字都是日文罗马音，简直了，每次只能把题目名字复制粘贴，怕写错。

第五天上午是考试。由于他没有意识到我们是有多水，出了两道中等难度的题和一道代码超长的模拟题。第一题是把字符串翻来翻去匹配的问题，因为没有领会到”无限次翻转”的意义所在，只能暴力用递归生成所有可能去做，自然TLE无疑了。第二题是不知道怎么解决的贪心问题，但是在题目讲解的时候，我被折服了:首先动规都是最少O(N2)的，这么大规模只能贪心做；c++里面的比较符号就那几种，一个一个的尝试，然后取最优解就可以了——这种思路从来没听过，只有这种真正的大神才会有如此精辟的总结。第三题是我最满意的，毕竟是AC了，而且比另外一个满分的用时少十倍，比标程代码少了70行！然后结果就是第二名(才115分)，比第一低20分，比第三名快那么几毫秒吧，于是就有了第一个键盘。

第六天上午是第二场考试。自以为是做的很差了，不过竟分数比昨天高，而且还提升一名，所以机械键盘用的好舒服的说。具体原因是因为该水的分水到了(前几名就是该水的就水了的，所以二三四名分数一样)，然后多骗到了10分，不过时间也到了快TLE的极限了。第一题很可惜，知道是用莫比乌斯函数，但是就像数学知道要求导一样，求完之后就发现求了也没什么用，所以就没有办法，转而写暴力去了；第二题完全没有思路，于是就做了50分的送分部分，也没有办法了，而题解是用二分(了解到二分的条件是单调性，三分的条件是凸性)；第三题，我可是很用心的写了一个多小时的二维背包+记忆化，但是自己做的数据就TLE了，没办法，只能和写一维背包的人一样的分了，而且还稍稍慢一点吧。不过开心的是拿了第一吧。此处还要特别点名王司恺同学，他无意中发现老版本g++编译器的一个CE之处:如果对(unsigned) long long在构造的时候赋初值一定要带上ull后缀，否则就会报CE；顺带说一句，要是没有CE的话，我的键盘就是他的啦……(其实王司恺才是这里真正的大神啊)

然后第五天和第六天的下午和晚上就是讲题和新课。新课就是数论和字符串，数论上增加了(相对我已掌握的而言)莫比乌斯函数，Miller Rabin素数测试，矩阵的基本概念；字符串就基本上只讲了Hash，特别是双模Hash值得研究！！！然后简单提了一下BM和KMP算法，不过在我们的钟大神看来，Hash可以直接水过这种题，就无所谓用不用KMP什么的了。

然后就是用他讲题解和中间休息的时间自己重新写了AK程序，重新去评测，效果甚至不亚于std程序(这里就当我在YY吧)，不过AK程序可以自己查看，没有注解的话可能会比较吃力吧。

第五&六&七天总结:坑爹的数论，字符串，两场模拟考(键盘*2)，pojAC，洛谷20AC(表示是三天的总和……)

后记

因为时间仓促，写到后记的时候已经到孝感了，所以就在此处住笔吧。表示回看前文发现自己作文水平退步了，不仅没有典雅的书面语，还看起来就像是流水账，简直不能看，不过都写这么多了，就还是发给大家吧。总的来说，这个国庆长假时十分充实，完成了我几个月难以完成的工作量，比如在6.5天AC洛谷81题；还有再次感谢友善的各位，谢谢大家的关心和照顾，此次收获颇丰！作此为念。

10072016 晚于高铁邓迅 Dorence

作者: admin 时间: 2018-5-13 22:42
配个图，就是这个同学

欢迎光临华师一附中OI组 (http://hsyit.cn/)