转移到 qheldiv.net

又是一年省选时，昨天比赛了一天，比较累，但是结局还好。

比赛的成绩wyfenger第一，我第二，认识的人中进入省队的还有 省实验中学的3个（王梦迪（初三），王宇飞，常跃如），郑外的陈科。

结果出来前比较忐忑，因为毕竟这可能是OI生涯的结尾，不过即使可以参加Noi，也只剩下3个月了。

上午的比赛

前两题很简单，简直是NOIP普及组水平，以至于刚开始看到第2题还以为是最小费用最大流，但问题是没有搞到200的人很多，也许河南真的是没有多少人好好学Oi吧！至于第三题，是和牛棚的灯一摸一样原题！（比赛前我还看到了这题，但是没有写）其实 我已经写出 Gauss-Jordan消元法，但是没有考虑多解的情况，检查了半天不对，所以最后还是写了个暴力，总共230

下午的比赛

下午的比赛比上午难一些，第一个问题可以用线段树Ac，但是形式不太一样，不过不是很难想，想了10分钟，加之看到第二题像是个恶心的搜索……所以就决心搞第一题，写了1h，调试+对拍了1.5h（手动对拍），最后还好100分，否则就很悲剧了，（无力吐槽这题的数据，最裸的暴力算法就可以搞到60分）

而第二题其实可以用最短路做，甚至也有模拟Ac的办法，而我在第一题上花了大部分时间，最后仅仅交了个骗分（输出-1能得30……）

总共130

去年省选比今年质量高多了，难度也大多了。。

今后恐怕就不能用win8了，

第一

还有大约5天就到期了

第二，Noi是在Linux下的，所以只能乖乖的用Ubuntu了。

时间已经很少了，水平还差得很远。

又是一年省选时，这是最后一次省选了。

接下来一个星期就复习已学算法吧。。

（只搞下划线的）

影踪禅院

问题大意是 给定一个无向图，求最小的Q使得标记Q个点后其它所有点都可以到达这Q个点中的某个点 ， 以及方案数。

对于每个联通块：

• 显然，如果坍塌点不是割点，不影响图的连通性。
• 但是可以知道，如果坍塌发生在割点，肯定

的

总是想得很复杂，其实很简单。

用O(n²)或者O(nlog_n)的时间复杂度统计出f_i即以i开始的最长上升序列是多少

因为字典序的缘故，暴力找最优解

假设某次询问是a，给定的数列是{A_i}

对于第一个位置，为了使字典序最小，我们一定选最早的i，使得f_i1>=a

对于第二个位置，A_i2一定 且f_i1>=a-1所以接着向后找第一个满足着两个条件的位置

……

这一段的代码：

	for(int i=1;i<=M;i++){
	int j,a,b,pr;
		fin>>a;
		b=0;
		A[pr=0]=-1;
		for(j=1;j<=N;j++)
			if(f[j]>=a && A[j]>A[pr]){
				Ans[++b]=j;
				a--;
				if(!a)
					break;
				pr=j;
			}
		if(b<a){
			fout<<"Impossible\n";
			continue;
		}
		for(j=1;j<=b;j++)
			fout<<A[Ans[j]]<<" ";
		fout<<endl;
	}

调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，以及网上各种题解。

几周前写的"NOI 郁闷的出纳员"最后3组一直TLE，不明原因，但真正让我费解的是读入问题

• 首先，我用的是fstream读入，于是我猜测是读入导致超时。
• 于是我换用cstdio读入，但是问题是我的Splay莫名其妙的让读入出现问题，比如有些时候'S'竟然读成了'9'等等
• 而奇怪的是无论我用Windows下的Mingw环境还是Ubuntu 12.10，都是没有问题的，难道是评测环境Noi Linux的不同嘛？

明天安装Noi Linux再看看吧。

先声明一下下述的变量

N为总天数,

A[i]表示第i个数字,

f[i]和g[i]的定义见下文

Max=max(f[i])1<=i<=N

第一问就是个最简单的最长下降序列,f[i]表示当前包含第i个数字的最长下降序列,

第二问稍复杂,我的分析:

1. 如果没有不能重复这个限制,非常好想到用g[i]存储当前包括第i个数字的最长下降序列的个数
   1. 如果f[i]被f[j]+1(j<i)更新,g[i]就更新为g[j]
   2. 如果f[i]等于f[j]+1,g[i]就更新为g[i]+g[j]
   3. 最后输出的方案数就是∑g[i] (f[i]=Max,1<=i<=N)
2. 如果加上不能重复这个限制,想一想会发现对于任意两个相同的数字A[i]和A[j](j<i),如果A[i-1]的值已经求出,那么之后的任何f[i]值都用不到A[j]了,因为f[i]>=f[j] 且 g[i]>=g[j],所以遇到A[i]=A[j]的情况就把A[j]标记为不可用,以后动态规划的时候就跳过j,这样就避免了重复,一下将证明该算法的正确性(分成两个独立的部分)
   1. 用数学归纳证明按照上述做法,当程序结束时g[i]表示的序列总数中没有任何重复:
      1. 首先对于i=1时,f[i]=1,g[i]=1只有一种方案,所以没有重复
      2. 对于N≥i>1,假设当前要求f[i]和g[i],那么对于1<=j<i的g[j]都是没有任何重复的(归纳假设)
      3. 只有A[j]>A[i]且f[i]=f[j]+1时才有可能发生重复,因为g[j]没有任何重复,所以g[i]有重复当且仅当枚举j的时候有A[j1]=A[j2]且j1≠j2(举个例子:3 2 1 3 2 1,要求f[6]和g[6],当j1,j2取1,4或2,5时显然重复了).
      4. 每遇到A[i]=A[j]就把A[j]删去,保证了数列元素唯一性
      5. 按照上述做法 可以做到没有j1,j2(j1≠j2)使得A[j1]=A[j2](因为数列保证了元素的唯一性) , 那么g[i]也是没有任何重复的.
      6. 注:其实上面的话可以简述为:因为算法保证了元素单调性,所以不可能发生重复
   2. 接下来证明g[i]没有少也没多计算任何情况(算出的g[i]是正确的)
      1. 容易看出g[i]不会比正确的结果大(删除序列元素不会增加答案)
      2. 假设某个被删除的元素为A[j],那么肯定有A[i]=A[j](i>j),而g[i]包括了g[j]的所有情况(g[i]≥g[j]),所以不会有任何一种非重复情况被遗漏
      3. 综上,算出的g[i]是正确的

我的代码(因为答案可能很大,所以用了高精度,并重载了"+"运算