almost 3 years ago

前言

NOI2009的题目都好神啊QAQ

二叉查找树

题目意思很简单,就是要你不断修改一棵Treap,使得最终答案最小。
首先我们先离散化数据值,从小到大重标号点,再设为区间且满足根结点的键值构成一棵Treap的最小代价。
然后观察到区间肯定是由构成的。
如果,那么我们可以直接把点作为根,代价为。其中意思是区间的访问频度和(因为以一个点为根相当于把树中点的深度都加上)。当然也可以花费的代价把降成
否则我们必须花费的代价把升成,代价就是
方程就很显然了:

treapmod.cpp

变换序列

很显然题目的模型可以化成一个二分图。
如果存在度数为的点显然无解,如果存在度数为的点那么这个点对应的点就唯一确定了,把确定的点都删除后,原图就变成了若干个简单环构成的图。每次我们尽量取最小的边走就行了。
transform.cpp

诗人小G

这道题就是传说中的四边形不等式。。。定义不熟悉的你可以去看看黑书。。。
首先我们考虑最裸的,设为前个句子的最优答案,为前个句子长度的前缀和,那么有:

,那么有
是凸完全单调的,这个你可以自己证明一下(我不会说我看的byvoid的证明),然后就是裸题了。。。
poet.cpp

植物大战僵尸

这道题我们将模型转化一下,如果保护了,那么连边,如果在同一行,右边的是保护左边的。
然后如果图中存在环,那么这个环和这个环能够到达的点都肯定不能被攻击,删去这些点。
然后我们把边反转,就是求一个最大权闭合图,做法参见胡伯涛论文。
pvz.cpp

管道取珠

这道题的做法好神奇。。。
首先我们难搞的就是那个平方,但我们可以注意到一个等式
因此我们只要考虑有多少个二元组,其中是任意的操作方法,满足两操作的结果相等。
表示操作在管道中取了个,在管道中取了个,操作在管道中取了个,在管道中取了个的答案。
首先我们可以忽略掉一维,因为。转移方程就很简单了(为了方便转移方程还是写成四维的):

你要没事做也可以加一个队列优化
ballb.cpp

← NOIP2015总结 分块专题 →
 
comments powered by Disqus