NOI2006
2008年7月19日 21:35
NOI2006解题报告
day1
network
很经典的treedp，至少我是想不到的。
首先题目中给的权是边权而不是点权（所谓边权就是说两个点之间的权，而不是点上的权），因此要首先把边权变成点权才方便计算。它的那个计费方式可以看成是这样，对每棵子树A，谁少收谁的钱，一样多收B的钱。所谓对某个点i收钱，是指求出i到以A的另一个儿子为根的子树中的所有点的流量和。试一试就会发现，这样算出来的结果与直接计算是一样的。于是我们给每个非叶顶点标号，如果这棵子树要收A的钱，那么就标A，否则标B。这样，对于每一个叶节点，如果知道了它的所有祖先的收费情况，就知道它要交多少钱了。因此我们可以这样表示状态：f[i][l][S]表示对于节点i，当前还剩下l个A的配额（就是说在以i为根的子树所管辖的节点中，要有l个A），然后i的祖先的收费状态是S时的最小费用。于是推起来就很容易了，
![\[ f[i][l][S] = \min_{0 \le k \le l} { f[child[i][0]][k][S+newS] + f[child[i][1]][l-k][S+newS] } \]](http://agnimon.is-programmer.com/user_files/agnimon/epics/58200a269d337447cd272342034c7c5900e28a2b.png "\[ f[i][l][S] = \min_{0 \le k \le l} { f[child[i][0]][k][S+newS] + f[child[i][1]][l-k][S+newS] } \]")
其中newS表示i的收费状况，这个状况可以根据l来确定。很显然，l不小于1<<(n-dep[i]-1)的时候要收B的钱，否则要收A的钱，其中dep[i]表示i的深度。特殊情况是i为叶子，那么就要根据l来算i的状态，然后算出费用即可。这个算法据说有80%的分。
但是l最多可能到1024，i最多也是1024，然后S最多还是1024，这么个数组怎么开得了啊，除非到下个世纪全世界人都用上1T的内存了再说吧。仔细考虑，假设i的深度叫t，那么l最多有可能是2^{n-t-1}，而S最多只有2^{t-1}，两个乘起来还不超过2^n，于是这就可以存下来了。我是采取把l移位到s前面，合成一个整数，然后再记s的位数来存的，题解是说做hash表，这个一直是我基不擅长的东西。
问题是，嗯，还是没AC。
happybirthday
呜呼，这题是（几乎可以认为）一次AC的，郁闷死了
一个经典而简单的Treap题。据说move有很好的分数。再据说要用treap的题move都会有很好的分数，再再据说move写起来可以比treap短几百行，好了，没什么好说的了。
嗯，首先，get_present就是插入然后删除然后再插入，told就是把删除的那个名字说出来。很显然插入的元素会有很多的重复，于是我是用一个treap套的一个链表，treap是根据果冻数来平衡的，链表里头存的是名字。其他的就直接按照题目做就可以了。
然后为什么没一次AC呢？很简单，链表删除的时候如果删掉了链表头，那么在treap里头保存的那个head也要相应改变。然后这个我忘了。加上去，AC。
worm
这题是有名的灵异恶心题，然后如果按5小时来做的话恐怕连题目都看不完，orz。其实我连题目都没怎么看明白，还是不说了…
day2
profit
经典最大流的题。按照Amber的说法，题目其实是一个最大闭合子图的模型，也就是说一个有向图上，每个顶点有点权，可正可负，求一个子图，使得子图之中的任何一个顶点的后继都在子图中（即，具有封闭性），而且这个子图的顶点点权之和最大。转移到这个题目上来，我们可以把顶点看成是两类，一类是顾客，一类是基站，然后如果顾客使用基站的话就从顾客到基站连一条有向边，基站的点权是负的，顾客的点权是正的。于是根据amber写的通用解法，把所有原图有向边的流量设为无穷，然后新增一个源，指向所有权为正的顶点，边权就是该点的点权，再新增一个汇，从所有权为负的顶点指向汇，边权为该点权的相反数。这样，求出最大流之后，用从汇出发的边流量之和减掉最小割的值就可以了。
正确性是显然的，首先，最小割一定不会包含无穷边，因此最小割一定是从源出发的某些边和进入汇的某些边构成的。最小割把s-t分成了两个连通分量，我们把包含s的连通分量叫做s集，把包含t的叫t集。既然不包含无穷边，那么如果某个顶点在s集中，从它出发的所有边一定也在s集中，因此它的后继一定在s集中。因此，s集是满足要求的。关于权的计算可以这么看，最小割的值是由从s出发的某些边（把这个集合叫做A）和进入t的某些边（把这个集合叫做B）构成的。注意到s集中的那些负权点，由它们指向汇的边就是B集。而那些不在s集中的正权点，源指向它们的边就是A集。因此，用由S出发的所有边的边权和减掉最小割，就相当于减掉了不选的正权点和负权点造成的损失。那么为什么这样求出来一定是最大值呢？因为每一个闭合子图都可以与某一个s集建立一一对应关系，然后每一个s集又可以与一个割建立一一对应关系。既然这个割是最小的，那么闭合子图就一定是最大的。
然后，这题肯定不能用邻接矩阵来存边了，我不喜欢链表，不管是真的还是伪的，所以就写了前向星。写的时候有一些技巧，就是加入一条边的时候就顺便加入反向边，然后每一条边一个指向反向边的指针（当然，反向边的指针就指向正向边了），这样不管是正向边还是反向边都不用分开来处理，只需要当成一般边来做就可以了。也就是说，在找流的时候，面对一个改变量，不管当前边是正向边还是反向边，只需把它加上去，然后把当前边的反向边减掉就可以了。我WA就是因为这个原因，我以为要分开处理。
bag
其实这个题只有一个要点，就是［无限制的点不影响概率］，也就是说不管两个限制之间隔了多远，或者第一个限制是否处在序列的最前端，我们只要简单地把无限制的段删除，按照有限制的点来处理就可以了。这个证明是这样的。
不妨假设第1次实验是无限制的，第二次实验限制颜色必须为k，设![\[s=\sum_{i=1}^t a[i]\]](http://agnimon.is-programmer.com/user_files/agnimon/epics/18e6ad6667b1d3d8b66e353f67f47db67e74822a.png "\[s=\sum_{i=1}^t a[i]\]")
，那么
![\[ \begin{matrix} P & = &\sum_{1 \le i \le t, i \ne k} \frac{a[i]}{s} \times \frac{a[k]}{s+d} + \frac{a[k]}{s} \times \frac{a[k]+d}{s+d} \\ \ & = & \frac{s-a[k]}{s} \times \frac{a[k]}{s+d} + \frac{a[k]}{s} \times \frac{a[k]+d}{s+d} \\ \ & = & \frac{sa[k] - (a[k])^2 + (a[k])^2 + a[k]d}{s(s+d)} \\ \ &=& \frac{a[k]}{s} \end{matrix} \]](http://agnimon.is-programmer.com/user_files/agnimon/epics/67bdc40334ac89c7933926dd25b989af2032435f.png "\[ \begin{matrix} P & = &\sum_{1 \le i \le t, i \ne k} \frac{a[i]}{s} \times \frac{a[k]}{s+d} + \frac{a[k]}{s} \times \frac{a[k]+d}{s+d} \\ \ & = & \frac{s-a[k]}{s} \times \frac{a[k]}{s+d} + \frac{a[k]}{s} \times \frac{a[k]+d}{s+d} \\ \ & = & \frac{sa[k] - (a[k])^2 + (a[k])^2 + a[k]d}{s(s+d)} \\ \ &=& \frac{a[k]}{s} \end{matrix} \]")
这样，其他位置以此类推，于是就可以得出前面的结论。接下来只要写一个高精度就好了，为了不使用高精度除法可以做因子分解，用标准分解式来计算。