火山喷发
火山喷发对所有附近的生物具有毁灭性的影响。在本题中，我们希望用数值来模拟这一过程。
在环境里有 n 个生物分别具有 A1,A2,⋯,An点生命值，一次火山喷发总计 MM 轮，每轮造成 11 点伤害，等概率地分给所有存活的生物，即如果目前有 K 个活着的生物，每个生物受到这点伤害的概率是 1/K。如果一个生物的生命值减为 0，它会立即死去，此后都不会再占用受到伤害的概率。如果没有生物存活，那么将没有生物会受到伤害。
现在你的任务是，给定 n,M 和全部生物的生命值，问每个生物火山喷发后依然存活的概率。
输入格式
第一行两个正整数 n 和 M。
第二行 nn 个正整数 A_1,...,A_n。
输出格式
n 行，第 i 行一个数表示第 i 个生物存活下来的概率，保留小数点后六位。
数据范围与约定
对于 10% 的数据 N=1。
对于 30% 的数据 N=2。
对于全部数据 N≤4,M≤120,Ai≤50。
样例输入1
1 2 1
样例输出1
0.000000
样例输入2
3 15 2 12 2
样例输出2
0.001684 0.996632 0.001684
信息传递
样例输入
3 2 0 1 0 0 1 4 1 0 2 4 2 0
样例输出
0.400000 0.350000 0.250000
任性的国王
样例输入
4 14 2 3 4 3 1 1 1 5 4 7 1 1 2 1 2 3 1 1 3 1 2 4 2 1 5 1 1 4 4 2 1 1 1 3 1 2 3 1 2 4 3 3 100 1 3 4 1 2 4 1 1 4
样例输出
6 8 10 13 17 9 5 10 15 16 20
T1:
普通dp（太暴力啦）
1 #include<cstdio> 2 #include<cstdlib> 3 #include<algorithm> 4 #include<string> 5 #define MAXN 5 6 using namespace std; 7 namespace solve1{ 8 int a[MAXN]; 9 void solve(int n,int m){ 10 scanf("%d",&a[1]); 11 double ans; 12 if(a[1]<=m){ 13 ans=0; 14 printf("%.6f ",ans); 15 } 16 else{ 17 ans=1; 18 printf("%.6f ",ans); 19 } 20 } 21 } 22 namespace solve2{ 23 int a[MAXN]; 24 double f[121][51][51]; 25 void solve(int n,int m){ 26 scanf("%d%d",&a[1],&a[2]); 27 f[0][a[1]][a[2]]=1; 28 for(int k=1;k<=m;k++){ 29 for(int i=0;i<=a[1];i++){ 30 for(int j=0;j<=a[2];j++){ 31 double t; 32 if(j){ 33 t=0.5; 34 } 35 else{ 36 t=1; 37 } 38 if(i<50)f[k][i][j]+=f[k-1][i+1][j]*t; 39 if(i){ 40 t=0.5; 41 } 42 else{ 43 t=1; 44 } 45 if(j<50)f[k][i][j]+=f[k-1][i][j+1]*t; 46 } 47 } 48 } 49 double ans1=0,ans2=0; 50 for(int i=1;i<=a[1];i++){ 51 for(int j=0;j<=a[2];j++){ 52 ans1+=f[m][i][j]; 53 } 54 } 55 for(int i=0;i<=a[1];i++){ 56 for(int j=1;j<=a[2];j++){ 57 ans2+=f[m][i][j]; 58 } 59 } 60 printf("%.6f %.6f ",ans1,ans2); 61 } 62 } 63 namespace solve3{ 64 int a[MAXN]; 65 double f[121][51][51][51]; 66 void solve(int n,int m){ 67 scanf("%d%d%d",&a[1],&a[2],&a[3]); 68 f[0][a[1]][a[2]][a[3]]=1; 69 for(int k=1;k<=m;k++){ 70 for(int i=0;i<=a[1];i++){ 71 for(int j=0;j<=a[2];j++){ 72 for(int p=0;p<=a[3];p++){ 73 double t=1; 74 double cnt=3; 75 if(!j) cnt=cnt-1; 76 if(!p) cnt=cnt-1; 77 t=t/cnt; 78 if(i<50)f[k][i][j][p]+=f[k-1][i+1][j][p]*t; 79 t=1; 80 cnt=3; 81 if(!i) cnt=cnt-1; 82 if(!p) cnt=cnt-1; 83 t=t/cnt; 84 if(j<50)f[k][i][j][p]+=f[k-1][i][j+1][p]*t; 85 t=1; 86 cnt=3; 87 if(!i) cnt=cnt-1; 88 if(!j) cnt=cnt-1; 89 t=t/cnt; 90 if(p<50)f[k][i][j][p]+=f[k-1][i][j][p+1]*t; 91 } 92 } 93 } 94 } 95 double ans1=0,ans2=0,ans3=0; 96 for(int i=1;i<=a[1];i++){ 97 for(int j=0;j<=a[2];j++){ 98 for(int p=0;p<=a[3];p++){ 99 ans1+=f[m][i][j][p]; 100 } 101 } 102 } 103 for(int i=0;i<=a[1];i++){ 104 for(int j=1;j<=a[2];j++){ 105 for(int p=0;p<=a[3];p++){ 106 ans2+=f[m][i][j][p]; 107 } 108 } 109 } 110 for(int i=0;i<=a[1];i++){ 111 for(int j=0;j<=a[2];j++){ 112 for(int p=1;p<=a[3];p++){ 113 ans3+=f[m][i][j][p]; 114 } 115 } 116 } 117 printf("%.6f %.6f %.6f ",ans1,ans2,ans3); 118 } 119 } 120 namespace solve4{ 121 int a[MAXN]; 122 double f[121][51][51][51]; 123 void solve(int n,int m){ 124 scanf("%d%d%d%d",&a[1],&a[2],&a[3],&a[4]); 125 f[0][a[1]][a[2]][a[3]]=1; 126 for(int k=1;k<=m;k++){ 127 for(int i=0;i<=a[1];i++){ 128 for(int j=0;j<=a[2];j++){ 129 for(int p=0;p<=a[3];p++){ 130 int q=a[4]-(k-(a[1]-i+a[2]-j+a[3]-p)); 131 if(q<0) continue; 132 double t=1; 133 double cnt=4; 134 if(!j) cnt=cnt-1; 135 if(!p) cnt=cnt-1; 136 if(!q) cnt=cnt-1; 137 t=t/cnt; 138 if(i<50)f[k][i][j][p]+=f[k-1][i+1][j][p]*t; 139 140 t=1; 141 cnt=4; 142 if(!i) cnt=cnt-1; 143 if(!p) cnt=cnt-1; 144 if(!q) cnt=cnt-1; 145 t=t/cnt; 146 if(j<50)f[k][i][j][p]+=f[k-1][i][j+1][p]*t; 147 148 t=1; 149 cnt=4; 150 if(!i) cnt=cnt-1; 151 if(!j) cnt=cnt-1; 152 if(!q) cnt=cnt-1; 153 t=t/cnt; 154 if(p<50)f[k][i][j][p]+=f[k-1][i][j][p+1]*t; 155 156 t=1; 157 cnt=4; 158 if(!i) cnt=cnt-1; 159 if(!j) cnt=cnt-1; 160 if(!p) cnt=cnt-1; 161 t=t/cnt; 162 f[k][i][j][p]+=f[k-1][i][j][p]*t; 163 } 164 } 165 } 166 } 167 double ans1=0,ans2=0,ans3=0,ans4=0; 168 for(int i=1;i<=a[1];i++){ 169 for(int j=0;j<=a[2];j++){ 170 for(int p=0;p<=a[3];p++){ 171 ans1+=f[m][i][j][p]; 172 } 173 } 174 } 175 for(int i=0;i<=a[1];i++){ 176 for(int j=1;j<=a[2];j++){ 177 for(int p=0;p<=a[3];p++){ 178 ans2+=f[m][i][j][p]; 179 } 180 } 181 } 182 for(int i=0;i<=a[1];i++){ 183 for(int j=0;j<=a[2];j++){ 184 for(int p=1;p<=a[3];p++){ 185 ans3+=f[m][i][j][p]; 186 } 187 } 188 } 189 190 for(int i=0;i<=a[1];i++){ 191 for(int j=0;j<=a[2];j++){ 192 for(int p=0;p<=a[3];p++){ 193 int q=a[4]-(m-(a[1]-i+a[2]-j+a[3]-p)); 194 if(q){ 195 ans4+=f[m][i][j][p]; 196 } 197 } 198 } 199 } 200 printf("%.6f %.6f %.6f %.6f ",ans1,ans2,ans3,ans4); 201 } 202 } 203 int main() 204 { 205 int n,m; 206 scanf("%d%d",&n,&m); 207 if(1==n){ 208 solve1::solve(n,m); 209 } 210 else if(2==n){ 211 solve2::solve(n,m); 212 } 213 else if(3==n){ 214 solve3::solve(n,m); 215 } 216 else{ 217 solve4::solve(n,m); 218 } 219 return 0; 220 }
其实这题可用bfs转移状态，因为按照总伤害，前面的不会对后面的产生影响，所以开始轮到队头元素时，一定是最优的
1 #include<cstdio> 2 #include<cstdlib> 3 #include<algorithm> 4 #include<cstring> 5 #include<queue> 6 #define MAXN 52 7 using namespace std; 8 struct Node{ 9 int a[4]; 10 Node(int p1=0,int p2=0,int p3=0,int p4=0){ 11 a[0]=p1,a[1]=p2,a[2]=p3,a[3]=p4; 12 } 13 }; 14 queue<Node> q; 15 double f[52][52][52][52]; 16 bool b[52][52][52][52]; 17 int n,m; 18 19 int main() 20 { 21 int a[4]={0},c[4]={0}; 22 scanf("%d%d",&n,&m); 23 for(int i=0;i<n;i++){ 24 scanf("%d",&c[i]); 25 } 26 f[c[0]][c[1]][c[2]][c[3]]=1; 27 q.push(Node(c[0],c[1],c[2],c[3])); 28 while(!q.empty()){ 29 memcpy(a,q.front().a,sizeof(a)); 30 int sum=0; 31 for(int i=0;i<4;i++){ 32 sum+=(c[i]-a[i]); 33 } 34 if(sum>m){ 35 break; 36 } 37 q.pop(); 38 int cnt=0; 39 for(int i=0;i<4;i++){ 40 if(a[i]){ 41 cnt++; 42 } 43 } 44 double t=1/(double)cnt; 45 if(a[0]){ 46 f[a[0]-1][a[1]][a[2]][a[3]]+=f[a[0]][a[1]][a[2]][a[3]]*t; 47 if(!b[a[0]-1][a[1]][a[2]][a[3]]){ 48 b[a[0]-1][a[1]][a[2]][a[3]]=1; 49 q.push(Node(a[0]-1,a[1],a[2],a[3])); 50 } 51 } 52 if(a[1]){ 53 f[a[0]][a[1]-1][a[2]][a[3]]+=f[a[0]][a[1]][a[2]][a[3]]*t; 54 if(!b[a[0]][a[1]-1][a[2]][a[3]]){ 55 b[a[0]][a[1]-1][a[2]][a[3]]=1; 56 q.push(Node(a[0],a[1]-1,a[2],a[3])); 57 } 58 } 59 if(a[2]){ 60 f[a[0]][a[1]][a[2]-1][a[3]]+=f[a[0]][a[1]][a[2]][a[3]]*t; 61 if(!b[a[0]][a[1]][a[2]-1][a[3]]){ 62 b[a[0]][a[1]][a[2]-1][a[3]]=1; 63 q.push(Node(a[0],a[1],a[2]-1,a[3])); 64 } 65 } 66 if(a[3]){ 67 f[a[0]][a[1]][a[2]][a[3]-1]+=f[a[0]][a[1]][a[2]][a[3]]*t; 68 if(!b[a[0]][a[1]][a[2]][a[3]-1]){ 69 b[a[0]][a[1]][a[2]][a[3]-1]=1; 70 q.push(Node(a[0],a[1],a[2],a[3]-1)); 71 } 72 } 73 } 74 double ans[4]; 75 if(n>=1){ 76 ans[0]=0; 77 for(int i=1;i<=c[0];i++){ 78 for(int j=0;j<=c[1];j++){ 79 for(int k=0;k<=c[2];k++){ 80 for(int l=0;l<=c[3];l++){ 81 if(c[0]-i+c[1]-j+c[2]-k+c[3]-l==m) 82 ans[0]+=f[i][j][k][l]; 83 } 84 } 85 } 86 } 87 } 88 if(n>=2){ 89 ans[1]=0; 90 for(int i=0;i<=c[0];i++){ 91 for(int j=1;j<=c[1];j++){ 92 for(int k=0;k<=c[2];k++){ 93 for(int l=0;l<=c[3];l++){ 94 if(c[0]-i+c[1]-j+c[2]-k+c[3]-l==m) 95 ans[1]+=f[i][j][k][l]; 96 } 97 } 98 } 99 } 100 } 101 if(n>=3){ 102 ans[2]=0; 103 for(int i=0;i<=c[0];i++){ 104 for(int j=0;j<=c[1];j++){ 105 for(int k=1;k<=c[2];k++){ 106 for(int l=0;l<=c[3];l++){ 107 if(c[0]-i+c[1]-j+c[2]-k+c[3]-l==m) 108 ans[2]+=f[i][j][k][l]; 109 } 110 } 111 } 112 } 113 } 114 if(n>=4){ 115 ans[3]=0; 116 for(int i=0;i<=c[0];i++){ 117 for(int j=0;j<=c[1];j++){ 118 for(int k=0;k<=c[2];k++){ 119 for(int l=1;l<=c[3];l++){ 120 if(c[0]-i+c[1]-j+c[2]-k+c[3]-l==m) 121 ans[3]+=f[i][j][k][l]; 122 } 123 } 124 } 125 } 126 } 127 for(int i=0;i<n;i++){ 128 printf("%.6f ",ans[i]); 129 } 130 return 0; 131 }
T2:
矩阵快速幂
1 #include<cstdio> 2 #include<cstdlib> 3 #include<algorithm> 4 #include<cstring> 5 #define MAXN 205 6 using namespace std; 7 int n,T; 8 int d[MAXN][MAXN]; 9 int sum[MAXN]; 10 struct Mat{ 11 double a[MAXN][MAXN]; 12 Mat operator *= (const Mat &B){ 13 Mat C; 14 for(int i=1;i<=n;i++){ 15 for(int j=1;j<=n;j++){ 16 C.a[i][j]=0; 17 for(int k=1;k<=n;k++){ 18 C.a[i][j]+=a[i][k]*B.a[k][j]; 19 } 20 } 21 } 22 memcpy(a,C.a,sizeof(a)); 23 return *this; 24 } 25 }; 26 void Floyed(){ 27 for(int k=1;k<=n;k++){ 28 for(int i=1;i<=n;i++){ 29 for(int j=1;j<=n;j++){ 30 d[i][j]=min(d[i][j],d[i][k]+d[k][j]); 31 } 32 } 33 } 34 for(int i=1;i<=n;i++){ 35 sum[i]=0; 36 for(int j=1;j<=n;j++){ 37 sum[i]+=d[i][j]; 38 } 39 } 40 } 41 int main() 42 { 43 double a[MAXN]; 44 scanf("%d%d",&n,&T); 45 for(int i=1;i<=n;i++){ 46 scanf("%lf",&a[i]); 47 } 48 for(int i=1;i<=n;i++){ 49 for(int j=1;j<=n;j++){ 50 scanf("%d",&d[i][j]); 51 } 52 } 53 Floyed(); 54 Mat A; 55 for(int i=1;i<=n;i++){ 56 for(int j=1;j<=n;j++){ 57 A.a[i][j]=(double)d[i][j]/(double)sum[j]; 58 } 59 } 60 Mat B; 61 memcpy(B.a,A.a,sizeof(B.a)); 62 T--; 63 while(T){ 64 if(T&1){ 65 B*=A; 66 } 67 A*=A; 68 T>>=1; 69 } 70 for(int i=1;i<=n;i++){ 71 double ans=0; 72 for(int j=1;j<=n;j++){ 73 ans+=a[j]*B.a[i][j]; 74 } 75 printf("%.6f ",ans); 76 } 77 return 0; 78 }
T3:
这题巧妙地把线段树和dp的思想结合在了一起，同时还用到了最小生成树
首先我们用f[k][i][j]表示线段树中节点k所对应区间的值，同时i表示左端的竖边是否选，j表示右端的竖边是否选
那么可以得到方程：
f[k][i][j]=min{ f[k<<1][i][1]+f[k<<1|1][1][j]-cot[mid], f[k<<1][i][1]+f[k<<1|1][0][j]-cot[mid], f[k<<1][i][0]+f[k<<1|1][1][j]-cot[mid] }
其中cot[mid]表示中间的竖边
证明如下：
（1）如果最小生成树中包含竖边mid
那么左区间和右区间内包含mid的最小生成树合并一定可以得到最优解
（2）如果最小生成树不包含竖边mid
就上图来说，如果它位于右区间，那么由于最小生成树一共一定包含9条边，然后左区间包含5-1条边，右区间包含5条边
我们强制左边加上竖边mid，即f[k<<1][i][1]，然后减去cot[mid]，这样左边一定只会包含左区间的最小生成树的边数-1
这样另一条边就让给了右区间，所以直接是f[k<<1|1][0][j]，这样就得到了一定存在一条竖边竖边位于右区间的情况
从效果的角度来看，我们用f[k<<1|1][0][i]的方式使得右区间强制形成一条竖边，然后由于右区间的连通性，
导致左区间处理时相当于已经有了mid这条边，所以左区间是f[k<<1][i][1]，然后减去cot[mid]的代价
左区间的话就是f[k<<1][i][0]+f[k<<1|1][1][j]-cot[mid]
至此，已经囊括了所有的情况
1 #include<cstdio> 2 #include<cstdlib> 3 #include<algorithm> 4 #include<cstring> 5 #define MAXN 100005 6 #define INF 1000000000 7 using namespace std; 8 int a[MAXN]; 9 int f[MAXN*8][2][2]; 10 int n; 11 int up[MAXN],down[MAXN],cot[MAXN]; 12 int read(){ 13 int x=0;char ch=getchar(); 14 while(ch<'0'||ch>'9'){ch=getchar();} 15 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 16 return x; 17 } 18 void pushup(int k,int c){ 19 int lc=(k<<1),rc=(k<<1|1); 20 for(int i=0;i<2;i++){ 21 for(int j=0;j<2;j++){ 22 int t=INF; 23 t=min(t,f[lc][i][1]+f[rc][1][j]-c); 24 t=min(t,f[lc][i][0]+f[rc][1][j]-c); 25 t=min(t,f[lc][i][1]+f[rc][0][j]-c); 26 f[k][i][j]=t; 27 } 28 } 29 } 30 void build(int k,int L,int R){ 31 if(L+1==R){ 32 f[k][0][0]=INF; 33 f[k][0][1]=up[L]+down[L]+cot[L+1]; 34 f[k][1][0]=up[L]+down[L]+cot[L]; 35 f[k][1][1]=min(up[L],down[L])+cot[L]+cot[L+1]; 36 return ; 37 } 38 build(k<<1,L,(L+R)>>1); 39 build(k<<1|1,(L+R)>>1,R); 40 pushup(k,cot[(L+R)>>1]); 41 } 42 void ask(int a,int b,int k,int L,int R,int &q00,int &q01,int &q10,int &q11){ 43 if(a<=L&&R<=b){ 44 q00=f[k][0][0]; 45 q01=f[k][0][1]; 46 q10=f[k][1][0]; 47 q11=f[k][1][1]; 48 return; 49 } 50 else{ 51 int mid=((L+R)>>1); 52 if(b<=mid){ 53 ask(a,b,k<<1,L,mid,q00,q01,q10,q11); 54 return; 55 } 56 if(a>=mid){ 57 ask(a,b,k<<1|1,mid,R,q00,q01,q10,q11); 58 return; 59 } 60 int c=cot[mid]; 61 int p00,p01,p10,p11,l00,l01,l10,l11; 62 ask(a,b,k<<1,L,mid,p00,p01,p10,p11); 63 ask(a,b,k<<1|1,mid,R,l00,l01,l10,l11); 64 65 66 int t=INF; 67 t=min(t,p01+l10-c); 68 t=min(t,p01+l00-c); 69 t=min(t,p00+l10-c); 70 q00=t; 71 72 t=INF; 73 t=min(t,p01+l11-c); 74 t=min(t,p01+l01-c); 75 t=min(t,p00+l11-c); 76 q01=t; 77 78 t=INF; 79 t=min(t,p11+l10-c); 80 t=min(t,p11+l00-c); 81 t=min(t,p10+l10-c); 82 q10=t; 83 84 t=INF; 85 t=min(t,p11+l11-c); 86 t=min(t,p11+l01-c); 87 t=min(t,p10+l11-c); 88 q11=t; 89 } 90 } 91 void update(int a,int k,int L,int R,int x,int K){ 92 if(L+1==R){ 93 if(2==K){ 94 up[a]=x; 95 } 96 else if(3==K){ 97 down[a]=x; 98 } 99 else{ 100 cot[a]=x; 101 } 102 f[k][0][0]=INF; 103 f[k][1][0]=cot[L]+up[L]+down[L]; 104 f[k][0][1]=cot[L+1]+up[L]+down[L]; 105 f[k][1][1]=cot[L]+cot[L+1]+min(up[L],down[L]); 106 return; 107 } 108 int mid=((L+R)>>1); 109 if(mid>=a){ 110 update(a,k<<1,L,mid,x,K); 111 } 112 if(mid<=a){ 113 update(a,k<<1|1,mid,R,x,K); 114 } 115 pushup(k,cot[mid]); 116 } 117 int main() 118 { 119 //freopen("data.in","r",stdin); 120 n=read(); 121 int T=read(); 122 for(int i=1;i<n;i++){ 123 up[i]=read(); 124 } 125 for(int i=1;i<n;i++){ 126 down[i]=read(); 127 } 128 for(int i=1;i<=n;i++){ 129 cot[i]=read(); 130 } 131 build(1,1,n+1); 132 for(int i=1;i<=T;i++){ 133 int K=read(),S=read(),T=read(); 134 if(1==K){ 135 if(S==T){ 136 printf("%d ",cot[S]); 137 } 138 else{ 139 int q00,q01,q10,q11; 140 ask(S,T,1,1,n+1,q00,q01,q10,q11); 141 printf("%d ",min(min(q00,q01),min(q10,q11))); 142 } 143 } 144 else{ 145 update(S,1,1,n+1,T,K); 146 } 147 } 148 return 0; 149 }