若水而净万物

NOI_2002_Day2_jerrygen_Sol

题目大意是给一棵n个结点的树（n的上限是200000），树的每条边都有一个权值ti,求三个点x,y,z，使满足|XZ|>=|XY|,且使|XY|+|YZ|尽量的大。

这个问题显然不能穷举，一共三个点，那么最多就有C（3，200000）=1333313333400000种状态，会超时。肯定会有O(nlogn)或者是O(n)的算法。考虑到这是棵树，很难找出O(nlogn)的算法，如果是对这棵树进行DFS遍历，那么时间复杂度就是O（n）了。如果时间复杂度是O（n），那么只有贪心或Dp了。。于是，clever的KFC想出了一种Greedy,能过所有的数据。可能这种贪心是对的，只是无法给出准确的证明。。有谁有反例或者证明，欢迎留言：）

贪心如下：

任意找一条树中的最长路，设此最长路的距离为Maxl,最长路的两个端点为n1,n2，设每个结点i（包括n1,n2）到此两个端点的距离分别为dis1[i]、dis2[i],那么所求的答案即为
MAX{min{dis1[i],dis2[i]}}+Maxl(i为树中的每个结点)。。。。。
求最长路，可以进行一次树型动态规划，求每个结点i到n1的距离，可以进行一次DFS,求每个结点i到n2的距离，可以再进行一次DFS。如此时间复杂度为求最长路的时间复杂度（即Dp的复杂度=O(n)）+两次DFS的复杂度(=O(n))=O(n)!!

真是佩服KFC的Imagination和Creation!
其实当我们想不出什么算法的时候，往往可以从数据范围入手寻找可能的算法，并毫不犹豫的拍，就比如这道题，虽然不能给出证明，但毕竟AC了，AC才是王道。。证明可以放在赛后才去考虑。而且有的时候虽然不知道算法正不正确，但还是要思路理清楚，想清楚应该怎么实现，怎么高效的实现，不能应为自以为算法错误而拍出TLE或者是小错误不断的程序，一个错误的算法往往也有可能拍出100+行的程序，这并没有什么奇怪的。。
比如此题，我的代码便有了160多行。

p.s.RS此题代码150行，KFC只有80多行。不过第5个点C++或者FP的go32v2编译会暴栈，只有PASCAL的Win32编译才能AC。。建议C++的同志们用非递归的DFS吧。。。-_-!(此题正确解法见oyy论文)

code: 

.....

 没事写两个并查集的基本操作

1。路径压缩 

function Find(now:longint):longint;
begin
     if now=fa[now] then Find:=now
                    else
             begin
                  Find:=Find(fa[now]);
                  fa[now]:=Find;
             end;
end;

2。启发式合并

procedure Union_Set;
begin
     a_fa:=Find(a);
     b_fa:=Find(b);
     if rank[a_fa]<rank[b_fa] then fa[a_fa]:=b_fa
                              else
          begin
               fa[b_fa]:=a_fa;
               if rank[a_fa]=rank[b_fa] then inc(rank[a_fa]);
          end;
end;

最简单的题目见NOI2002_Day1_Galaxy

题目一：道路重建(USACO_2002_Feb02 Rebuilding Roads)（PKU1947）(程序附后)
题目大意是给一棵树，要去掉最少的边，使一棵子树从中分离出来，且这棵子树要恰有B个节点。

很容易想到此题为树型Dp,用状态[i,j]来表示以节点i为根，得到一棵j个节点的子树至少要去多少条边（请注
意，这里定义的节点i是这棵子树的根,所以一定包含这棵去掉一些边后所得到的j个节点的子树里面）。怎么
转移呢？如果穷举i的子节点保留还是不保留，如果保留，保留多少个。那么这道题目又退化成完全的搜索了。。不难想到,因为节点i的所有子节点是一个线性结构,我们可以双重Dp!!

下面讲一下第二重的Dp:
对于一个节点i,
设它的儿子依次为1,2,....,x.再设一个状态(k,m)表示到节点i的第k个儿子,要保留m个节点,至少要去掉多少条边.这样,对于这个节点i,我们得到它的儿子的序列1,2,....,x.按照1到X的线性顺序进行动态规划.显然,当我们规划到i的儿子k时,有两种选择,一是选这个k,二是不选这个k,
1.如果不选k,那么(k-1,m)+1--->(k,m)(加1是因为不选这个儿子k,所以k和i所连的边应该断开,那么花费就要加1).
2.如果选nk,那么(k-1,j)+[k,m-j]--->(k,m)(注意,中括号所表示的状态时第一重动规所得到的状态,在这里[k,m-j]的意思就是节点k为根，得到一棵(m-j)个节点的子树至少要去多少条边)

那么就很容易转移了:(k,m)=min{(k-1,j)+[k,m-j]{0<=j<=m},(k-1,m)+1},边界自己想吧。。。。。对于这个节点i,算完所有的(1,m),(2,m),...,(x,m)后,[i,m+1]就等于(x,m)(这里+1是因为i这个节点要保留),每次算出(i,B)后,动态更新下ans就行了...Dp时候的顺序可以记忆化搜索,也可以按后序遍历的顺序进行Dp...

尽管讲了这么多,感觉还是有很多细节问题没有讲清楚,这还是要自己思考一下的,这里只是提供了一个大致的
思路而已...(更多时候，这个思路可能只有作者本人才能看懂的--!)。如果谁有更好的方法,欢迎留言:)

题目二： 贪吃的九头龙（NOI2002_DAY1）
题目大意是给一棵树，再给m种点，这些点要覆盖这棵树的所有节点，且每种种类的点至少要用一次，还规定第一种点必须恰好用K次。这棵树的每一条边都有一个权值（每条边的权值可能不同）。对于某条边，若这条边的两个顶点种类相同，则总权值需要加上这条边的权值。问总权值最少是多少。（可能描述的有些模糊，不懂的看一下原题吧。。。）

首先，要明确一点，就是除了m=2的情况外，如果有的边的两个顶点种类相同，那么这种种类一定是第一种！这能保证解是最优的！发现了这个，就意味着问题解决了一半了。接下来就是状态表示了。。
不难想到用[i,j]表示节点i，恰有j个节点被第一种类的点覆盖，总权值最小是多少。不！这还不够！我们必
须增加一维！这一维不是0就是1，0表示节点i被第一种类的点覆盖，1表示节点i被非第一种类的点覆盖（就是被第二或第三...或第m种类的点覆盖啦--！）。即状态是[i，j，0/1]怎么转移？这不禁联想到上面的第一题，如果还是这样进行一重Dp,那也就是退化成单纯的搜索了。。我们必须进行双重Dp!!

下面还是讲一下第二重的Dp:
还是和上题一样，对于一个节点i，它是0或1类型的。这里只举0类型的例子（即不妨假设节点i被第一种类的点覆盖）。我们得到它的儿子的序列1,2,....,x.按照1到X的线性顺序进行动态规划.显然,当我们规划到i的儿子k时,有两种选择,一是这个儿子类型是0,二是这个儿子的类型是1。
转移就不细讲了。因为涉及到很多很多的细节问题，并且不把这些细节问题讲清楚的话，转移就讲不清楚。而讲清楚这些细节问题至少需要1000+个字。所以就不详细展开讲了。。。。-_-！-_-！-_-!。。。。

总结一下。这两道题都是TreeDp,都是需要双重Dp.可以说,它们两的本质是相同的.可是,不同在哪呢?为什么第二题《贪吃的九头龙》要再加一维呢?深入思考,可以看出它们两的转移方式不同,即option不同.对于第一题,转移的时候是对边而言选还是不选的.对于第二题,转移的时候是对点而言选0类型还是选1类型.而状态是记录在点上,而不是记录在边上.所以第一题只要二维而第二题要三维.换句话说,如果我们表示状态的时候把状态记录在边上,那么第二题只要二维而第一题要三维了。上述的一段话正是本文想要说明的关键部分，有些问题虽然形式不同，但本质相同，所以只有把握本质，深入思考，才能豁然开朗。。。。。

刚搞到一个code_to_html的软件Highlight Code Converter，效果感觉不错：）。故把上述第一题的代码附上。

P.S.第二题我写了7KB,很烂,所以不发上来了.

CODE:                                                 

..........

 

三分法单谷求极值[low,up] (此处所求为极小值，如图所示)

设函数为y=f(x)

mid1=low+(up-low)/3

mid2=up-(up-low)/3

若f(mid1)<f(mid2) ,则min ∈ [low,mid2]（即把up更新为mid2）

                         否则min ∈ [mid1,up]（即把low更新为mid1）

B Mountains pku3227

题目意思就是你站在一个点上看一座连续的山，求可看到山的总长度。
我们可以把山的每一条线段分开考虑，分别求出每一条线段能看到的长度，累加起来即可。
精度也没什么要求，时间复杂度也不必考虑。可惜比赛时没看此题。。。

C Gold Transportation pku3228

题目意思就不讲了（虽然本人看成了最小费用最大流），算法就是二分+最大流，二分最长路，如果两点之间的路小于或等于二分的值，则这两点连两条相反的有向 边，且容量为无穷大。在建一个源和一个汇，分别与有黄金的村庄和储存黄金的村庄相连，容量为该村庄的拥有量或储量。求最大流判断即可。

D The Best Travel Design pku3229

考虑到n很小，可以用状态压缩的Dp(即炮兵阵地)。

G Accelerator pku3232

此题又是看错。。郁闷。
只要二分结束时间即可。。。还有要注意用int64。



这四题应该都能做出来。可惜老是理解错题目。。还是要多分析样例，以验证自己的理解是否正确。总得来说这次赛得不够理想，下次再加油吧。

考得不怎么样。才AC4道。。

先讲下AC的题

A String's Puzzle pku3226
题目大意是给一个长度为n的仅a..z组成的字符串，求这个字符串的编号。
比如：n=3时，
ABC 0
ABD 1
…… 　
ZYX 15599

简单题。算法就不细讲了。主要思路就是从前往后扫，边扫边加。
刚比赛的时候看到已有很多人AC了此题，所以先做了这道。。虽然高精度比较恶心，但还是一遍AC。。

D Travel pku3230
题目意思是说n个城市，m天，每天必须呆在一个城市，呆在某个城市可以赚到一些钱，从城市i到城市j需要一

些花费，问最多得多少钱。
看了一下数据范围，n,m<100,晕。简单的Dp。状态表示是opt[m,n]表示第m天在第n个城市最多能赚到的钱。这道题也是一次AC。


F FlashGet pku3231

这题关键要能够弄懂题目意思就不难做出来。题目意思是说有一些文件要下载。
给出每个文件的大小，初始下载速度和最大下载速度，求每个文件什么时候下载完。题目还有一个带宽限制，

即所有正在下载的文件速度总和不能大于带宽。关键要理解他那个HINT。
我就把HINT用人类的语言翻译出来吧。

HINT 提醒

当一个文件下载完成之后，多下来的带宽是这样分发的：
每一个没下载完并且没有达到最大速度的文件分到同样多的带宽（就是说带宽在没下载完并且没有达到最大速度的文件中平均分配），大家就要问了，万一平均分配下来有的文件超过了最大速度怎么办？那就不行，一定要以能分配的最大速度为准。 比如剩下6个带宽，还有2个文件没下完，第一个文件速度是1，可下的最快速度是3，第二个文件速度是1，刻下的最快速度是10。那么一开始只能以第一个文 件为基准，每个文件分配3-1=2个带宽，还剩6-2*2=2个带宽。剩下的2个带宽怎么分呢？继续按照上述规则分，直到不能分为止。这个例子中，这两个 带宽就全给第二个文件了。。


这道题第一遍交没有理解题意。。第二遍居然TLE。。原来是精度不够，循环跳不出来。。加了个特判之后第三遍才勉强AC。。。

H Pushing Boxes pku1475

题目大意就是大家熟知的推箱子游戏，可惜看错题目，耗了不少时间。推箱子是要使人推箱子的步数最少，而不是人走的步数和推箱子的步数的加和。。
但还是那么做，即不断BFS,不断迭代加深，直到不能扩展为止，而且已经扩展过的节点还是要扩展。。据说lrj的某篇论文已经证明这是NP-complete --！。所以队列尽量开大点吧。。所幸测试数据很弱，没有TLE或暴队列。。。

可重复的排列

如果S是一个多重集，那么S的一个r排列是S的r个元素的一个有序排放．如果S的元素总个数是ｎ（包含计算重复），那么S的ｎ排列也将称为S的全排列．例如，如果S＝｛2•a,1•b,3•c｝那么acbc,cbcc都是4排列.
如果S是一个多重集,它有K个不同的类型元素，每一个元素都有无穷重复个数，那么，S的r排列个数为k^r
如果S是一个多重集,它有K个不同的类型元素，各元素分别为n1,n2,…,nk个，那么，S的r排列个数为
            n!/(n1!*n2!*…*nr!)

 可重复的组合

设S是一个具有k种类型元素的多重集，每种元素均具有无限的重复数．则S的r-组合数为c(r+k-1,r).
令S＝｛a,b,c,d｝,S的使得4种元素的每一种都至少出现一次的10－组合的数目是多少？
其实这是方程x1+x2+x3+x4=10的方程的整数解的个数．
答案c(6+4-1,6)=84

好不容易找到一篇GHY的论文（WC2007）,看过之后稍有些明白。
RMQ是给定一列数，动态询问［i,j］区间内的最小（或最大值）。
LCA是给定一棵树，动态询问u和v的最近公共祖先。

解决这两种问题都有个很重要的倍增思想（这个思想在后缀数组方面亦有所应用）。
关键需要记住的是
在LCA预处理的时候
p[i,j] 表示i的2^j 倍祖先
那么就有一个递推式子  p[i,j]=p[p[i,j-1],j-1]

RMQ和LCA可以相互转化。。   所以只要记住一种就行了。。 

RMQ转LCA的时候是生成一棵类似于堆的递归树；LCA转RMQ的时候用到的是深度优先遍历。

主要掌握的不在于算法，而是在于倍增思想

我觉得写的东西不应该是单纯的解题报告，而是应该把自己的思想和思维过程表达出来，流露出来给自己看，给自己不断思考，以此来理清思路，总结经验，不断提升。

这道题最先的想法是搜索，由于每个节点有A或B两种状态，那么总共有2^（2^n）种状态，用这种方法在不及多想的情况下可以过4个点。遇上有关树的题目，首先想到的是树型DP,但是这道题并没有很清晰的表明父节点与子节点的关系，而是告诉了每一对叶子节点的关系。能不能有所转化呢？分析题目中给出的那张表可以很容易的发现每一个叶子节点与其祖先节点的关系，从而把计算每对叶子节点的费用转化成计算各个独立的叶子节点的费用。这个很显而易见的关系是，对于一个非叶子节点i，
<1>若它所管辖的叶子节点中A比B多 或者 它所管辖的叶子节点中A和B一样多，那么对于它所管辖的每一个叶子节点k来说，若这个叶子节点k是A类型的，那么这个叶子节点在这个i节点上所要的费用就是0，若这个叶子节点是B类型的，那么这个叶子节点在这个i节点上所要的费用就是sigma(f[k,j]),其中j节点满足j是叶子节点 并且 j和k的最近公共祖先是i.
<2>若它所管辖的叶子节点中B比A多，那么对于它所管辖的每一个叶子节点k来说，若这个叶子节点k是B类型的，那么这个叶子节点在这个i节点上所要的费用就是0，若这个叶子节点是B类型的，那么这个叶子节点在这个i节点上所要的费用就是sigma(f[k,j]),其中j节点满足j是叶子节点 并且 j和k的最近公共祖先是i.

至此，已将每对叶子节点的费用转化成计算各个独立的叶子节点的费用了^^.
接下来就是想DP的状态表示了。首先肯定有的一维是当前的节点i。但为了从i的左儿子的状态和i的右儿子的状态转移至i的状态，一维显然不行，必须增加维数。可是，还有的维是什么呢？显然有的一维是当前的节点i所管辖的叶子节点中A类型有多少个（既然A类型有多少个知道了，很容易知道B类型有多少个。），难道说这样两维就可以推了吗？试试看，用opt[i,cura]表示以节点i为根的子树，节点i所管辖的叶子节点中A类型有cura个的最小费用。。不对！这不满足最优子结构！（即i的左儿子的状态和i的右儿子的状态不能转移至i的状态！！（可以尝试转移，发现不行）），必须再加一维！这维是什么呢？———用数学归纳法可以很快推出此维即i的祖先中A多还是B多（比如i是第五层，那么i有4个祖先，用"0"来表示A多，用"1"来表示B多,那么这一维状态有0000，0001，0010，……共2^4种），至此，状态表示大功告成，状态转移也就迎刃而解了：
用(i,cura,fathers)表示以节点i为根的子树，节点i所管辖的叶子节点中A类型有cura个，他的祖先的状态为fathers(这个fathers其实是一个01串，可以把它转成十进制数，这样方便。)，叶节点所需要的最小费用。。转移方程就不写了。 还有一点要注意的是实现的时候要用滚动数组，否则也只能对4个点。。。。
给我的两点启示是<1>Dp时不能转移可以考虑增加维数〈2〉Dp时状态表示通常是在当前状态时的最优解，而这个在当前状态时的最优解有两种，一种是推导至当前状态时的最优解，另一种是推导至当前状态时全局的最优解。本题恰恰选择了后者，这一点很值得留心注意。 
 
程序写完。。又长又恶心。。还只能拿80分，FT。

MINCUT—MAXFLOW
建模还是感觉有些困难。一开始以为是最小费用最大流，由于要获益最大，可以把费用全部改成负号，然后就不知道怎么做了。还是看了解题报告，才有所领悟。
个人觉得看到网络流的题目，建模时要往这几个方面思考：
1。点的个数要尽可能少 2。最大流 3。最小割 4。最小费用最大流 5。最小覆盖 6。最大匹配 7。最优匹配
一切包含于简单之中，建模时要尽量往简单的方面去思考，不能太complicated。。
 
编完之后只能对8个点。。。关键还是图存不下。。应该使用前向星的。。