周末测试-JC的小苹果

    让我们继续JC和DZY的故事。
“你是我的小丫小苹果,怎么爱你都不嫌多!”
“点亮我生命的火,火火火火火!”
话说JC历经艰辛来到了城市B,但是由于他的疏忽DZY偷走了他的小苹果!没有小苹果怎么听歌!他发现邪恶的DZY把他的小苹果藏在了一个迷宫里。JC在经历了之前的战斗后他还剩下hp点血。开始JC在1号点,他的小苹果在N号点。DZY在一些点里放了怪兽。当JC每次遇到位置在i的怪兽时他会损失Ai点血。当JC的血小于等于0时他就会被自动弹出迷宫并且再也无法进入。
但是JC迷路了,他每次只能从当前所在点出发等概率的选择一条道路走。所有道路都是双向的,一共有m条,怪兽无法被杀死。现在JC想知道他找到他的小苹果的概率。

输入格式:
第一行三个整数表示n,m,hp。接下来一行整数,第i个表示jc到第i个点要损失的血量。保证第1个和n个数为0。接下来m行每行两个整数a,b表示ab间有一条无向边。

输出格式:
仅一行,表示JC找到他的小苹果的期望概率,保留八位小数。

样例输入:
3 3 2 0 1 0 1 2 1 3 2 3

样例输出:
0.87500000

数据范围:
对于10%的数据n=5,hp=1
对于30%的数据n<=20,hp<=5
对于60%的数据n<=50,hp<=10000
对于另外10%的数据 所有点权均为正
对于100%的数据 2<=n<=150,hp<=10000,m<=5000,保证图联通,点权非负。

时间限制:
4s

空间限制:
256M

 

囧,一开始不知道点权非负,是后来加上去的,问别人才知道

copy题解(懒得写了,题解讲得比我好多了):

【算法一】
爆搜(虽然我也不知道怎么搜) 期望的分10
【算法二】
把所有点按照hp拆点,然后高斯消元,复杂度O(hp^3*n^3)。期望的分30
【算法三】
我们发现对于hp来说层与层之间是DAG,所以每一层做高斯消元。然后层与层之间递推就可以了。复杂度O(hp*n^3),期望的分60
【算法四】
大致同算法三,但是我们发现每一次高斯消元的矩阵除了常数项都是相同的,所以可以先进行一次高斯消元预处理,其它只要做带入的工作即可。复杂度O(hp*n^2),期望的分100

 

囧,自环环太无语,只能加一条,不能加两次

周末测试-JC的小苹果
  1 const
  2     maxn=152;
  3     maxm=5050;
  4     maxhp=10010;
  5     eps=1e-9;
  6 var
  7     x,y:array[0..maxn,0..maxn]of double;
  8     f:array[0..maxhp,0..maxn]of double;
  9     ff:array[0..maxn]of double;
 10     a,d,first:array[0..maxn]of longint;
 11     last,next:array[0..maxm*2]of longint;
 12     n,m,hp,tot:longint;
 13     ans:double;
 14  
 15 procedure insert(x,y:longint);
 16 begin
 17     if x=n then exit;
 18     inc(tot);
 19     last[tot]:=y;
 20     next[tot]:=first[x];
 21     first[x]:=tot;
 22     inc(d[x]);
 23 end;
 24  
 25 procedure swap(var x,y:double);
 26 var
 27     t:double;
 28 begin
 29     t:=x;x:=y;y:=t;
 30 end;
 31  
 32 procedure work;
 33 var
 34     i,j,k:longint;
 35     s:double;
 36 begin
 37     for i:=1 to n do
 38         begin
 39             j:=first[i];
 40             while j<>0 do
 41                 begin
 42                     if a[last[j]]=0 then x[last[j],i]:=x[last[j],i]-1/d[i];
 43                     j:=next[j];
 44                 end;
 45         end;
 46     for i:=1 to n do x[i,i]:=x[i,i]+1;
 47     for i:=1 to n do y[i,i]:=1;
 48     for i:=1 to n-1 do
 49         begin
 50             for j:=i to n do
 51                 if abs(x[j,i])>eps then break;
 52             for k:=1 to n do swap(x[i,k],x[j,k]);
 53             for k:=1 to n do swap(y[i,k],y[j,k]);
 54             for j:=i+1 to n do
 55                 if abs(x[j,i])>eps then
 56                 begin
 57                     s:=x[j,i]/x[i,i];
 58                     for k:=1 to n do x[j,k]:=x[j,k]-x[i,k]*s;
 59                     for k:=1 to n do y[j,k]:=y[j,k]-y[i,k]*s;
 60                 end;
 61         end;
 62     for i:=n downto 2 do
 63         for j:=1 to i-1 do
 64             if abs(x[j,i])>eps then
 65             begin
 66                 s:=x[j,i]/x[i,i];
 67                 for k:=1 to n do x[j,k]:=x[j,k]-x[i,k]*s;
 68                 for k:=1 to n do y[j,k]:=y[j,k]-y[i,k]*s;
 69             end;
 70     for i:=1 to n do
 71         for j:=1 to n do
 72             y[i,j]:=y[i,j]/x[i,i];
 73 end;
 74  
 75 procedure main;
 76 var
 77     i,j,k,u,v:longint;
 78 begin
 79     read(n,m,hp);
 80     for i:=1 to n do read(a[i]);
 81     for i:=1 to m do
 82         begin
 83             read(u,v);
 84             if u<>v then insert(u,v);
 85             insert(v,u);
 86         end;
 87     work;
 88     f[hp,1]:=1;
 89     for i:=hp downto 1 do
 90         begin
 91             ff:=f[i];
 92             ans:=ans+ff[n];ff[n]:=0;
 93             for j:=1 to n do f[i,j]:=0;
 94             for j:=1 to n do
 95                 for k:=1 to n do
 96                     f[i,j]:=f[i,j]+ff[k]*y[j,k];
 97             ans:=ans+f[i,n];f[i,n]:=0;
 98             for j:=1 to n do
 99                 begin
100                     k:=first[j];
101                     while k<>0 do
102                         begin
103                             if (i-a[last[k]]>0) and (a[last[k]]>0) then
104                             f[i-a[last[k]],last[k]]:=f[i-a[last[k]],last[k]]+f[i,j]/d[j];
105                             k:=next[k];
106                         end;
107                 end;
108         end;
109     writeln(ans:0:8);
110 end;
111  
112 begin
113     main;
114 end. 
View Code

 更新:bzoj上有了题目,但是pascal一直被卡,想了n久,无奈交了std(C++的),突然又想到一个优化,15s+卡过了(好辛酸啊)

周末测试-JC的小苹果,布布扣,bubuko.com

周末测试-JC的小苹果

上一篇:Google I/O 2014? No,Android I/O 2014


下一篇:Eclipse初始化