假期时光飞逝，转眼，第二波集训已悄然降临。回望刚刚经历的两天，我认为有必要进行一次总结。 
这两天，主要由陈楷予学长带领我们进行动态规划的深入学习。 
动态规划，关键在于把握题目中的信息。由于题目本身的性质导致动态规划题难以使用暴力方法解决，就算暴力也通常只有很少的分数。找出转移方程是关键，正确选取最优子结构也是关键，并且要适当结合数据结构和搜索的知识。只有这样才可以灵活地运用动态规划，使不同的方程或是算法发生关系（产生联系）。 
第一天，先简要复习了一下动态规划的已学过的知识点。以前的动态规划主要是针对一串数的选择与不选择问题，包括各种背包与各种朴素算法，但是随着数据范围的扩张，很可能造成超时或者爆空间的情况。然后进行了LCS的学习（最长公共子序列）以及LIS的学习（最长不下降子序列），但时间复杂度由n^2下降至nlogn。主要的方法有：二分+单调栈和树状数组。接下来是树形DP，包括求树上最长连、最多任意不相连的点和树上背包。主要方法是用DFS加上一个转移方程来取代普通的循环操作，这样就可以确定树上节点的选取或者不选取，自然确定状态。然后是图上DP，包括求有向无环图最长路径、FLOYD以及次短路径的求取。 
第二天，首先补充了树形DP，此时要进行题目的抽象与剥离，使其变成“通俗易懂”的题目，再来动态规划。数据结构优化DP，将动态规划与数据结构结合。状态压缩DP，将原先的flag数组打标记的工作，用一个数的二进制数的1或0状态来代替，加上位运算，大大缩减了时间空间复杂度，并且可以方便地查询并且更改某一个特定位置上的状态并且保证之前没有而不用for一遍。只是位运算的原理要搞懂。数位DP嘛。。。。 
现在的动态规划已经不是单纯的针对数的探究与选取，更多的是与栈、队列、树等数据结构的结合，把曾经单一的数字转变成节点、子树、甚至森林里的一棵树。总而言之，动态规划算法属于递推算法，并且这个算法适用的问题必须具有最优子结构，利用局部最优解来推导全局最优解。 
（啊，我的动态规划怕是废了。）

字符串的学习紧接着动态规划，老实说，这部分确实挺难得，同时也具有难度，确实需要聆听与思考。 
字符串，关键在于将字符串与各种数据结构结合。一个字符串的性质，当然要考虑到自身的规律，也要考虑到数据结构的运用。你说，这一个字符串，怎么就这么神奇呢？后来陈凯予学长就给我说啊，说NOIP已经确定啦，字符串一定会考！所以说，这一部分很重要。 
首先学习的是Hash函数、Hash散列性质以及Hash的储存。运用这个方法可以快速判断多个字符串是否相同。接着学习了字典树，也就是Tire树。这个算法可以解决“给出一个字符串t，求以此串为前缀的单词有多少个”、“判断单词中是否存在某个串为另一个串的前缀子串”等问题。Tire时间复杂度是o（len），但是空间复杂度是o（n*len），消耗较大。然后学习的是KMP算法，可以用来解决“求t在s中的匹配次数”、“最多能在s中提取出多少个t”、“求s的最小覆盖子串”、“求出现次数”等问题。KMP是针对两个字符串，查看一个有没有另一个子串的算法。下面是AC自动机，在Tire树上加上fail指针，也可以说是Tire树和KMP。

马上就要结束竞赛的寒假训练了。 
在这几天里，信息竞赛变成了数学竞赛，丁尧尧学长为我们讲解了信息学需要的数论知识，也就是数学。当然，由于这部分理论偏多，并且与信息学的关联不算大，所以理解起来有一定的难度。我很庆幸，自己撑过了这关。 
首先我们学习了组合数与排列数。从n个对象中选m 个排成一列的方案数称作排列数，记作P(n，m)。如果n=m，则称为全排列，记作P(n)。从n 个对象中选择m 个的方案数称作组合数，记作C(n，m)。这里还涉及到了可重排列与循环排列、夹棍法以及卡特兰数列。接下来是容斥原理，这个类似于抽屉原理。然后是快速幂（快速乘），如果我们要计算a的n次方，那么我们可以将n写成二进制形式，然后将a的n次方拆成一些a的2i此方的乘积，而后者可以递推来算。然后是lcm、gcd以及exgcd。两个整数公共的约数称为公约数，如果这两个数不同时为0, 那么他们中就存在最大的一个公约数，称为最大公约数，记作gcd(a，b)。两个不为0 的整数公共的倍数称为公倍数，其中最小的正公倍数记为最小公倍数，记作lcm(a，b)。 
扩展欧几里得算法。这个可以证明辗转相除法与唯一分解定理。gcd（a，b）=ax+by。二元不定方程的解法十分灵活。接下来是同余，同余是指两个数除以某个数有相同的余数这一个重要的关系。尽管还学习了欧拉函数、求逆元以及中国剩余定理，但是由于我本身对这些知识的掌握就不算很好，加之知识点庞杂繁琐，在这里就不过多介绍。（可以参考讲义上的知识） 
数论是一大难点，难懂，并且对思维的速度与准度有极高的要求。就我个人的情况而言，想要在短短的几天之内搞懂这些知识是不可能的。所以我会在日后多加理解复习，虽然难，但毕竟这些知识是基础。

 ——关于应试技巧及方法

回望这个寒假，我一共经历了八次考试。这八次考试，我经历不同难度，不同出题风格，不同时间安排以及不同的考试氛围。这给了我非常多的经验，让我之前对考试的畏惧心理极大的消散。记得刚刚考试我经常爆零，拿到了题目不知所措，打好了所知道的程序，就不知道干嘛了。我的成绩由较差到较好，最终稳定在班级十名左右，我认为有以下几个原因。 
首先，平时与同学的交流。某种意义上来说，与同学进行交流比与老师交流更加重要。同学的问题也许自己也有，解决他的问题的同时，也就逼迫自己去解决自己身上存在的问题。并且同学之间可以没有顾虑的表达自己的疑惑以及知识漏洞，可以平等的分享经验方法。这给了我非常多的知识，不仅是理论知识，更重要的是人生的经验。 
其次，该暴力就暴力。记得有次考试，我做不出最后一题，无奈之下选择暴力方法。也不知道是误打误撞还是灵感一现，我想出的暴力方法就是正解的“退化版”和“通俗版”，于是那道题我用非常朴素的方法暴力对了60分。这对于一道信息竞赛的考试题，还是最后一题是相当不错的分数了！庆幸之余，我也因为尝到了暴力的甜头而走上“不归路”（尽管很管用）。暴力的好处就是不会爆零，并且说不定你辛辛苦苦打了两个小时的“正解”，结果还是拿了零分，还不如提早决定，果断放弃，开始暴力，并且想尽一切方法对代码进行各种各样的优化，包括空间、时间。你可以选择分段处理，利用给出的数据范围强势骗分；也可以用超时代码打表，最原始的“时间换时间”方法，回归本真；你甚至可以全部输出“No”，或者全部输出“1”，甚至利用数据的边界和特殊数据（0，1,100000等），强力脑算！不管什么方法，拿到分了就行。所以我就想到了中国的一位伟大的改革开放总设计师所说的话“不管白猫黑猫，只要能抓到老鼠的，就是好猫！” 
然后，拿到试题通读试卷，大概想出所需的算法，不会的果断放弃。不要拿着就开跑，正所谓“工欲善其事，必先利其器”、“欲速则不达，见小利则大事不成也”。 
最后，学会善于自主的、静态地、查错。尽管我会用调试器，但是我很少在实战中使用它。一个是因为它比较麻烦，并且变量一多，容易搞不清楚过程。二一个，是因为我调试器用的还不是很熟练，花费的时间巨大，还不如自己静态查错来得快。事实证明，静态查错在某些方面确实有优势，但如果代码太长，静态查错无法快速进行时，就需要适当利用调试器了。 
总体来讲，考试和学习是一个相反而又相同的过程。先学好，才可以考好。考试是不全面的，考题指示方向，最重要的是整理笔记，记清楚算法模板，而不是单纯的做题。仅仅做题，有人做一次，以后都会了；有人做十次，还是不能对。只有分清自己是“考生”还是“学生”，确定自己的地位与目标，才可以在学习与考试中都做到较为成功。

 ——首次正大光明的讨论

今天是2017年2月12日，我参加了人生首次ACM比赛。 
队友：朱闻笛、李家童。战队名称：theljt。 
私下里，我们三个是非常要好的朋友，自然在比赛过程中有着精妙的默契。我们分工合作，一人两题，高效又准确。巅峰时期达到了第二名，尽管最后只得了第五，不过相对于我们的实力，这个成绩还算正常。这种比赛，不仅刺激（excited！），而且有效地学习了知识。 
希望还有这种比赛，希望还可以战斗下去。

信息学带给我的，不只是知识层面的东西，更是精神层面的宝藏。很感激自己，能够坚持下来。 
作为一名学生，一名七中学子，一名竞赛生,一定要学会思考。思考是无可替代的，再忙也要思考，不能被别人带着走，要形成自己的节奏与习惯。忙，但是不能假忙。时间花在正确的事情上，不要让不该做的事占据了大部分空间与时间。 
在之前的总结中，我并没有在之前的总结中大量的总结知识层面的东西，而是在没有大量的总结知识层面的东西时更注重一些经验性以及概念性的东西。我没有附上一条代码，因为个人觉得没必要，而且会让总结变丑（真的，我强迫症晚期，估计是没救了）。这篇总结是以故事的文本格式写的，段落不多，文字较为密集，很少明确区分1234的顺序。更偏重自我的看法。知识总结多了，就应该叫做“百度”，叫做“知识荟萃”，叫做“算法集锦”，而不是“自己的总结”。由于这篇总结是与其它文献资料配合使用的，所以在日后的复习中，可以直接参考其他文件上的知识（各位学长的讲义及代码模板，考试的代码，甚至网络上的博客以及评测网站的交流平台）。 
我还有大量的知识没有学，还有很长的路要走。希望自己可以坚持下去，和我亲爱的同学和敬爱的老师一起，越走越远！