四次死亡轮回后,昴终于到达了贤者之塔,当代贤者夏乌拉一见到昴就上前抱住了昴“师傅!你终于回来了!你有着和师傅一样的魔女的余香,肯定是师傅”。
众所周知,大贤者是嫉妒魔女沙提拉的老公,400年前与神龙、剑圣一起封印魔女因子暴走的莎缇拉。在魔女茶会的时候,莎缇拉也表示过对昴浓浓的爱意,昴便是被莎缇拉召唤来异世界的。
而贤者之塔中的资料与试炼,似乎都指向同一种可能性……记忆的轮廓,逐渐显形……
通往贤者之塔的路上,有许多的危机。
我们可以把这个地形看做是一颗树,根节点编号为1,目标节点编号为n,其中1-n的简单路径上,编号依次递增,在[1,n]中,一共有n个节点。
我们把编号在[1,n]的叫做正确节点,[n+1,m]的叫做错误节点。一个叶子,如果是正确节点则为正确叶子,否则称为错误叶子。
莎缇拉要帮助昴到达贤者之塔,因此现在面临着存档位置设定的问题。为了让昴成长为英雄,因此一共只有p次存档的机会,其中1和n必须存档。被莎缇拉设置为要存档的节点称为存档位置。
当然不能让昴陷入死循环,所以存档只能在正确节点上进行,而且同一个节点不能存多次档。因为通往贤者之塔的路上有影响的瘴气,因此莎缇拉假设昴每次位于树上一个节点时,都会等概率选择一个儿子走下去。每当走到一个错误叶子时,再走一步就会读档。
具体的,每次昴到达一个新的存档位置,存档点便会更新为这个位置(假如现在的存档点是i,现在走到了一个存档位置j>i,那么存档点便会更新为j)。读档的意思就是回到当前存档点。
初始昴位于1,当昴走到正确叶子n时,便结束了路程。莎缇拉想知道,最优情况下,昴结束路程的期望步数是多少?
输入格式
第一行一个正整数T表示数据组数。
接下来每组数据,首先读入三个正整数n,m,p。
接下来m-n行,描述树上所有的非正确边(正确边即连接两个正确节点的边),用两个正整数j,k表示j与k之间有一条连边,j和k可以均为错误节点,也可以一个为正确节点另一个为错误节点。数据保证j是k的父亲。
输出格式
T行每行一个实数表示每组数据的答案。请保留四位小数。
1
3 7 2
1 4
2 5
3 6
3 7
9.000
数据范围及约定50%,n=p
70%,50<=p<=n<=500
100%,50<=p<=n<=700,m<=1500,T<=5
数据保证每个除了n的正确节点均有至少2个儿子,至多3个儿子。
---------------------------------------------------------------分界线---------------------------------------------------------------
考试T2,调考前刚qj过改过,确实是一道毒瘤题好题,考试时时间不够看都没看考完试才开始做了这题。
理解题理解了一节课
做题先看数据范围,否则凉凉。
我们可以看到有50%的数据是n=p的,对于n=p的情况,我们不难分析出每个点都存档是最优解,这样情况就简单很多。
接下来我们考虑怎么转移。
设个g[i]为对于一个错误节点i还要走多少步会存档。
g[i]=1+∑g[j]/du[i](j是i的儿子)。一遍dfs就可以处理出来g数组。
我们再处理数组sum,sum[i]=∑g[j](j是i的错误儿子)。
设f[i]表示正确节点i走到n的期望步数,显然f[n]=0,我们倒着递推。
f[i]=1+1/d[i]*f[i+1]+1/d[i]*sigma{g[j]+f[i]}[j是i的错误儿子]
移项得f[i]=d[i]+f[i+1]+s[i]。
over,50pts到手。
接下来我们考虑把它优化到70pts。
设dp(i,j)表示存档点在i还有j次存档机会的最优解。
设a(i,j)表示存档点在i,从i走到正确节点j的最少期望步数。
首先我们可以o(n2)把a数组处理出来。
a(i,j)=a(i,j-1)+1+1/du(j-1)×∑(a(i,j)+g(k)){k是j-1的错误儿子}。
整理移项得a(i,j)=du(i,j-1)×a(i,j-1)+sum(j-1)+du(j-1)。
然后我们枚举存档点k,则dp(i,j)可以由dp(k,j-1)和a(i,k)转移。
时间复杂度O(n2p),70pts到手。
最后我们来考虑正解。其实博主并不会正解。
还是放直链吧。%%%出题人。
https://blog.csdn.net/WerKeyTom_FTD/article/details/53026266
出题人给出了三种正解。
由于第二种看起来十分好写比较优秀,博主选择了第二种。
到现在博主还是很mengbi,在这里就不给予讲解了。
如果有时间的话博主也会用其他两种方法A掉这题的。
下面是三个分数段的代码