鉴于BZOJ要关了。。。。我把我所有的AC Code发了出来。。。
大家趁还没关赶紧凑合着D一D吧。。。。
见我的SkyDrive网盘。。。空间一打开右上角就有地址

不知道为啥最近CF做起来顺的跟做梦一样。。。
成为了

International Grandmaster
就发个贴庆祝一下吧～～

0 在常州混了这么多天，还是挺开心的，很可惜的是没有把到一个妹纸（喝多了无视）。。

1 游乐园玩的真心开心，嗓子都叫哑了。。。

2 讲课中我各种刷存在感，感觉教练印象分提高了很多？

3 我看了一下，我THUSC第四，NOI第四，THU集训第四，作业分第四，WC之前第四，WC分数没有第四（如果这个第四我就做不到总分第四了，所以第四数量是理论最值？），WC之后第四。。。。。

4 不得不说这WC太囧了。。我整个人都考场梦游了。。。。前两题各骗了50分之后。。本来想看看是写第二题的100分呢。。还是做第三题呢。。想先做做第三题搞点分再搞第二题。。。结果写搜索各种跑不出来最后就被坑进去了。。。。。尼玛现在OI是不是就是比谁挂的少啊！！！大家都各种SB错误挂。。。某人文件名打错都不知道怎么吐槽了。。。。。

5 貌似noi前4除了我都跪了？当然fhq不算。。这OI尼玛太凶残了。。。

6 各种搅基啊。。。。欢乐死了。。。。

7 最后上去唱周杰伦的菊花～～台了～～。。虽然我自我感觉良好。。不过貌似声音都被炫教盖没了T_T。。。。

8 尼玛这1.5道提交答案题创纪录了吧！！！！！

9 雅礼神校啊。。。屠场屠的太狠了。。。。。。

10 wc rank1的某人。。。考完还发完挂状态。。。。。。。。。。

11 zrp和某人各种那啥。。大家都懂。。。

WC作业居然得了9.9分。。难道是因为我教练印象分很高么。。。

作业见我的网盘的OI目录

那啥由于我讲的这玩意Suffix Automaton的定义和证明之类的东西太多了。。。。。。
不得以就讲的跟堆定义一样。。。。。

时间也非常紧。。。感觉40分钟读一遍定义都差不多了。。讲的太快也请大家见谅T_T。。。

其实ppt做到还是很详细的。。。如果讲的时候没有跟上可以慢慢看ppt。。。。

资料在我的skydrive网盘的OI文件夹的all.rar里

另外我现在对于我的选材感到非常的后悔。。本来我的题目应该是

“根号算法与分块思想”。。。。。。。

马上就要WC了，我的OI生涯估计也要结束了(今年要被刷了，明年不想搞了)。。。。
比赛什么的，能觉得尽力了就好了吧。。。

另外我WC的时候会讲点傻逼的东西，大家轻点喷。。。

那啥最近闲的蛋疼。。把SGU的Volume 5 A光了。。（为啥A这个？因为Volume5题目最少。。。。。）

就简单的吐槽一下吧：

500：恶心的计算几何题。。算法很好想就是很恶心。。。由于我写的太烂还被卡常数。。T了无数次。。。

501：很久以前做的了。。这个一看就知道是要用dp做的。。。。慢慢写吧。。。

509：赖神貌似有题解。。不过也不是很难的题目。。自己想也行

516：毫无难度的傻逼模拟题。。。居然只有个位数AC。。。

522：简单的调整就可以构造出答案

526：我感觉我傻逼爆了。。。只会n^2的做法。。大体就是只有O(n)个有用的时间位置组合，然后搞搞求出路径就行了。。。。。

528：比较麻烦的模拟题，理清楚就行了

529：HNOI原题
530：分析一下可以发现有很简单的结论

535：这题其实是傻逼题。。别想复杂了。。。

541：比较麻烦的代码实现题。。。。

 另外我WC打算讲某个神奇数据结构。。。。大家可以做好准备到时候喷我。。

这两天闲的慌把POI18水完了。。。决定发一篇题解以除草。。。。。

Stage I和II似乎发过了。。就发下Stage III的吧。。
Party：每次找到两个不是朋友的人，把他们都删掉，就可以得出结果，为什么很容易证明。
Sticks：我觉得这题有点傻逼。。将所有排序之后，扫描一遍，维护最大且颜色不同的三个即可。

Periodicity：这个题目还是很有意思的，首先这货其实是要求一些长度的前缀和后缀相等，比如1,2,4,10。。那么我们依次构造，比如1,2,4的结果是A,那么可以知道1,2,4,10的结果是A**A。中间当然是能全添0最好，如果不能全添0，把最后一个改成1就行了。如果是1,2,4,7这样的话。直接在A的前面补上一个长度正好的前缀就行了。

Meteors：我们进行分治处理，比如处理到[l,r)这个操作区间，答案在这个区间的国家集合是S，那么我们添加[l,m=(l+r)/2)这些操作，如果一些国家已经够了，那么它的答案就在[l,m)否则就在[m,r)，递归处理即可，复杂度是nlogn。

Inspection：这题貌似没有什么难度。。树形dp出每个子树的大小和结果然后判断一下计算结果就行了。

Dynamite：首先二分答案，然后不难发现一个lighted fuel越靠近根越好，那么我们可以从底向上处理，必须放的时候才放。另外这个idea已经年娇处了吧>_<。。。。

Programming Contest:不难建出费用流模型，但是注意到有些边的代价是二次函数，不过这不影响费用流算法>_<，直接做就行了。同时由于此题的特殊性，可以实现的很简单，比如BZOJ上我就写了800B。

由于基本上前人都有题解。。。。。。所以发这篇的单纯是除草。。。。。

由于做的比较多。。就只说说AC数<20的好了。。。

sgu 331：crazyb0y有题解。。没啥好说的。。。

sgu 387：挺傻逼的一题。。令人吐槽不能的是大小可以为0。。。

sgu 450：挺傻逼的模拟题。。

sgu 470：就几行的傻逼构造题。。。

sgu 472：分治一下算出每个点周围的最短路然后dijstra就行了。。。

sgu 474：挺裸的题目。。。。没啥好说的。。。

sgu 498：意外的居然是傻逼题。。。随便算算就能算出来了。。。

个人感觉难的题目的话。。ural总体质量比sgu好？当然这跟ural题目比较多也有关系。。不过sgu上好题也是有些的。。。

250：

做法很多，我用的是最暴力的一种，考虑一个数x，它如果是完全平方数，那么它下一轮就跪了，否则它下一轮的位置是

x-sqrt(x)，sqrt(x)取下整。

由于没删掉的数之间的顺序不会变。

我们显然是要找到一个最大的数，它在变成1之前没有跪，那么我们从n到1暴力判断。。。。

这个速度很慢。。Java会T。。改成C++就能卡过。。。

500：

注意到期望的平方不具有可加性，咋办呢。。

注意到Sum(a1+..an) ^2 = Sum(ai*aj){i in [1,n],j in[1,n]}

那么一个点上的和平方的期望，就等于每对个range在这个点上相遇的期望次数的和

后者是可以通过简单的数学计算得出的。

1000：

确保你会做http://community.topcoder.com/stat?c=problem_statement&pm=8587这题

SRM396 1000pt

我们要找出一个最大的，独立的子空间，使得Sum(Red)*Sum(Blue)最小

我们考虑所有这些子空间，它们的（sumRed，sumBlue）组成的点集合。

那么我们可以注意到，答案只可能在这个点集合的凸包上！

那么我们来办法搞出凸包上的所有点就行了。。

打个比方说，我们给一个斜率k，然后把所有信封按red*k+blue排序，然后用SRM396 1000pt的做法

我们就能得到一个最大独立子空间，它的k*sumRed+sumBlue最小

这意味这，它就是斜率k的直线，一直往下压所碰到的凸包上的一个点！！！

根据标程我们只要搞出所有有可能成为答案的斜率，计算即可。。

不过我随机了很多斜率。。也过了。。