昨晚第一次做cf，结果做了两题就笔记本断电滚粗了。。
A Sereja and Coat Rack 水题
B Sereja and Suffixes 预处理
C Sereja and Algorithm
题意：给出长度<=1e5的字符串s（只含有xyz），给出算法：随意选三个字母长的子串，且要求它不是xzy、yxz、zyx三个中的一个，然后可以随意重排它。直到找不出这样的三字母长的子串，算法结束。对于每个样例，给出m个询问（m<=1e5）：l r。问s[l……r]能否在有限步数内终结。
思路：可知如果会终结，则最后的字符串一定是以下情况中的一种：
(1)形如xzyxzy……或者yxzyxz……或者zyxzyx……
(2)只有一个字母或两个字母。
注意第（2）种情况，被坑了。。
所以预处理统计符合条件的长度为i的字符串中x、y、z各自的个数即可（三种情况），然后统计s[l……r]中x、y、z的个数
D：现在还不会。。。。。。。
E Sereja and the Arrangement of Numbers
题意：给出n（n<=2*1e6），m(m<=1e5),给出m个互异的整数。定义数列:a1、a2……an，如果任意两个数ai、aj(ai!=aj)存在pos(1<=pos<=n)，a[pos]=ai,a[pos+1]=aj或者a[pos]=aj,a[pos+1]=ai,则称该数列合法。给出的m个数有各自的价值，问组成长度为n的合法数列最多能得到价值。
看了题解才知道是图论，，弱爆了。。
先求出i个不同的数组成合法序列的最小长度。然后对于n只要在这个数组（已经单调）中二分出它的位置pos，pos表示组成长度为n的合法序列最多可以用多少个不同的数。然后将给出的m个数降序排列，取前面pos个。
关键在于求出i个不同的数组成合法序列的最小长度：
方法是可以把i个不同的数看成i个点，两两之间连边形成完全图。有边表示两点相邻。问题变为求最小加多少条边可以使其变成半欧拉图。（因为如果是半欧拉图的话，就可以不重复的遍历所有边，也就是找到了一个序列满足所有相邻关系）。分奇偶讨论，偶数要加n/2-1，因为i为偶数的话，每个点的度数是奇数，最后要补成只有两个奇度点。注意序列长度=边数+1；
polya定理&&burnside引理
专题地址：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=36645#overview
这里有更完整的：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=484
看了下大白书，做下上面的习题。两个定理叙述很简单，证明暂时没看，先把题做的差不多再说。。
一些小结：
1.置换。一对一的函数
2.置换的乘法：满足结合律，但不满足交换律
3.置换分解成几个循环的乘积，因为假如将一个置换看成一条有向边那么形成的图中每个点都是入度为1，出度为1.所以一定是若干个圈。
4.独立的循环之间的乘法满足交换律
5.设A是与元素个数为n的循环，则：
(1)若n为奇数，则A*A是一个n个元素的循环
(2)若n为偶数，则A*A是两个n/2个元素且相互独立的循环的乘积
6.引出：由5的性质可知：
(1)一个长度n为奇数的循环B，一定可以找到一个长度为n的循环A,满足A^2=B;
(2)两个长度都为n的不相交循环B和C，一定可以找到长度为2*n的循环A，使得A^2=B*C;
7.继续引出：
(1)长度n为奇数的循环既可以是两个长度为n的循环乘出来的，也可以是两个长度为2n的循环乘出来的。
(2)长度n为偶数的循环只可能是两个长度为2n的循环乘出来的。
下面是一些题目
UVA 10294 Arif in Dhaka (First Love Part 2)
数学推算。。
2013 hangzhou regional I题
感觉最近写代码总是小错误不断，没有刚学acm时认真了。。
uva12589 Learning Vector
比赛的时候没想到是背包的dp啊。。。
思路：先按斜率排序，因为对于确定的一些向量，一定是斜率大的在前可以使总面积最大化。dp方程主体是背包，但是加了一维，表示最右侧的向量的最高点的y值。也就是dp[i][j][k]表示前i个向量中选取j个且最右侧高为k的最大面积。可以用滚动数组省掉阶段那一维，然后和一般背包不同的是，因为如果填表的话，每次对于dp[i][j][k]，都要枚举dp[i-1][j-1][0……k-1],复杂度很高，所以用刷表的方式，每次用dp[i][j][k]更新dp[i+1][j+1][k+p[i].y]。
splay tree专题
很早以前就想学splay，但是迫于图论方面的知识还很不全面，于是放弃了计划，第一次区域赛之后打算学一下splay，所以这几天就开始看起来了，看着爽哥的ppt和模板慢慢学，到现在为止基本上理解了splay树的旋转和splay操作，然后就开始做题啦。。接下来要开始重点转入dp和数据结构的学习了~
1.关于rotate和splay操作的一个问题：为什么旋转x结点的时候只pushup()fa[x]?
答：因为rotate操作是用在splay操作里面的，由于splay的时候x结点可能被旋转多次，所以x结点为根的子树的结构在不停变化中，没必要每次旋转都pushup，但是旋转点x的父亲结点却在旋转后不会再旋转了，所以要pushupx结点的父亲。最后全部旋转完毕在pushupx结点就行了。
2.由此可能想到另一个问题：splay的时候，又是旋转x结点前要先旋转x的父节点y，这时候pushup了y的父节点z，那么y结点有没有pushup呢？
答：有的，因为每次旋转y必然伴随着旋转一次x，所以旋转x的时候，y结点pushup了。
3.要注意哪些地方要pushdown。旋转一个节点前要先pushdown父节点，再pushdownx节点，将信息下推，完成这个节点的”使命”再旋转。访问一个节点的操作之前记得pushdown，再对这个节点操作。
4.深刻理解splay树的“序”:这个序是很广义的，没有序也可以是序。加入初始插入节点完毕时其实就形成了一个“序”。这时它的中序遍历序列就是它的序，也就是说此时splay中的任意两个元素间有了一种前后关系，这就是序。splay操作会维护splay树的平衡但是不会改变这个序，也就是说splay操作之后树的中序遍历序列式不变的。
5.findpre(x)和findnext(x):这两个操作必须先把x节点splay到根。因为如果不是根，那么x的父节点有可能是所求答案，但是findpre()和findnext()并没有考虑
6.关于翻转操作
11月1号完成此题
贴个链接，然后睡觉。。
用二分和平衡树完成
线段树优化dp，待做
poj3171
lightoj 1415
bzoj1835
uestc 1501
poj2376
poj2374
zjoi2010
fafu1231 http://acm.fafu.edu.cn/problem.php?id=1231
poj2355
hdoj4719
uestc1558
接下来要深入学习不单调的斜率优化dp，线段树深入，线性规划，分数规划，还有splay和可持久化的一些数据结构
hdoj3698 Let the light guide us——线段树优化dp
终于ac了，好久不写线段树，成段更新变生疏了。
第一道用线段树优化的dp题。线段树用于成段更新，求区间最小值（包括历史值在内的最小值）。
dp[i][j]:前i行，且第i行选第j个可以得到的最小花费
dp[i][j]=min{dp[i-1][k]|1<=k<=m且abs(j-k)<=f[i-1][k]+f[i][j]}+cost[i][j]
复杂度n*m*m，超时
其实对于确定的i，j可以选择哪些k呢？abs(j-k)<=f[i][j]+f[i-1][k]等价于以j为中心，f[i][j]为半径的区间和以k为中心，f[i-1][k]为半径的区间的重合部分，so。。求解每个阶段的时候，可以建立线段树[1,m]，然后不断加入上个阶段的dp值，dp[i-1][k]的区间是
[max(1,k-f[i-1][k]),min(m,k+f[i-1][k])]，线段树维护最小值，注意lazy字段，lazy表示要往下更新的最小值，但是子孙节点的lazy有可能是小于它的（加入先对父区间更新为10，然后左子区间更新为8，这时候子区间的lazy就要比父区间小了），所以pushdown的时候，只有儿子节点的lazy没值或者小于父节点的lazy，才能重写这个儿子节点的lazy,否则可能导致结果偏大
斯坦纳树相关
1.复杂度 O(n*3^k+cE*2^k)
hdoj3401 Trade
单调队列优化dp，太菜了做不出来啊，看了题解才ok
http://hi.baidu.com/mobius_strip/item/a0152244c47e4ec9c1a592f6
hdoj4122 Alice’s mooncake shop
哎，一道简单的单调队列比赛时候居然没做出来，很不应该。
hdoj3507 Print Article
比较水的斜率优化dp
dp[i]：前i个词的最小cost
s[i]：前i个词的cost之和
w[j,i]:把第j到i个词分在一行的cost
dp[i]=min{dp[j]+w[j+1,i]}(0<=j<=i-1)
其中w[j,i]=(s[i]-s[j])^2+m
dp[i]的是式子展开：dp[i]=min{dp[j]+s[j]^2-2s[i]*s[j]}+s[i]^2+m
k=2s[i]
x=s[j]
y=dp[j]+s[j]^2
点的横坐标非递减，所以可以用单调队列维护凸壳，因为斜率非递减(即决策单调)，所以可以均摊O(1)的求出最优决策是哪个，总复杂度O(n)
//////////////////
关于决策单调的另一种严格证明：
即证明w[i,j]满足四边形不等式：对于i<i’<j’<j,w[i,j']+w[i',j]<=w[i,j]+w[i',j']
(s[j']-s[i])^2+(s[j]-s[i'])^2<=(s[j]-s[i])^2+(s[j']-s[i'])^2
继续化简:-2s[i]s[j']-2s[i']s[j]<=-2s[i]s[j]-2s[i']s[j']
s[i]s[j']+s[i']s[j]>=s[i]s[j]+s[i']s[j']
(s[i']-s[i])(s[j]-s[j'])>=0
因为i<i’<j’<j,(s[i']-s[i])(s[j]-s[j'])>=0显然成立，所以w[i,j]满足四边形不等式，决策单调
hdoj2829 Lawrence
我擦。。去掉一个语句居然就ac了，纠结n久。这题貌似不用斜率有优化，用四边形不等式优化也行。具体明天再说。。
第一道状态是二维，决策一维的斜率优化dp，其实和状态一维的差不多，无非多了层外层循环。每个阶段都用一下单调队列。。
bzoj1010 玩具装箱toy
斜率优化dp第一题，纠结了n久。。最后输出改成%I64d就PE，要%lld才能ac，而且把输入也改成%lld比%I64d快看了200MS。。
终于大致清楚了斜率优化dp，记下几点：
(1)求最大值，维护上凸壳；求最小值，维护下凸壳；
(2)当点的横坐标单调，且斜率单调时，此时决策是单调的（即满足四边形不等式），可以用单调队列从前往后找最优决策(怎么找？只有最优决策点的值比两侧都要优，注意只有二字)，找到之后前面的都是无用决策了，插入点的时候维护队列凸壳。
(3)如果点的横坐标是单调的，而斜率不单调，这时候决策是不单调的，但是可以发现最优决策点与两侧相邻点的斜率分别是k1,k2(k1
正确做法是用平衡树维护动态凸壳。（我擦，说着简单，写着蛋疼无比）(这种情况细节还不太会，有待学习)