先挖坑…… 【last update 2.17】
这大概是我最后一次参加和OI有关的活动了，现在应该算是彻底退役了。 往年都是以选手身份，这次是以讲员身份去的，还验了一道试题并客串了监考。 大大小小比赛都参加过，当过选手、当过讲员还当过监考，OI生涯也算圆满了。
以下讲课内容都是回忆的，记不清的地方就自己脑补了，所以应该错误一大堆，欢迎指出……
day1
上午
按惯例王宏教授讲第一讲，今年没有讲CEOI试题，而是讲了近年来非传统题出现越来越多这个事情……
然后我上去讲了若干非传统题和IOI2013 day1的题解。因为讲的内容太傻叉，就不多说了……
下午
QMD大神讲了和DFA相关的一些东西。DFA定义就不说了…… NFA和DFA的区别在于NFA中每个结点可以出去很多很多条同字符的边，还可以出去空字符的边…… 然后只要存在一种方案走到终点就算可以识别……
可以发现DFA和NFA是等价的： 考虑某个串匹配到了前若干个字符，那么NFA和DFA区别在于，DFA的话肯定处于某个结点上，而NFA可能处于若干结点之一。 于是，设NFA有n个结点，考虑建立2^n个结点表示任意时刻NFA的可达结点集合，然后枚举下一个字符，对应连边。这样就从这个NFA转化得到了一个等价的DFA。
实际进行NFA识别时候直接按上述方法转DFA会跪，因为2^n规模实在太大。然后一个方法是维护当前可行结点集合，这样是\(O(\)串长\(*\)结点数\()\)的。还有一个更好的方法，因为真正有用的可达结点集合往往不多，它们之间的转移边也不多，因此用一个hash把之前已经处理出的转移边和结点集合进行记忆化，如果之前已经处理过了可以就直接用了。 这样就是\(O(\)串长\(+\)用到的不同转移边数目\(*\)结点数\()\)，虽然理论复杂度没有变，但实际速度更快（CTSC2004数字搜索）。
然后引入语言…… 语言是一个单词集合。定义某个DFA识别的单词集合为这个DFA的语言。一个语言是正则语言当且仅当它是某个DFA的语言。定义语言的运算：交、并、补集、连接、幂、闭包。可以发现正则语言是有封闭性的，证明只要对每个运算找个办法把两个自动机拼成一个自动机就行了，比较简单就不说了。
然后引入正则表达式，定义懒得写了。可以证明正则表达式和DFA也是等价的： 首先正则转DFA是很容易的，与正则语言封闭性证明相同：对每个运算找个办法把两个自动机拼成一个自动机就行了。 但DFA转正则就比较复杂了：我们要引入一个叫GNFA的玩意，它与NFA的区别是，它只有一个识别状态，且每条边上不是一个字符而是一个正则表达式…… 然后一个DFA显然可以直接视为一个GNFA（多个识别状态的话拉一条空字符边即可）。 然后我们每次删去GNFA的任意一个结点，并试图构造出一个与原GNFA等价的GNFA：考虑所有连向这个被删点的点和这个被删点连出的点。 可以发现，删掉这个结点后，可以找到一种方法在这两组点间两两连边（可以变成0正则表达式的交、并、闭包的形式），达到与原GNFA等价的效果。这样每次删一个结点，把中间结点都删光后，只剩下起点和终点，连接它们的那条边上的正则表达式就是与原DFA等价的正则表达式了。 这样DFA、NFA、GNFA、正则表达式就都是等价的了。
还可以发现DFA有一些东西识别不出来，比如所有0和1个数相等的串构成的语言。 证明可以用反证：如果一个n个结点的DFA识别了这个语言，考虑1个0、2个0 …… n+1个0 这些串在这个DFA的终止位置。 肯定有两个相同的，不妨设为x个0与y个0。 那么这个DFA要么同时识别x个0+x个1与y个0+x个1，要么同时不识别。 不管哪一种都无法满足要求。
有一个叫做泵引理的东西可以帮助判断一个语言是否是正则的： 一个正则语言一定能找到一个适当地正整数p，使得语言中任意长度>=p的串s均可以分成s=xyz使得y非空且|xy|<=p且对任意i>=0有xy^iz也在正则语言里。直观的看就是y这段不管重复多少次都不会影响这个串是否被识别。
证明的话，感性理解比较简单： 如果语言只有有限个串，只要取一个特别大的p就没事了。 否则既然它能识别无限个串，肯定要在DFA的某个环上绕啊绕，考虑识别过程肯定是前面走一段，然后在某个环上绕若干圈，然后出环再走一段走到目标状态。那么只要取一个足够大的p，然后取y=那个环绕一圈的序列，x=前面一段，z=后面一段就可以了。数学化的证明就看讲义吧。
怎么证明一个语言是不是正则的呢？ 大概是适当地和其他语言取交、连接、取闭包啥的，然后搞出一个新的正则表达式，然后证明这个正则表达式不满足泵引理（证明不满足泵引理的方法和证明DFA识别不出0和1个数相等的串的方法很类似，也是利用抽屉原理制造矛盾）…… 有没有更普适的方法不知道，这段课上好像只讲了几个例子。或者是我听漏了。
还有就是泵引理倒过来用是不对的：满足泵引理的语言不一定是正则语言（例如{a^i b^j c^k | i,j,k>=0且若i=1则j=k}）。
营员交流
【第一组】
ydl大神讲了偏离算法，是一个快速求图的两点间第k短可重最短路的算法（可以走重边，如果有多条等长的路径视为多条路径）。 感觉真心超级神啊，各种刷新三观…… 去年在80中集训时候听ayq讲过，但当时听得很迷糊，现在总算基本搞懂了。
算法思路大概是这样子的：考虑每个点到t点的最短路的第一条边，如果有多种选择随意选一条。 不妨称其为“偏离树”，其实就是图的反向图从t出发的最短路径树。 这时候我们发现，如果直接按树边走，那么肯定没事了，走的就是最短路。 但如果不按树边走的话，对于每个点i，如果我们选择下一个点是j，可以发现边(i,j)对答案的贡献是dist(j)+w(i,j)-dist(i)（如果从j出发后走的不是最短路的话，贡献就不是由(i,j)这条边产生的了，可以用同样的方法算；而从j出发走最短路到t的话额外代价就是dist(j)+w(i,j)-dist(i)）。
然后，我们用优先队列进行BFS。每次取出当前额外代价最小的点i，然后枚举偏离树上i到根（也就是到t）路径上的某个点k，表示i到k都走的是最短路，从k出发走了第一条非树边。 然后再枚举这条非树边，把额外代价算出来，丢进堆里。 到这一步，算法和暴力的A*还是一样的。
这时我们可以发现，对每个点i，其实丢进堆里东西是一样的。 不妨设当前i点的代价是original_cost，每个点i拉出一个二元组列表(j,cost)表示存在非树边(i,j)且走这条非树边的代价是cost，那么每次扩展i，实际丢进堆里的元素就是i到根所有结点的列表里的所有元素，当然cost都要加上original_cost。 我们用一个可持久化的数据结构来维护每个结点的列表。那么也能快速处理出i到根的所有结点的列表的并。 然后每次扩展i时候，就相当于把所有元素加一个值，然后并入优先队列。这个显然用可持久化的treap就可以完成了，结点上带一个区间加标记并维护一个最小值即可。这样复杂度就是\(O(n\log n+m+k\log m)\). （注：现场讲的好象是用可持久化的堆来做的，维护略麻烦，还要堆套堆啥的…… 我感觉用可持久化treap直接做不是方便很多吗…… 也可能是我YY错了，没实际写过）
后来我想了一下，感觉不用可持久化数据结构大概也能做？ 首先用倍增来支持路径最小值，这样一条链的最小值就可以找到了。 然后优先队列里的东西是若干链的最小值和若干结点的列表的k小值。 考虑优先队列里的最小值的情况： 如果它是某个结点的k小值，那很简单，只要把这个结点的k+1小值丢进优先队列即可； 如果它是条链，考虑pop出这条链的最小值后的情况，设最小值所处的结点为j，就把这条链从j处断开成两截，把两条链都丢进优先队列，然后j结点的次小值丢进去优先队列。 最后扩展这个最小值结点，相当于把这个点到根的链丢进优先队列。 这样单次pop出最小值并更新优先队列也是\(O(\log m)\)的，这样复杂度和之前做法相同. 当然这个做法也是我乱YY的，没实际写过，所以不保证正确性。
【第二组】
好像讲了某乱搞骗分算法与某个游戏的设计过程。 那个骗分算法感觉脑洞略大的样子……
那个RPG游戏果然好猎奇…… 飞过去然后被冰住了23333 被杀也可以升级23333 杀人后空血空蓝还没法回，被满血满蓝复活的对手直接反杀23333333
看完这个游戏后再看我们的AC大逃杀，其实做的也不是太糟糕的样子呢。→_→
【第三组】
wyt神犇三人组讲传说中的后缀仙人掌。 后缀仙人掌听名字能吓死人，但其实和仙人掌图一点关系没有。 就是一个由后缀数组构造后缀树的算法。 其实这算法大多数人都会吧，只是可能没几个人知道它有后缀仙人掌这奇葩名字而已……
还提到了一个叫后缀预言机的东西，是一个错误率和时间复杂度相关的字符串匹配算法…… 但我完全没理解意义何在…… 后缀树已经线性了好不好…… 也可能是我理解错了。
day2
上午
范爷科普黑科技。各种神思路，不能更加跪舔。听得各种云里雾里…… TAT 只写几个大概听懂的题吧……
Problem 1: 要求在O(log n)级别内存内，估测一个n个数的极大的集合中不同元素的大致个数。
好像可以证明在给定限制下，任意高概率得到精确解 或 保证得到任意接近真实答案的解 都是不可能的。（我没听懂证明……） 但有一个很神的算法可以做到以O(log n)的内存，做到以任意高的概率得出任意接近真实答案的解。
这个算法大致思路是这样的：考虑有m个盒子，如果我们每次等概率地选择一个盒子，往里面丢一个球，那么假设有k个盒子里有球了，我们期望已经丢了多少个球呢？ 显然答案是m/m+m/(m-1)+m/(m-2)+…+m/(m-k+1)。 但这个估算在盒子几乎满了或几乎空的时误差可能会比较大，不太靠谱。朴素的算法是这样的： 选择一个哈希函数，使得每个元素被等概率的映射到0~m-1的一个值上。 然后统计有多少个值有元素出现过了，据此推测不同元素个数。 但这样不太靠谱，因为元素一多，盒子肯定满了。
一个改进的算法大概是这样的： 我们找一个适当的i，让每个球只有1/2^i的概率被丢进盒子中，其余的概率被直接扔掉。选择适当地i值可以让有球的盒子个数不太多也不太少，这样估计就比较准了。 最后答案乘以2^i即可。也就是说，我们有很多很多层盒子，每个球能够进入第i层盒子的概率是1/2^i. 然后选择一个适当地i，以第i层的盒子的占用情况作为结果。 取层数=O(log n)就足够了，每一层盒子的个数可以视为O(1)，这样内存是O(log n)的。然后可以证明这个算法是可以满足我们“以任意高的概率得出任意接近真实答案的解”要求的。以及Hash函数好像不能随意选，必须满足pairwise-independent才行…… 不太明真相……
Problem 2: 多项式恒等判别
随机选若干个值，代入检验，比较在模质数意义下的结果即可。 为什么要模质数？ 因为这样才能保证根的数量只有O(n)个。 类似的，字符串hash也要模质数，原因相同。模2的幂次就要被卡了（POI卡人法）。
Problem 3: 给定集合S和它上面的二元运算符f，问是否满足结合律。要优于三方暴力的做法。
没听懂。 这题好像是lyp大神给THU集训出的测试题……？ 给跪穿地板了。
Problem 4: 有一个\(n*n\)的矩阵和一个R值，要求找到一个\(R*R\)的子矩阵，使得中位数最大。有一个期望\(O(n^2)\)的做法。（直接二分答案后判定是\(O(n^2\log n)\)的）
考虑随机地选k个子矩阵，求出它们的中位数。 然后把所有达不到这个中位数的子矩阵全部排除不再考虑。 因为是随机选k个，因此一次排除后期望只剩下n^2/k个候选子矩阵了。
我们考虑怎么足够快地求这k个子矩阵的最大中位数： 如果直接整体二分，复杂度是\(O(n^2\log n)\)的，不行。 但实际我们发现，只要求这k个子矩阵中最大的中位数就行了，不用求所有的。 因此我们整体二分后不用分治，只要递归处理其中一侧就可以了。 这样，如果预先离散化的话，复杂度就变成了\(O(n^2+k^2\log k)\)，这样的话，取\(k=\sqrt{n/log n}\)，就可以发现此时求出k个子矩阵的最大中位数是\(O(n^2)\)的。而此时\(\log_k n^2=O(1)\)，因此期望\(O(1)\)次排除就能得到最终答案。 这样复杂度就期望\(O(n^2)\)了。
我个人感觉这题思路的奇特之处在于，因为是随机选的k个矩阵，因此期望总是能把当前候选矩阵数目减小到原来的1/k.
Problem 5: 无向图的全局最小割。 存在一个\(O(n^2\log n)\)的蒙特卡罗算法（正常向的做法是用stoer-wagner）。
一个算法思路是这样的： 考虑对当前图，以每条边的边权为正比，随机选择一条边（也就是选择到一条边的概率与其边权值等比例），把这条边缩掉。 缩到只剩一条边为止，以这条边权值为答案。
但这个算法是不靠谱的…… 考虑有一条链，每条边权值都极接近但两两不同。 这样的话，割边是惟一的。 但因为边权极接近，可以认为缩边是等概率随机选一条边缩掉。 这样的话，就相当于从n条边中随机选择一条边作为割边，正确率只有1/n。
然后试图改进这个算法。 我们发现，这个算法一开始的缩边成功率是很大的，但越到后来，成功率越小。因此产生了一个很好玩的想法： 每次图变小一定程度后，就递归执行这个算法两次，取较优的一次。
这样的话，即使是像上述的缩边等于等概率随机选一条边缩掉的情况，正确率也有\(P(n)=\sqrt{2}*P(n/\sqrt{2})-P(n\sqrt{2})^2/2\), \(P(1)=1\). 这个函数收敛于\(2\sqrt{2}-2\)，大约0.83，是一个可以接受的正确率，多执行几次就行了。复杂度的话，是\(T(n)=2*T(n/\sqrt{2})+O(n^2)\)，解出是\(O(n^2\log n)\)…… 总感觉这算法很有推广潜力啊，不知道有没有什么其他问题能用类似的思路。
Problem 6: 随机化算法在线性时间内求最小生成树
没听懂。 好像是以p的概率采样原图中的边，得到若干连通块，在每个连通块上递归，然后blablabla一阵乱搞…… 完全没听懂……
还讲了一些梯度下降相关的东西，听得不明真相…… 就不写了。
下午
【待填坑】
营员交流
【待填坑】
day3
【待填坑】
day4
【待填坑】
day5
【待填坑】
day6
【待填坑】