…我的英语真是烂透了>_<
http://www.spoj.pl/problems/JZPGYZ/
题目大意是给一些字符串。。每次给一个新串。。询问在几个给的字符串里出现过。。。

傻叉题就不说了。。
Trees Again 
令Dp[root][Dep]表示子树根为root，最大深度（从root往下）是Dep的个数。。
然后考虑计算。。可以发现子树的状态只跟最深的两个节点有关。。
那么枚举这两个节点和它们的深度。。
然后有一点就是假如两个节点深度一样。。就会有重复。。要考虑一下。。
Easy Longest Common Substring
二分+Hash。。
Two Paths
跟TREECST一样的做法。。首先两个条路径必然有一条边把它们分开。。那么我们需要计算的就是对于每一条边。。它的上发子树和下方子树的直径。。画个图仔细想想就可以写出来了。。注意常数小心TLE。。。
Counting Arborescence
注意这里的图是有向的。。所以没法用那个xx矩阵。。。
所以只好集合动态规划Dp[set][root]表示set的顶点集合。。以root为顶点。。有几个Arboresecence。。。
然后推一下方程就可以了。。
Highway
块状数组。。我记得好像是GDOI的题目？
Copying DNA
集合DP。。记录一下目标串哪些被覆盖了。。常数优化一下>_<。。
好吧。。写的有点简陋。。有时间充实一下。。。

哎。。最近越来越颓废了。。。。做题目也没有神马精神。。。题解也懒得写>_<。。
效仿洲妹弄个plan激励一下自己>_<。。。
OJ：
    SPOJ有生之年刷到前50吧。。
    SGU暂时就不做了>_<。。。
    BZOJ好久没做了。。。哎。。。。
    MAIN里的POI15-17，PA08-10争取AK。。
算法：
    我的计算几何好差>_<。。。。好好学习学习计算几何。。。
    其它的各种算法似乎还是有一点漏洞的。。。。各种模块有时间复习复习吧。。。
    ：各种网络流我其实不是很熟练。。需要加强>_<。。。字符串的各种算法AC自动机和KMP神马的好像长久不写真的是容易忘啊>_<。。上次我就被AC自动机鄙视了。。还一直不知道哪里写错了。。。。
    各种贪心之类的也要好好领悟。。。
    不能盲目做题啦。。。以后弄个本子记录记录心得体会吧。。。。
比赛：
    TC和CF和CodeChef能参加都参加参加吧。。。
    TC以前比赛的题目都去做做。。锻炼代码能力。。。
    多多看看别人的代码。从中学习。。。
一些需要做的东西：
    果然看了题解之后不写代码等于不会啊>_<。。。
    GCJ的题目都去写写吧。。参考参考别人的代码。。。
    国家集训队的作业也要多看看。。。。
PS：
    别再看神马微小说了>_<。。浪费时间啊。。。
@Update:
    SPOJ rank:220
    SGU rank:165
    POI 17：差Ones。。
    PA 2010：差很多。。。
@Update 12.25:
    发现我从来都只是在SPOJ上挑会做的题目捉。。这毫无意义啊>_<
    SPOJ先放放。。。
    TCO 2005-2010都去做掉。。这主要是锻炼代码能力。。
    TCO 2010 Q1-Q3，R1，R2 Finished。。
    还有就是系统学习字符串理论，恶补计算几何。。至少要熟练起来。。然后对贪心的题目也要学会深入理解。。。
    Crotian还有一个类似中国CTSC的比赛啊，题目还是挺好玩的。。好好做做吧。。。
    NOI剩下的题目都应该做掉了。。。
    CTSC尽量吧。。。
    先把POI2007给AK掉。。

这道题我一年前看到过。。。当时吓死了。。毫无思路。。
现在再看看。。发现好像是。。傻叉题？
https://www.spoj.pl/problems/TOP10/

首先注意到一个性质。。就是一些字符串按字典序排序后。。以某个字串开始的字符串是一个区间。。
那么对于这个题目。。我们将所有的字符串的后缀排序。。由于后缀的前缀就是子串。。所以对于一个询问
只需要用线段树来找区间前10大值就可以了。。

注意到显然不能直接将后缀提取再排序。。
可以使用hash搞。。复杂度NLogN^2。。

被N道题目卡住了。。不是不会捉。。老是TLE >_<。。
好痛苦。。。

。。先写一部分吧。。
A：贪心+BFS。。就是每次贪心作出决策直到距离小于100后bfs解决。。注意到如果两个决策的距离一样。。优先考虑x的距离和y的距离的差比较小的。
B：其实就是全局最小割。。套用经典算法就可以了。
C：= =
D：这是POI2006的原题。。。有题解的。。
E：当然可以爬山。。也可以证明结果必然是对角线的交点或者顶点
F：裸的AC自动机就可以了。
G：很傻叉的Dp
H：枚举开始的位置的除5的余数。。就是经典问题了。。
I：dp。。注意到可以使用线段树或者数状数组维护状态
J：暴力

擦。。标程看的我很不爽。。自己做算了>_<。。。
经过各种努力。。终于A掉了yeah～～～好gaoxin。。。
代码写的。。比标程也短不了多少>_<。。。
我的办法还是一开始跟洲妹讲的办法。。就是维护一个数据结构保存所有未访问的点。。
每次对一个点快速找出未访问点中的相邻点。。并删除。。。。
这个数据结构很囧。。。明天再说～～～
代码：
http://www.ideone.com/l5NZB

http://main.edu.pl/user.phtml?op=showtask&task=cuk&con=PA2010
这题目的意思是。。。有N个物品,N<=24，重量<=10^9，分成3堆。。
设3堆重分别为A，B，C且A<=B<=C，求C-A的最小值。。。
看到这个N<=24并且分成3份不难想到要折半搞了。。
考虑前N/2和后N/2个物品的两个方案，
设前N/2的物品的方案是(a1,b1,c1)，

后N/2的物品的方案是(a2,b2,c2)
那么。。由于和是固定的。。只要考虑两个。。不妨考虑a和c。。
设S为所有物品和
那么a1+a2<=S-(a1+a2+c1+c2)
<=>(a1*2+c1)+(a2*2+c2)<=S
S-(a1+a2+c1+c2)<=c1+c2
<=>(a1+c1*2)+(a2+c2*2)>=S
设F(x)=ax*2+cx,G(x)=ax+cx*2,T(x)=cx-ax
也就是说F(1)+F(2)<=S,G(1)+G(2)>=S,求最小的T(1)+T(2)。。
这是个傻叉问题。。。排序降维之后直接数状数组就好了>_<。。。

终于搞定了Stage II >_<
下面是题解：
Antisymmetry：
这个题目很容易想到枚举中间的，然后二分向两边扩展并用倍增hash快速判断。。注意到NLogN的空间会悲剧。。
我的办法是。。空间是NLogN的。。但是底数是可以变的>_<。。我把底数开到20。。需要的空间就少多了。。
虽然速度慢了。。但还好不至于MLE。
PS。我傻叉。。标程是O(N)的。。
Hamsters：
这题的话相信一看到基本会想到快速幂吧。。我注意到这个问题可以转化为一个图论问题，就是n个点的图，AB两点之间的边权是B接在A后面需要新增加的长度。那么其实说白了就是求一个给定边数的最短路径。。这是一个经典问题。。套一下就可以了。。
Blocks:
首先我看到这个题目之后。。想了一会儿。。直觉告诉我贾如当前询问k，那么令C[i]=A[i]-k。。i到j这一段可以全部变得大于等于k的条件是Sum(Ci..j)>=0。。我不怎么会证明。。不过就这样吧。。
然后可以感觉到我们需要求的就是最长的和为正的子串。。
我一开始随便弄了NLogN的做法。。后来发现傻叉爆了>_<。。
看了标程之后才明白。。。把这个看成几何的问题，令Sum[i]为Ci的部分和。
考虑所有点(i,Sum[i])。其实求的就是x跨度最长的终点比起点高的线段。。
那么对于一个终点。。如果它的右上方有点。。显然那个点更优。。
起点也一样。。
所以的话。。我们可以找两条链。。都由那些右上方无点（左下方无点）的点构成。。
然后显然答案就是在两者之间。。然后扫描一条链。。另一条链上的对应点显然会单调移动。。就O(N)了。。。
Sheep：
这个题目题型比较经典。。关键是如果在dp的过程中判断对角线是否违反条件的话。。显然是会悲剧的>_<
。。。。其实最关键的一点是。。合法的对角线永远是合法的，非法的永远是非法的。。
比如说一条对角线上有点。。那么显然点不会变没。。
一个对角线两边是偶数。。那么多条两边是偶数的对角线混在一起分开的区域显然也都是偶数，偶数-偶数=偶数。。
两边有一边是奇数。。那边无论怎么也分不好。。
所以预处理出所有合法的对角线。。直接dp就好了。。
Teleportation：
这题目好囧。。
首先最终的结果的话。。按照与点1的距离。。当然分为6层（这个可以调整来证明）。分别是距离0到5。。
然后可以发现跟1距离为1、2的点，跟2距离为1和2的点。。层数是无法改变了。。
其他的点则可以随意+到某些层里去。。
首先发现把层1的点调到层2去。。结果不会变差，
层3调到层4也是一样。。
所以把剩下的点放到第2层或第3层。。
考虑到2、3层之间的对调。。可以发现必然是要么全放在2层，要么全放在3层。。
然后就好弄了。。

Guilds
傻叉题，首先如果有一个孤立点显然不行。其次把图看成树（忽略多余边），奇数层染K，偶数层染S就可以了。。
Railway
见洲妹的博客>_<
Beads
首先注意到如果枚举每个K。。那么实际上要考虑的项链总个数为N/1+N/2+…=O(NLogN)
那么枚举K的话。如果能快速计算出所有项链的Hash值来判重，还是doable的。。
那么Hash用倍增算，判重的话要考虑翻转，用两个集合搞，一个集合保存对称的串，一个保存非对称的。。
遇到对称串，放入集合，遇到非对称的就把它和它的反转一起放入集合。。
然后结果就是|对称集合|+|非对称集合|/2
Divine divisor
很容易想到因式分解之后瞎搞。。但是我用rho+miller-rabin搞了很久还是只有89分>_<。。
看了标程之后才明白，因为所有数小于10^18，那么首先用所有小于10^6的素数去除。。
那么接下来的数如果有3个质因数pqr，就矛盾了。所以只可能是p，pq,p^2这样的形式。。
然后考虑它们之间两两的最大公约数。由于所有数最多只有2个素因子，那么如果该最大公约数是某数的真因子。就肯定是素数。。
然后考虑某数可能是p^2的情况。。根号一下就可以了。。
然后剩下来的数要么是pq,要么是p。。而且两两之间要么相等要么互质。。所以可以直接拿pq去除所有数。。结果算两份就可以了。。
然后用miller-rabin判断是否是素数。。OK了。
傻叉题，对于每个数储存一个数组表示在原序列中的位置集合。。
然后一个个往下找，每次找当前位置后的第一个询问序列的当前数。。
找不到就挂了。。