火山喷发
火山喷发对所有附近的生物具有毁灭性的影响。在本题中，我们希望用数值来模拟这一过程。
在环境里有 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（太暴力啦）
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<string>
#define MAXN 5
using namespace std;
namespace solve1{
int a[MAXN];
void solve(int n,int m){
scanf("%d",&a[]);
double ans;
if(a[]<=m){
ans=;
printf("%.6f\n",ans);
}
else{
ans=;
printf("%.6f\n",ans);
}
}
}
namespace solve2{
int a[MAXN];
double f[][][];
void solve(int n,int m){
scanf("%d%d",&a[],&a[]);
f[][a[]][a[]]=;
for(int k=;k<=m;k++){
for(int i=;i<=a[];i++){
for(int j=;j<=a[];j++){
double t;
if(j){
t=0.5;
}
else{
t=;
}
if(i<)f[k][i][j]+=f[k-][i+][j]*t;
if(i){
t=0.5;
}
else{
t=;
}
if(j<)f[k][i][j]+=f[k-][i][j+]*t;
}
}
}
double ans1=,ans2=;
for(int i=;i<=a[];i++){
for(int j=;j<=a[];j++){
ans1+=f[m][i][j];
}
}
for(int i=;i<=a[];i++){
for(int j=;j<=a[];j++){
ans2+=f[m][i][j];
}
}
printf("%.6f\n%.6f\n",ans1,ans2);
}
}
namespace solve3{
int a[MAXN];
double f[][][][];
void solve(int n,int m){
scanf("%d%d%d",&a[],&a[],&a[]);
f[][a[]][a[]][a[]]=;
for(int k=;k<=m;k++){
for(int i=;i<=a[];i++){
for(int j=;j<=a[];j++){
for(int p=;p<=a[];p++){
double t=;
double cnt=;
if(!j) cnt=cnt-;
if(!p) cnt=cnt-;
t=t/cnt;
if(i<)f[k][i][j][p]+=f[k-][i+][j][p]*t;
t=;
cnt=;
if(!i) cnt=cnt-;
if(!p) cnt=cnt-;
t=t/cnt;
if(j<)f[k][i][j][p]+=f[k-][i][j+][p]*t;
t=;
cnt=;
if(!i) cnt=cnt-;
if(!j) cnt=cnt-;
t=t/cnt;
if(p<)f[k][i][j][p]+=f[k-][i][j][p+]*t;
}
}
}
}
double ans1=,ans2=,ans3=;
for(int i=;i<=a[];i++){
for(int j=;j<=a[];j++){
for(int p=;p<=a[];p++){
ans1+=f[m][i][j][p];
}
}
}
for(int i=;i<=a[];i++){
for(int j=;j<=a[];j++){
for(int p=;p<=a[];p++){
ans2+=f[m][i][j][p];
}
}
}
for(int i=;i<=a[];i++){
for(int j=;j<=a[];j++){
for(int p=;p<=a[];p++){
ans3+=f[m][i][j][p];
}
}
}
printf("%.6f\n%.6f\n%.6f\n",ans1,ans2,ans3);
}
}
namespace solve4{
int a[MAXN];
double f[][][][];
void solve(int n,int m){
scanf("%d%d%d%d",&a[],&a[],&a[],&a[]);
f[][a[]][a[]][a[]]=;
for(int k=;k<=m;k++){
for(int i=;i<=a[];i++){
for(int j=;j<=a[];j++){
for(int p=;p<=a[];p++){
int q=a[]-(k-(a[]-i+a[]-j+a[]-p));
if(q<) continue;
double t=;
double cnt=;
if(!j) cnt=cnt-;
if(!p) cnt=cnt-;
if(!q) cnt=cnt-;
t=t/cnt;
if(i<)f[k][i][j][p]+=f[k-][i+][j][p]*t; t=;
cnt=;
if(!i) cnt=cnt-;
if(!p) cnt=cnt-;
if(!q) cnt=cnt-;
t=t/cnt;
if(j<)f[k][i][j][p]+=f[k-][i][j+][p]*t; t=;
cnt=;
if(!i) cnt=cnt-;
if(!j) cnt=cnt-;
if(!q) cnt=cnt-;
t=t/cnt;
if(p<)f[k][i][j][p]+=f[k-][i][j][p+]*t; t=;
cnt=;
if(!i) cnt=cnt-;
if(!j) cnt=cnt-;
if(!p) cnt=cnt-;
t=t/cnt;
f[k][i][j][p]+=f[k-][i][j][p]*t;
}
}
}
}
double ans1=,ans2=,ans3=,ans4=;
for(int i=;i<=a[];i++){
for(int j=;j<=a[];j++){
for(int p=;p<=a[];p++){
ans1+=f[m][i][j][p];
}
}
}
for(int i=;i<=a[];i++){
for(int j=;j<=a[];j++){
for(int p=;p<=a[];p++){
ans2+=f[m][i][j][p];
}
}
}
for(int i=;i<=a[];i++){
for(int j=;j<=a[];j++){
for(int p=;p<=a[];p++){
ans3+=f[m][i][j][p];
}
}
} for(int i=;i<=a[];i++){
for(int j=;j<=a[];j++){
for(int p=;p<=a[];p++){
int q=a[]-(m-(a[]-i+a[]-j+a[]-p));
if(q){
ans4+=f[m][i][j][p];
}
}
}
}
printf("%.6f\n%.6f\n%.6f\n%.6f\n",ans1,ans2,ans3,ans4);
}
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
if(==n){
solve1::solve(n,m);
}
else if(==n){
solve2::solve(n,m);
}
else if(==n){
solve3::solve(n,m);
}
else{
solve4::solve(n,m);
}
return ;
}
Code1-1
其实这题可用bfs转移状态，因为按照总伤害，前面的不会对后面的产生影响，所以开始轮到队头元素时，一定是最优的
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<queue>
#define MAXN 52
using namespace std;
struct Node{
int a[];
Node(int p1=,int p2=,int p3=,int p4=){
a[]=p1,a[]=p2,a[]=p3,a[]=p4;
}
};
queue<Node> q;
double f[][][][];
bool b[][][][];
int n,m; int main()
{
int a[]={},c[]={};
scanf("%d%d",&n,&m);
for(int i=;i<n;i++){
scanf("%d",&c[i]);
}
f[c[]][c[]][c[]][c[]]=;
q.push(Node(c[],c[],c[],c[]));
while(!q.empty()){
memcpy(a,q.front().a,sizeof(a));
int sum=;
for(int i=;i<;i++){
sum+=(c[i]-a[i]);
}
if(sum>m){
break;
}
q.pop();
int cnt=;
for(int i=;i<;i++){
if(a[i]){
cnt++;
}
}
double t=/(double)cnt;
if(a[]){
f[a[]-][a[]][a[]][a[]]+=f[a[]][a[]][a[]][a[]]*t;
if(!b[a[]-][a[]][a[]][a[]]){
b[a[]-][a[]][a[]][a[]]=;
q.push(Node(a[]-,a[],a[],a[]));
}
}
if(a[]){
f[a[]][a[]-][a[]][a[]]+=f[a[]][a[]][a[]][a[]]*t;
if(!b[a[]][a[]-][a[]][a[]]){
b[a[]][a[]-][a[]][a[]]=;
q.push(Node(a[],a[]-,a[],a[]));
}
}
if(a[]){
f[a[]][a[]][a[]-][a[]]+=f[a[]][a[]][a[]][a[]]*t;
if(!b[a[]][a[]][a[]-][a[]]){
b[a[]][a[]][a[]-][a[]]=;
q.push(Node(a[],a[],a[]-,a[]));
}
}
if(a[]){
f[a[]][a[]][a[]][a[]-]+=f[a[]][a[]][a[]][a[]]*t;
if(!b[a[]][a[]][a[]][a[]-]){
b[a[]][a[]][a[]][a[]-]=;
q.push(Node(a[],a[],a[],a[]-));
}
}
}
double ans[];
if(n>=){
ans[]=;
for(int i=;i<=c[];i++){
for(int j=;j<=c[];j++){
for(int k=;k<=c[];k++){
for(int l=;l<=c[];l++){
if(c[]-i+c[]-j+c[]-k+c[]-l==m)
ans[]+=f[i][j][k][l];
}
}
}
}
}
if(n>=){
ans[]=;
for(int i=;i<=c[];i++){
for(int j=;j<=c[];j++){
for(int k=;k<=c[];k++){
for(int l=;l<=c[];l++){
if(c[]-i+c[]-j+c[]-k+c[]-l==m)
ans[]+=f[i][j][k][l];
}
}
}
}
}
if(n>=){
ans[]=;
for(int i=;i<=c[];i++){
for(int j=;j<=c[];j++){
for(int k=;k<=c[];k++){
for(int l=;l<=c[];l++){
if(c[]-i+c[]-j+c[]-k+c[]-l==m)
ans[]+=f[i][j][k][l];
}
}
}
}
}
if(n>=){
ans[]=;
for(int i=;i<=c[];i++){
for(int j=;j<=c[];j++){
for(int k=;k<=c[];k++){
for(int l=;l<=c[];l++){
if(c[]-i+c[]-j+c[]-k+c[]-l==m)
ans[]+=f[i][j][k][l];
}
}
}
}
}
for(int i=;i<n;i++){
printf("%.6f\n",ans[i]);
}
return ;
}
Code1-2
T2:
矩阵快速幂
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define MAXN 205
using namespace std;
int n,T;
int d[MAXN][MAXN];
int sum[MAXN];
struct Mat{
double a[MAXN][MAXN];
Mat operator *= (const Mat &B){
Mat C;
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
C.a[i][j]=;
for(int k=;k<=n;k++){
C.a[i][j]+=a[i][k]*B.a[k][j];
}
}
}
memcpy(a,C.a,sizeof(a));
return *this;
}
};
void Floyed(){
for(int k=;k<=n;k++){
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
}
}
for(int i=;i<=n;i++){
sum[i]=;
for(int j=;j<=n;j++){
sum[i]+=d[i][j];
}
}
}
int main()
{
double a[MAXN];
scanf("%d%d",&n,&T);
for(int i=;i<=n;i++){
scanf("%lf",&a[i]);
}
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
scanf("%d",&d[i][j]);
}
}
Floyed();
Mat A;
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
A.a[i][j]=(double)d[i][j]/(double)sum[j];
}
}
Mat B;
memcpy(B.a,A.a,sizeof(B.a));
T--;
while(T){
if(T&){
B*=A;
}
A*=A;
T>>=;
}
for(int i=;i<=n;i++){
double ans=;
for(int j=;j<=n;j++){
ans+=a[j]*B.a[i][j];
}
printf("%.6f\n",ans);
}
return ;
}
Code2
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]
至此，已经囊括了所有的情况
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define MAXN 100005
#define INF 1000000000
using namespace std;
int a[MAXN];
int f[MAXN*][][];
int n;
int up[MAXN],down[MAXN],cot[MAXN];
int read(){
int x=;char ch=getchar();
while(ch<''||ch>''){ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x;
}
void pushup(int k,int c){
int lc=(k<<),rc=(k<<|);
for(int i=;i<;i++){
for(int j=;j<;j++){
int t=INF;
t=min(t,f[lc][i][]+f[rc][][j]-c);
t=min(t,f[lc][i][]+f[rc][][j]-c);
t=min(t,f[lc][i][]+f[rc][][j]-c);
f[k][i][j]=t;
}
}
}
void build(int k,int L,int R){
if(L+==R){
f[k][][]=INF;
f[k][][]=up[L]+down[L]+cot[L+];
f[k][][]=up[L]+down[L]+cot[L];
f[k][][]=min(up[L],down[L])+cot[L]+cot[L+];
return ;
}
build(k<<,L,(L+R)>>);
build(k<<|,(L+R)>>,R);
pushup(k,cot[(L+R)>>]);
}
void ask(int a,int b,int k,int L,int R,int &q00,int &q01,int &q10,int &q11){
if(a<=L&&R<=b){
q00=f[k][][];
q01=f[k][][];
q10=f[k][][];
q11=f[k][][];
return;
}
else{
int mid=((L+R)>>);
if(b<=mid){
ask(a,b,k<<,L,mid,q00,q01,q10,q11);
return;
}
if(a>=mid){
ask(a,b,k<<|,mid,R,q00,q01,q10,q11);
return;
}
int c=cot[mid];
int p00,p01,p10,p11,l00,l01,l10,l11;
ask(a,b,k<<,L,mid,p00,p01,p10,p11);
ask(a,b,k<<|,mid,R,l00,l01,l10,l11); int t=INF;
t=min(t,p01+l10-c);
t=min(t,p01+l00-c);
t=min(t,p00+l10-c);
q00=t; t=INF;
t=min(t,p01+l11-c);
t=min(t,p01+l01-c);
t=min(t,p00+l11-c);
q01=t; t=INF;
t=min(t,p11+l10-c);
t=min(t,p11+l00-c);
t=min(t,p10+l10-c);
q10=t; t=INF;
t=min(t,p11+l11-c);
t=min(t,p11+l01-c);
t=min(t,p10+l11-c);
q11=t;
}
}
void update(int a,int k,int L,int R,int x,int K){
if(L+==R){
if(==K){
up[a]=x;
}
else if(==K){
down[a]=x;
}
else{
cot[a]=x;
}
f[k][][]=INF;
f[k][][]=cot[L]+up[L]+down[L];
f[k][][]=cot[L+]+up[L]+down[L];
f[k][][]=cot[L]+cot[L+]+min(up[L],down[L]);
return;
}
int mid=((L+R)>>);
if(mid>=a){
update(a,k<<,L,mid,x,K);
}
if(mid<=a){
update(a,k<<|,mid,R,x,K);
}
pushup(k,cot[mid]);
}
int main()
{
//freopen("data.in","r",stdin);
n=read();
int T=read();
for(int i=;i<n;i++){
up[i]=read();
}
for(int i=;i<n;i++){
down[i]=read();
}
for(int i=;i<=n;i++){
cot[i]=read();
}
build(,,n+);
for(int i=;i<=T;i++){
int K=read(),S=read(),T=read();
if(==K){
if(S==T){
printf("%d\n",cot[S]);
}
else{
int q00,q01,q10,q11;
ask(S,T,,,n+,q00,q01,q10,q11);
printf("%d\n",min(min(q00,q01),min(q10,q11)));
}
}
else{
update(S,,,n+,T,K);
}
}
return ;
}
Code3