首页 > 代码库 > CDOJ 1330 柱爷与远古法阵【高斯消元，卡精度】

CDOJ 1330 柱爷与远古法阵【高斯消元，卡精度】

2024-10-06 13:48:02   219人阅读

柱爷与远古法阵

Time Limit: 125/125MS (Java/Others)     Memory Limit: 240000/240000KB (Java/Others)
 

众所周知，柱爷的数学非常好，尤其擅长概率论！

某日柱爷在喵哈哈村散步，无意间踏入了远古法阵！

法阵很奇怪，是一个长度为NN的走廊，初始时柱爷在最左边，现在柱爷要到最右边去!

柱爷的行动方式如下:

  • 每个回合柱爷会投一次骰子，根据骰子上的点数每个回合柱爷会投一次骰子，根据骰子上的点数X，柱爷会相应的往右边移动，柱爷会相应的往右边移动X步.步.

  • 骰子的数值是骰子的数值是1到到6，取到每面的概率相同，取到每面的概率相同

  • 在某些位置可能有传送门，一旦柱爷在该回合结束后在这个位置上，会被强制传送到传送门的另外一边在某些位置可能有传送门，一旦柱爷在该回合结束后在这个位置上，会被强制传送到传送门的另外一边

  • 传送门是单向的,同时每个位置不会有超过1个传送门,同时不会存在a→b,b→c这种情况传送门是单向的,同时每个位置不会有超过1个传送门,同时不会存在a→b,b→c这种情况

  • 在任意时刻柱爷都必须保证在法阵内，也就说如果在这一回合结束后柱爷的位置在法阵外，那么这回合柱爷将什么都不做在任意时刻柱爷都必须保证在法阵内，也就说如果在这一回合结束后柱爷的位置在法阵外，那么这回合柱爷将什么都不做

那么请问柱爷到达最右边的期望回合数是多少呢？或者是永远都无法到达？

Input

第一行两个整数NN,MM，分别表示法阵的长度和传送门的数量

接下来MM行，每行两个整数uu,vv，表示从uu到vv有一扇传送门

数据保证:

  • 1≤N≤3001≤N≤300

  • 0≤M≤[N−22]0≤M≤[N−22]

  • 1<u<N，1≤v≤N，u≠v1<u<N，1≤v≤N，u≠v

Output

输出仅一行，表示期望的回合数，如果永远不能到达，输出−1−1.

答案误差在10−610−6以内将被忽略

Sample input and output

Sample InputSample Output
100 0
33.0476190476
100 22 399 100
29.8571428571

Hint

你可能需要一些概率论 & 线性代数的知识才能解决本题！

Source

2016 UESTC Training for Dynamic Programming
题目链接：http://acm.uestc.edu.cn/#/problem/show/1330
分析：第一次学高斯消元，看着卿学姐的视频长大的QAQ，然后，，，，，卿学姐的代码输出结果，，，，一直为0.0000000，我奋力找了5个小时的bug，最后竟然错在输出的精度问题，要取double，我也不知道为啥QAQ！
下面给出AC代码：
  1 #include <bits/stdc++.h>  2 using namespace std;  3 const int maxn=305;  4 const long double eps=1e-14;  5 long double a[maxn][maxn];//构造的高斯消元的矩阵，代表第i个方程式的第j个系数是多少 ，精度要求很高  6 int n,m,f[maxn],x,y;  7 inline int read()//读入优化  8 {  9     int x=0,f=1; 10     char ch=getchar(); 11     while(ch<‘0‘||ch>‘9‘) 12     { 13         if(ch==‘-‘) 14             f=-1; 15         ch=getchar(); 16     } 17     while(ch>=‘0‘&&ch<=‘9‘) 18     { 19         x=x*10+ch-‘0‘; 20         ch=getchar(); 21     } 22     return x*f; 23 } 24 inline void write(int x)//输出优化 25 { 26     if(x<0) 27     { 28         putchar(‘-‘); 29         x=-x; 30     } 31     if(x>9) 32         write(x/10); 33     putchar(x%10+‘0‘); 34 } 35 int main() 36 { 37     n=read(); 38     m=read(); 39     for(int i=1;i<=n;i++) 40         f[i]=i; 41     for(int i=1;i<=m;i++)//如果有传送的话，到哪里 42         f[read()]=read(); 43      //建立增广矩阵的过程 44     for(int i=1;i<n;i++) 45     { 46         a[i][i]=6;//第一个方程 47         if(f[i]!=i) 48             a[i][f[i]]=-6;//如果有传送门 系数直接抵消 x-y=0 相当于 x=y 49         else 50         { 51             a[i][n+1]=6;//方程右边的常数 52             for(int j=1;j<=6;j++) 53             { 54                 if(i+j<=n) 55                     a[i][i+j]-=1.0; 56                 else 57                     a[i][i]-=1.0;//另外一个方程 58             } 59         } 60     } 61     a[n][n]=1.0;//最后的方程 62     a[n][n+1]=0; 63     //高斯消元的过程 64     for(int i=1;i<=n;i++) 65     { 66         int p=i; 67         for(int j=i+1;j<=n;j++) 68         { 69             if(fabs(a[j][i])>eps)//向下查找第j个系数不为0的方程 70                 p=j; 71         } 72         if(fabs(a[p][i])>eps) 73         { 74             for(int j=i;j<=n+1;j++) 75                 swap(a[i][j],a[p][j]);//把方程移上来 76             for(int j=i+1;j<=n;j++)//向下消元 同时除去其他的系数 77             { 78                 if(fabs(a[j][i])>eps) 79                 { 80                     long double k=a[j][i]/a[i][i];//消元 81                     for(int t=i;t<=n+1;t++) 82                         a[j][t]-=a[i][t]*k;//系数相减 83                 } 84             } 85         } 86     } 87     //回代过程 88     for(int i=n;i>=1;i--) 89     { 90         for(int j=i+1;j<=n;j++) 91         { 92             if(fabs(a[i][j])>eps) 93                 a[i][n+1]-=a[i][j]*a[j][n+1];//用已知的解求未知解 94         } 95         if(abs(a[i][i])<=eps&&abs(a[i][n+1])>eps)//如果出现矛盾 96         { 97             printf("-1\n"); 98             return 0; 99         }100         a[i][n+1]/=a[i][i];//求出当前的解101     }102     printf("%.12lf\n",(double)a[1][n+1]);//a[i][n+1]就是第i个未知数的解103     return 0;104 }

 

CDOJ 1330 柱爷与远古法阵【高斯消元，卡精度】


联系
我们