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

柱爷与远古法阵

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

Submit Status

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

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

法阵很奇怪,是一个长度为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 Input

Sample Output

100 0

33.0476190476

100 2 2 3 99 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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Crossin的编程教室

【每周一坑】田忌赛马

本周的题目取自著名的历史典故:田忌赛马 背景资料如下 田忌经常与齐国众公子赛马,设重金赌注。田忌的上宾孙膑发现他们的马脚力都差不多,马分为上、中、下三等,于是对...

29410
来自专栏swag code

编程:判断一个数是否是奇数?(93.7%的人会写错)

看似是对的,但是每执行四次(四分之一错误)便会有一个错误的结果(用数据说话)。考虑到负奇数的情况,它除以2的结果就不会是1。因此,返回值是false,而这样是不...

874
来自专栏数说戏聊

Python3分析Excel数据

使用xlrd和xlwt扩展包,确定工作簿中工作表的数量、名称和每个工作表中行列的数量。 1excel_introspect_workbook.py

1032
来自专栏人工智能

如何使用tableaux进行逻辑计算

原文作者:Miguel Diaz Kusztrich

7468
来自专栏PPV课数据科学社区

【学习】《R实战》读书笔记(第二章)

“读书会是一种在于拓展视野、宏观思维、知识交流、提升生活的活动。PPV课R语言读书会以“学习、分享、进步”为宗旨,通过成员协作完成R语言专业书籍的精读和分享,达...

3589
来自专栏take time, save time

你所能用到的无损压缩编码(二)

     上个月项目荷兰大佬要检查,搞的我想写的东西不断推迟,现在检查完了,我决定继续把我想写的这整个一个系列写完,上一次写的是最简单的无损编码行程编码,这一次...

3589
来自专栏SimpleAI

令人困惑的TensorFlow【1】

我叫 Jacob,是 Google AI Resident 项目的研究学者。我是在 2017 年夏天加入该项目的,尽管已经拥有了丰富的编程经验,并且对机器学习的...

1062
来自专栏owent

PKU POJ 1724 ROADS 解题报告

题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=1724

642
来自专栏转载gongluck的CSDN博客

FLV文件格式官方规范详解

——如果要学习一个新的知识点,官方手册可能是最快的途径。查看网上其他人的总结也许入门更快,但是要准确,深入,完整,还是要看官方手册。 以下内容来自对官方文档Vi...

4895
来自专栏华章科技

令人困惑的TensorFlow!谷歌大脑工程师帮你解决麻烦

导读:虽然对于大多数人来说 TensorFlow 的开发语言是 Python,但它并不是一个标准的 Python 库。这个神经网络框架通过构建「计算图」来运行,...

1673

扫码关注云+社区

领取腾讯云代金券