B. 记忆的轮廓
题目描述
通往贤者之塔的路上，有许多的危机。
我们可以把这个地形看做是一颗树，根节点编号为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的父亲。
50<=p<=n<=700，m<=1500，T<=5。
数据保证每个正确节点均有至少2个儿子，至多3个儿子。
输出格式
T行每行一个实数表示每组数据的答案。请保留四位小数。
样例
样例输入
11 23 7 2 31 4 42 5 53 6 63 7
样例输出
9.0000
orz大佬题解：https://blog.csdn.net/WerKeyTom_FTD/article/details/53026266
我这里只是梳理一下自己的思路。
50算法
对于n==p的情况，就是在每一个点都存档，设d[i]表示节点i的儿子数，对于错误节点i，设g[i]为读档的期望步数，则g[i]=1+∑（1/d[i]*g[j]）.对于正确节点i，设s[i]=∑g[j](j为i的错误儿子)。设f[i]为从i到n的期望步数，f[n]=0,f[i]=1+f[i+1]/d[i]+∑(g[j]+f[i])/d[i],得f[i]=d[i]+f[i+1]+s[i];
1#include<cstdio> 2#include<iostream> 3#include<cmath> 4using namespace std; 5struct edge 6{ 7 int u,v,next; 8 #define u(x) ed[x].u 9 #define v(x) ed[x].v 10 #define n(x) ed[x].next 11}ed[200010]; 12int first[100010],num_e; 13#define f(x) first[x] 14int T; 15int n,m,p; 16double d[100000],g[100000],s[100000],f[100000]; 17 18void dfs(int x,int fa) 19{ 20 //cout<<x<<" "<<fa<<endl; 21 if(x>n)g[x]=1; 22 23 for(int i=f(x);i;i=n(i)) 24 if(v(i)!=fa) 25 d[x]++; 26 27 for(int i=f(x);i;i=n(i)) 28 if(v(i)!=fa) 29 { 30 dfs(v(i),x); 31 if(x>n)g[x]+=1/d[x]*g[v(i)]; 32 else s[x]+=g[v(i)]; 33 } 34 if(x<n) f[x]=d[x]+s[x]+f[x+1]; 35} 36inline void add(int u,int v); 37signed main() 38{ 39 cin>>T; 40 while(T--) 41 { 42 cin>>n>>m>>p; 43 for(int i=1;i<n;i++) 44 add(i,i+1),add(i+1,i); 45 int u,v; 46 for(int i=1;i<=m-n;i++) 47 { 48 cin>>u>>v; 49 add(u,v),add(v,u); 50 } 51 if(n==p) 52 { 53 dfs(1,0); 54 printf("%0.4lf\n",f[1]); 55 } 56 } 57 58} 59inline void add(int u,int v) 60{ 61 ++num_e; 62 u(num_e)=u; 63 v(num_e)=v; 64 n(num_e)=f(u); 65 f(u)=num_e; 66}
View Code
70算法
设a[i][j]为当前存档点为i，从i出发到j的期望步数，用n2的复杂度预处理出a，a[i][i]=0,对于i<j，a[i][j]=a[i][j-1]+1+1/d[j-1]*0+∑(g[k]+a[i][j])/d[j-1];(k为j-1的错误儿子)，得a[i][j]=a[i][j-1]*d[j-1]+d[j-1]+s[j-1];这里理解了好长时间，我本来写的是a[i][j]=a[i][j-1]+1/d[j-1]+∑(g[k]+a[i][j])/d[j-1];因为从j-1无论如何都要再走一步到他的儿子节点，我是忘了这个……设f[i][j]表示当前存档点为i，还剩j次存档机会，到n的期望步数，
那么f[i][j]=min(f[k][j-1]+a[i][k]),i<k<=n;最后答案为f[1][p-1];复杂度O（n2p）;
1#include<cstdio> 2#include<iostream> 3#include<cmath> 4#include<cstring> 5#define ma(x) memset(x,0,sizeof(x)) 6using namespace std; 7struct edge 8{ 9 int u,v,next; 10 #define u(x) ed[x].u 11 #define v(x) ed[x].v 12 #define n(x) ed[x].next 13}ed[20010]; 14int first[1510],num_e; 15#define f(x) first[x] 16int T; 17int n,m,p; 18double d[1510],g[1510],s[1510],f[1510]; 19 20double a[710][710],f2[710][710]; 21 22void dfs(int x,int fa); 23inline void add(int u,int v); 24signed main() 25{ 26 //freopen("5.in","r",stdin); 27 28 cin>>T; 29 while(T--) 30 { 31 num_e=0;ma(d);ma(g);ma(s);ma(f);ma(f2);ma(a);ma(first); 32 cin>>n>>m>>p; 33 for(int i=1;i<n;i++) 34 add(i,i+1),add(i+1,i); 35 int u,v; 36 for(int i=1;i<=m-n;i++) 37 { 38 scanf("%d%d",&u,&v); 39 add(u,v),add(v,u); 40 } 41 dfs(1,0); 42 if(n==p) 43 { 44 printf("%0.4lf\n",f[1]); 45 continue; 46 } 47 for(int i=1;i<=n;i++) 48 for(int j=i+1;j<=n;j++) 49 a[i][j]=a[i][j-1]*d[j-1]+d[j-1]+s[j-1]; 50 for(int i=n-1;i;i--) 51 for(int j=0;j<=p;j++) 52 f2[i][j]=0x7fffffff; 53 for(int i=n;i>=1;i--) 54 for(int j=1;j<p;j++) 55 for(int k=i+1;k<=n;k++) 56 f2[i][j]=min(f2[i][j] , f2[k][j-1]+a[i][k] ); 57 printf("%0.4lf\n",f2[1][p-1]); 58 } 59 60} 61inline void add(int u,int v) 62{ 63 ++num_e; 64 u(num_e)=u; 65 v(num_e)=v; 66 n(num_e)=f(u); 67 f(u)=num_e; 68} 69void dfs(int x,int fa) 70{ 71 if(x>n)g[x]=1; 72 for(int i=f(x);i;i=n(i)) 73 if(v(i)!=fa) 74 { 75 d[x]++; 76 //cout<<i<<" "<<v(i)<<endl; 77 } 78 //cout<<x<<endl; 79 for(int i=f(x);i;i=n(i)) 80 if(v(i)!=fa) 81 { 82 dfs(v(i),x); 83 if(x>n)g[x]+=1/d[x]*g[v(i)]; 84 else s[x]+=g[v(i)]; 85 } 86 if(x<n) f[x]=d[x]+s[x]+f[x+1]; 87}
View Code
70算法+玄学优化AC
题解的分析没有看懂，就是证明了一下a数组不会爆炸的问题，a的增长是非常快的，但答案并不会有那么大，所以可以假定一个常数step，每次转移最多从距离step转移过来，step取40就差不多了，因为a的下界是2^40了，而答案的上界远远没有达到。题解说复杂度是O(np log ans)，没有搞懂，O（40np）更容易理解吧，其实也差不多。
1#include<cstdio> 2#include<iostream> 3#include<cmath> 4#include<cstring> 5#define ma(x) memset(x,0,sizeof(x)) 6using namespace std; 7struct edge 8{ 9 int u,v,next; 10 #define u(x) ed[x].u 11 #define v(x) ed[x].v 12 #define n(x) ed[x].next 13}ed[20010]; 14int first[1510],num_e; 15#define f(x) first[x] 16int T; 17int n,m,p; 18double d[1510],g[1510],s[1510],f[1510]; 19 20double a[710][710],f2[710][710]; 21const int step=40; 22 23void dfs(int x,int fa); 24inline void add(int u,int v); 25signed main() 26{ 27 //freopen("5.in","r",stdin); 28 29 cin>>T; 30 while(T--) 31 { 32 num_e=0;ma(d);ma(g);ma(s);ma(f);ma(f2);ma(a);ma(first); 33 cin>>n>>m>>p; 34 for(int i=1;i<n;i++) 35 add(i,i+1),add(i+1,i); 36 int u,v; 37 for(int i=1;i<=m-n;i++) 38 { 39 scanf("%d%d",&u,&v); 40 add(u,v),add(v,u); 41 } 42 dfs(1,0); 43 if(n==p) 44 { 45 printf("%0.4lf\n",f[1]); 46 continue; 47 } 48 for(int i=1;i<=n;i++) 49 for(int j=i+1;j<=n;j++) 50 a[i][j]=a[i][j-1]*d[j-1]+d[j-1]+s[j-1]; 51 for(int i=n-1;i;i--) 52 for(int j=0;j<=p;j++) 53 f2[i][j]=0x7fffffff; 54 for(int i=n;i>=1;i--) 55 for(int j=1;j<p;j++) 56 for(int k=i+1;k<=min(i+step,n);k++) 57 f2[i][j]=min(f2[i][j] , f2[k][j-1]+a[i][k] ); 58 printf("%0.4lf\n",f2[1][p-1]); 59 } 60 61} 62inline void add(int u,int v) 63{ 64 ++num_e; 65 u(num_e)=u; 66 v(num_e)=v; 67 n(num_e)=f(u); 68 f(u)=num_e; 69} 70void dfs(int x,int fa) 71{ 72 if(x>n)g[x]=1; 73 for(int i=f(x);i;i=n(i)) 74 if(v(i)!=fa) 75 d[x]++; 76 for(int i=f(x);i;i=n(i)) 77 if(v(i)!=fa) 78 { 79 dfs(v(i),x); 80 if(x>n)g[x]+=1/d[x]*g[v(i)]; 81 else s[x]+=g[v(i)]; 82 } 83 if(x<n) f[x]=d[x]+s[x]+f[x+1]; 84}
View Code
100算法
居然是个单队。首先证明a[i][j+1]-a[i][j]>=a[i+1][j+1]-a[i+1][j],把a[i][j+1]展开，得左边=(d[j]-1)*a[i][j]+…,右边=（d[j]-1）*a[i+1][j]+…。得证。则可以用单队优化，复杂度O（np log n）。
另外还有一种做法，目前还没有看懂……