QhelDIV

@____@

我的Splay书写规范

调Splay太恐怖了,虽然不难,但是为什么bug这么多。。。这里记一下原则性问题吧。。。

类名叫SplayTree

  • 在我的写法里,每个SplayTree对象不仅代表一个点,它代表整棵子树
  • 每个对象里有一个特殊的阈值,SplayTree *Nil,它代表不存在的点(即叶子结点的后继或者是总根节点的前驱),算法导论上好像称之为哨兵,预处理的时候所有的前驱后继都等于Nil(其实原来把Nil定义在了类的外面而不是类的阈值,但是这样会很麻烦。。所以干脆再开个变量叫Nil好了)
  • 下面的代码表示阈值:
    • int v,size;//分别是键值,子树大小,
      bool pl;//place 表示该节点在父节点的哪个位置
      ST *pr,*suc[2],*Nil;//分别表示前驱,两个后继,和Nil节点的位置
  • 下面的代码声明了各种函数:
    • /*由于SpayTree太长了,一下所写为ST*/
      void mt();//maintain 即维护Splay,保证信息的正确性
      void ini();//初始化,将所有的前驱后继都改成Nil
      void trans(ST *tar,bool place);//将该子树移动到tar的place边(place=0表示左子树,反之右子树)
      void rotate();//旋转,一个函数搞定左旋/右旋
      void Splay();//核心操作,即将某节点提到根
      ST *find_v(int fv)//找到fv所在的位置,找不到返回它应该在的位置的根(按照数字值查询)
      void insert(int iv/*也可以是 ST*p */);//插入iv到相应位置
      void find_s(int pos);//按照size找第pos小的元素,也就是如果要求第pos小的元素是哪个,就可以用这个函数在O(lgn)的时间复杂度内完成
      ST *fmin/*或fmax*/();//找到最小值所在的位置(返回指针)
      void merge(ST *obj);//将obj所在的Splay合并到该节点所在的Splay...
  • 下面的代码描述了trans,rotate,Splay的过程
    • 	void trans(ST *tar,bool place){//ST::移形换位
      			pl=place;
      			pr=tar;
      			tar->suc[pl]=this;
      	}
      	void rotate(){//旋转
      	bool ppl=pl;
      	ST fprev=*pr;
      		suc[!pl]->trans(pr,pl);//移动子树
      		pr->trans(this,!pl);//移动原前驱
      		trans(fprev.pr,fprev.pl);//移动该节点
      		suc[!ppl]->mt();
      		mt();
      	}
      	void Splay(){//Splay操作
      		while(pr!=Nil){
      			if(pl==pr->pl && pr->pr!=Nil)
      				pr->rotate();
      			rotate();
      		}
      	}
  •  的

 

 

刷题小记

今天早上。。出于某种不可抗拒的原因,没心情写题,所以正好小记以下(我是按分类记录,不是按日期记录):

  • 动态规划:
    • SCOI2008 着色方案  很好的题,f[c1][c2][c3][c4][c5][k]表示状态进行转移(上网看)
    • HAOI2010 计数  主要是涉及到 具有不可区别物体的集合的排列(比如重新排列SUCCESS能构成多少种不同的串,公式是(n,k1)*(n-k1,k2)*(n-k1-k2,k3)... = n!/(k1!*k2!...*kn!)其中ki表示某种元素的个数
    • SDOI2010 地精部落  这个题网上说的方法看不太懂,神马之云想的方法是 f[i][j]表示长度为i的序列第1个是j且开始下降的序列个数,g[i][j]表示...且开始上升的序列个数,那么f[i][j]=Sigma(g[i-1][k])k<j,g[i][j]=Sigma(f[i-1][k])k>j,dp的时候记录一下Sigma信息就可以省掉转移的那一维。
    • HAOI2010 最长公共子序列  dp时记录方案数,再容斥掉多计算的即可
    • HAOI2010 软件安装  好题 一开始看不就是个简单的树形依赖背包嘛,写出来才发现图里面竟然有环,不过既然是环,选一个就全都得选,所以缩成点,构成新的图,再在新图里面dp就可以了(注意环连接的要么什么都没有要么是外向树,对于外向树,缩点之后都不可能有前驱,所以连接到0,这样就是棵标准的树了,从0开始dp就行了)
    • 越狱第1季第13集 大神的做法不会,不过好像和我的方法有点像(二分答案,然后检查)
    • 瑰丽华尔兹 又是好题 f[k][y][x]表示第k段的结尾在y行x列的最长滑动距离,转移O(n)的,所以优先队列优化就可以Ac
  • 图论
    • 公路修建 。。。看出来了很简单,裸的最小生成树,不过由于边数太多Kruskal会跪掉,所以只能用Prim了
    • 卡赞群岛 找到双连通分量,缩点然后dp(由于是无向图,缩点之后必然是个无根树,或者是无根树森林,所以可dp。
    • HAOI 软件安装 见上文
  • 贪心
    • SCOI2008 斜堆 很有意思的题,按照斜堆的规则,最后插入的点一定在最左边(也就是便利的时候从不向右转),如果没有根变成左子树的情况,每次找最左边的点,删掉,然后模拟一下就行了(基于字典顺序最小的原则)。考虑上较小元素会替代根的情况,如果我们发现某个极左点没有右子树,那么说明它是叶子结点或者是替代根的元素,此时必须先删它(否则不可能构成目标树),基于最小字典序的原则,这些步骤合在一起就是:每次从根向左找没有右子树的点,一旦发现就把它删掉,并且将它的祖先的左右子树互换,最后倒序输出删点顺序即可(有一个特殊情况,即某点的左子树只有一个叶子结点,而且它没右子树,那么此时删除那个叶子结点(基于字典序最小的原则)),相关拓展见这位大神网志
    • 立春树 树上贪心,比较简单,不说了
  • 数论
    • 双亲数 貌似都是利用容斥搞的,用Mobius函数搞会快点,关于Mobius Function见Noi2010 能量项链,HAOI2011问题B,以及网上各种题解。