hdoj3308 LCIS

单点修改的最长连续递增子序列
比前面几题都要简单,但是磨蹭了n久。。原因是query的时候没弄清楚,query的时候可能去左子区间也可能去右子区间,还有一种是答案是左右子区间拼起来的,想是想到了,但是还是写错了。。这种情况下应该是左起点选max(L,m+1-rmax[lson]),右起点选min(R,m+lmax[rson]).但是我原来写的时候只有当L<=m+1-rmax[lson] && m+lmax[rson]<=R的时候才考虑这种情况。。。

poj3667 Hotel

经典的区间合并的线段树
关于找满足要求长度的最左连续空闲区:
维护左起连续空闲区lmax,右起连续空闲区rmax,区间最长连续空闲区max。当区间max=len,若是则转入左子区间,否则看rmax[lson]+lmax[rson]是否>=len,若是,则直接返回m+1-rmax[lson],若还是不行,则忘右区间找一定能找到(因为已经确定max[id]>=len)。
为什么这样是正确的?
如果最终答案不是lmax那段,也不是rmax那段,而是当前区间中间的一段空白,那么如果它被两个子区间隔开,那么必然是rmax[lson]+lmax[rson],否则它必定在左子区间或右子区间,这种情况下会继续往下找。知道所求区间是lmax或rmax或rmax[lson]+lmax[rson]或到达叶子结点。所以只设置这些量是足够的。

poj2991 Crane——线段转化成向量,向量旋转

神奇的一道题,解法很奇妙————对我而言。。
题意:给出一些线段,起始时它们一次邻接的排列在二维笛卡尔坐标系上,端点分别是(0,w1)(0,w1+w2)……(0,w1+w1+……+wn),wi是第i个线段的长度。给出一些操作s,angle。表示把第s条线段的右端点p的后面的所有线段以p为中心旋转到p点两侧的线段成angle角度。(angle角度=以线段s以p点为中心逆时针转到与线段s+1重合经过的角度),要求每次操作后输出线段n右端点的坐标。
难点:直接做很麻烦,因为每次旋转的中心点可能不同,操作无法统一化表示,如果能统一化的话,就可以使用线段树了。
关键点:
1.把线段看成向量。
2.当进行操作是s,angle后,第s+1条线段开始的线段所在直线都旋转了angle角度。
3.向量(x1,y2)逆时针旋转a弧度后的端点坐标为
x1=x0*cos(a)-y0*sin(a);
y1=x0*sin(a)+y0*cos(a);
当顺时针旋转b弧度时,a=-b。相当与旋转了负角度。

有了这三个认识,题目就简单了。线段树中的结点(id,l,r)存储的是第l条线段的右端点到第r条线段的右端点表示的向量的右端点的横纵坐标。所以其实答案就是(x[1],y[1])。
那么怎样把题目告诉的旋转到成angle角度转化为旋转了多少角度呢?
这个简单,只要开个数组angle[],angle[i]表示第i条和第i+1条线段现在所成的角度。那么假如现在要旋转到成r弧度角,那么旋转了r-angle[i].注意化成弧度计算哦。

poj1436 Horizontally Visible Segments

终于ac了,不容易啊。。
题意:给出n条垂直的不相交线段,如果两条线段之间可以用一条不穿过其他线段的水平线段连接起来,那么称这两条线段互相可见。如果三条线段间两两可见,那么称这三条线段组成三角形,问总共有多少个三角形。
思路:每条线段的id(将线段按x坐标排序,id从1开始)作为颜色,用线段树维护区间的颜色。每次插入一条线段,就询问这段区间内有哪些颜色(也就是之前插入的哪些线段与当前线段互相可见),之后更新该区间的颜色。起始时整个区间颜色为0,当一段区间内有多种颜色时color设成-1。
注意一点:
| | |
| |
| | |
1 2 3
上图中x坐标=2的两条线段的y坐标分别为(1,2)(3,4),那么显然线段1和3是互相可见的,但是因为在线段树上插入线段3时[1,4]这个区间颜色全是2,所以会会认为线段3与1不是互相可见。这样就造成了漏数。
解决:方法是线段树的每个点乘2.这样x、x+1变成2x、2x+2,中间的2x+1这个点就可以表示区间(x,x+1).

poj3225 Help with Intervals——线段树

开始对于区间乘以2的方法没理解透彻导致错误。
由于涉及开闭区间,所以既要用到点又要用到区间。普通线段树实际上是将区间堪看成离散的点,每次操作都是对点进行操作,对连续的区间则无可奈何。
解决方法:对于数x,x乘2,2x表示点本身,2x+1表示(x,x+1)这段区间。这样问题就解决了。

round#215 div2

昨晚第一次做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)
数学推算。。

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.关于翻转操作

线段树优化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,否则可能导致结果偏大