咨询即串数字符合f找到有能够上的状态并再次将该进行编号。答案是慢慢消元啦。

题意:给你同样差数字,问即错数字符合f[n]
= a*f[n-1],f[n] = a*f[n-1]+b*f[n-2],f[n] =
a*f[n-1]+b*f[n-2]+c*f[n-3]眼看几乎独方程中之谁,然后如你吃闹第n+1项,如果符合多独方程,项数小之先(第一单方程优先)。

关押了一如既往龙的高斯消元求期望。

高斯消元的真相就是是模仿解方程

解法:这书我事先拍卖看是否满足f[n] =
a*f[n-1]的款型,如果非满足,则据此高斯消元借发点儿码与老三起的景况的a,b,c,比如第二独方程,f[3]
= a*f[2]+b*f[1],f[4] =
a*f[3]+b*f[2],两独方程两个未知量,用高斯消元解出a,b,这里可能未是整数,我拿他们加了只0.5沾下整,居然对了。后来关押那么集比赛尚未一个口是用之高斯消元,所以未懂得这么是不是正确,有看下端倪的逆评论报自己。

然一般因为好的几率论学的要命不同,所以总了同等仿自己非常之推断。

想像一下,你平常解n元一不行方程组的时段是怎么开的?

代码:

没证实,纯粹是私有想法。

答案是慢慢消元啦~

 

个人感觉,做高斯期望求概率的问题分为以下几步:

于方程组:

1.
 遍历所有出现的状态,找到有能够及的状态并重新将该进行编号,可以在一个num[]。

a11*x1+a12*x2+a13*x3+……+a1n*xn=b1

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 4

int f[14];
typedef double Matrix[N][N];
int x,y,z;

void gauss_elimination(Matrix A,int n)
{
    int i,j,k,r;
    for(i=0;i<n;i++)
    {
        //选一行r并与i行交换
        r = i;
        for(j=i+1;j<n;j++)
            if(fabs(A[j][i]) > fabs(A[r][i]))
                r = j;
        if(r != i)
        {
            for(j=0;j<=n;j++)
                swap(A[r][j],A[i][j]);
        }
        //与第i+1~n行进行消元
        for(k=i+1;k<n;k++)
        {
            double f = A[k][i]/A[i][i];  //为了让A[k][i] = 0,第i行乘以的倍数
            for(j=i;j<=n;j++)
                A[k][j] -= f*A[i][j];
        }
    }
    //回代
    for(i=n-1;i>=0;i--)
    {
        for(j=i+1;j<n;j++)
            A[i][n] -= A[j][n]*A[i][j];
        A[i][n] /= A[i][i];
    }
    x = (int)floor(A[0][n]+0.5);
    y = (int)floor(A[1][n]+0.5);
    if(n == 3)
        z = (int)floor(A[2][n]+0.5);
}

int main()
{
    int t,n,i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        memset(f,0,sizeof(f));
        for(i=1;i<=n;i++)
            scanf("%d",&f[i]);
        int ans = Mod;
        int a1,a2,a3;
        int flag;
        if((f[1] == 0 && f[2] == 0) || f[2]%f[1] == 0)
        {
            if(f[1] == 0 && f[2] == 0)
                a1 = 1;
            else
                a1 = f[2]/f[1];
            flag = 1;
            for(i=3;i<=n;i++)
            {
                if(f[i] != a1*f[i-1])
                    flag = 0;
            }
            if(flag)
                ans = a1*f[n];
        }
        if(ans != Mod)
        {
            printf("%d\n",ans);
            continue;
        }
        Matrix A;
        A[0][0] = A[1][1] = f[2];
        A[0][1] = f[1];
        A[1][0] = f[3];
        A[0][2] = f[3];
        A[1][2] = f[4];
        gauss_elimination(A,2);
        flag = 1;
        for(i=3;i<=n;i++)
        {
            if(f[i] != x*f[i-1]+y*f[i-2])
                flag = 0;
        }
        if(flag)
            ans = x*f[n]+y*f[n-1];
        if(ans != Mod)
        {
            printf("%d\n",ans);
            continue;
        }
        A[0][0] = A[1][1] = A[2][2] = f[3];
        A[0][1] = A[1][2] = f[2];
        A[0][2] = f[1];
        A[1][0] = A[2][1] = f[4];
        A[2][0] = f[5];
        A[0][3] = f[4];
        A[1][3] = f[5];
        A[2][3] = f[6];
        gauss_elimination(A,3);
        //printf("%d %d %d\n",x,y,z);
        ans = x*f[n]+y*f[n-1]+z*f[n-2];
        if(ans != Mod)
            printf("%d\n",ans);
    }
    return 0;
}

2.
判定称(终点)是否让码,意思就是是判能免可知出去(到达),不能到达直接出口不能到达。

a21*x1+a22*x2+a23*x3+……+a2n*xn=b2

View Code

  1.  遍历所有出现的状态,找到有标了号的状态
    E[num[i]],那么每个E[num[i]]都满足:

a31*x1+a32*x2+a33*x3+……+a3n*xn=b3

 

   
 E[num[i]]=(E[num[0]]+step[0])*p[0]+…(E[num[j]]+step[j])*p[j]
   其中E[num[0~j]] 为所有E[num[i]]
能达到的状态,step[0~j]啊所欲的步数(比如在迷宫图中,step[0~j]=1代表走相同步能顶),p[0~j]
代表至这种状态的概率(这个概率不克为零星,要以之前被消除,不然会吃方程无解!!)

……..

    假设可上状态产生cont个,则有的状态就构成了cont*(cont+1)的增广矩阵。

formula1:把x1系数化为1,即方程除以a11

    这时候又使所有的说道(终点)的盼望为0(因为要是手上尽管于极限就无须走了,所以想是0)

接下来对余下的n-1只方程组,用剩下的n-1独方程组去减formula1*ai1【ai1为相应之方程组的首先只系数】

4.
用到高斯消元法求解实数增广矩阵(注意精度每次用绝对值最特别的行去消元),求解出起点编号所对应的解
x[num[start]] 就是咱们如果的答案了。

立即样子剩余的每个方程的x1就给免去哪

注意点:

下一场用formula2去消掉x2,逐步消掉每个x,直至最后一个方程只剩an,算出an,往回迭代,就解出这个方程了~

1.免能够达的状态自然要放弃去,不然会叫方程无解。

如上就是是高斯消元的切实考虑步骤。

2.数记得初始化!

倘若小心的凡,在除一个频繁前若觉察这个数为0,那么无解

3.为减少精度丢少,每次消元的时刻用绝对值最可怜之展开消元。

来道水题练练手= =

4.留意控制状态数,高斯消元是O(n^3)的算法,若状态了多,则尝试换需寻找状态的思路。(例如:要以E(i,j)中i==j的状态,其实可以当是摸索状态E(i-j=0)=E(0)的状态)

1013: [JSOI2008]球形空间发出器sphere

Time Limit: 1 Sec  Memory
Limit: 162 MB
Submit: 5976  Solved: 3115
[Submit][Status][Discuss]

差一点道问题:

Description

  有一个球形空间产生器能够当n维空间中起一个坚的球体。现在,你为累死在了这n维球体中,你只知道球
表面n+1个点之坐标,你需要为极抢之速规定此n维球体的球心坐标,以便为摧毁是球形空间产生器。

hdu 2262 Where is the canteen 

Input

  第一执是一个整数n(1<=N=10)。接下来的n+1行,每行有n个实数,表示球面上一些底n维坐标。每一个实数精确到有些数点
晚6员,且该绝对值都不超过20000。

题意:n*m的迷宫图,”.“是空地、”@“是起点(仅来一个)、”X“是墙、”$“是终端(不止一个),问于起点到终端的步数期望。

Output

  有且只出一行,依次为出球心的n维坐标(n个实数),两独实数之间用一个空格隔开。每个实数精确到有些数点
后3员。数据保证有解。你的答案必须同正式输出一模子一样才能够得分。

其实非常简短就是bfs跑同一整图,然后把点又编号,不克顶的点去丢。

Sample Input

2
0.0 0.0
-1.0 1.0
1.0 0.0

下一场于外侧遍历一遍n*m建立增广矩阵(其实当bfs里面一直打为足以,但是个人不希罕这样),然后判断能否走至巅峰,能饶进展高斯消元。

Sample Output

0.500
1.500

接下来要出要。这题同前面一个题解的公式就非列了。

HINT

  提示:给起片只概念:1、 球心:到球面上无限制一点相差都抵的点。2、
距离:设两只n为空间达到的点A, B

的坐标为(a1, a2, …, an), (b1, b2, …, bn),则AB的相距定义也:dist = sqrt(
(a1-b1)^2 + (a2-b2)^2 + 

… + (an-bn)^2 )

咱们解,圆心到圆上所有点的相距等,这样子我们虽可列出n个方程,两限平方去括号可以窥见xi^2都好大体去,最后只是残留一个如此的方程组:

2*(a(i)1-a(i-1)1)x1+2*(a(i)x-a(i-1)x)xx+……+2*(a(i)n-a(i-1)1n)xn=a(i)1^1+a(i)2^2+……-a(i-1)1^2-a(i-1)2^2-……..

简直就是板题呐

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
using namespace std;
const int maxn=15,INF=2000000000,P=1000000007;

double A[maxn][maxn],num[maxn][maxn],ans[maxn];
int n;

void init(){
    cin>>n;
    for(int i=0;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%lf",&num[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            A[i][j]=2*num[i][j]-2*num[i-1][j];
            A[i][n+1]+=num[i][j]*num[i][j]-num[i-1][j]*num[i-1][j];
        }
}

void gaosi(){
    for(int i=1;i<=n;i++){
        double t=A[i][i];
        if(t==0.0) return;
        for(int j=i;j<=n+1;j++)
            A[i][j]/=t;
        for(int j=i+1;j<=n;j++){
            t=A[j][i];
            for(int k=i;k<=n+1;k++)
                A[j][k]-=A[i][k]*t;
        }
    }
    for(int i=n;i>0;i--){
        for(int j=i+1;j<=n;j++)
            A[i][n+1]-=ans[j]*A[i][j];
        ans[i]=A[i][n+1]/A[i][i];
    }
}

void print(){
    printf("%.3lf",ans[1]);
    for(int i=2;i<=n;i++)
        printf(" %.3lf",ans[i]);
}

int main(){
    init();
    gaosi();
    print();
    return 0;
}
#include"cstdlib"
#include"cstdio"
#include"cstring"
#include"cmath"
#include"queue"
#include"algorithm"
#include"iostream"
#define eps 1e-12
using namespace std;
struct node
{
    int x,y;
};
int f;
int n,m;
int equ,var;
char map[20][20];
double a[300][300];
double x[300];
int num[20][20];
int move[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};
void debug()
{
    for(int i=0;i<equ;i++)
    {
        for(int j=0;j<=var;j++) printf("%3.2f ",a[i][j]);
        puts("");
    }
    puts("");
}
int ok(int x,int y)
{
    if(x<0||y<0||x>=n||y>=m) return 0;
    if(map[x][y]=='#') return 0;
    return 1;
}
int bfs(int xx,int yy)
{
    int i,id=0;
    node cur,next;
    queue<node>q;
    cur.x=xx;
    cur.y=yy;
    q.push(cur);
    while(!q.empty())
    {
        cur=q.front();
        q.pop();
        if(num[cur.x][cur.y]!=-1) continue;
        if(map[cur.x][cur.y]=='$') f=1;
        num[cur.x][cur.y]=id++;
        for(i=0; i<4; i++)
        {
            next.x=cur.x+move[i][0];
            next.y=cur.y+move[i][1];
            if(ok(next.x,next.y)) q.push(next);
        }
    }
    return id;
}
void gauss()
{
    int i,j;
    int row,col;
    for(row=0,col=0;row<equ&&col<var;row++,col++)
    {
        int maxr=row;
        for(i=row+1;i<equ;i++) if(fabs(a[i][col])>fabs(a[maxr][col])) maxr=i; //为找绝对值最大的行
        for(i=0;i<=var;i++) swap(a[row][i],a[maxr][i]);
        for(i=row+1;i<equ;i++)
        {
            if(fabs(a[i][col])>eps)
            {
                double ta=a[i][col]/a[row][col];
                for(j=col;j<=var;j++) a[i][j]-=ta*a[row][j];
             }
        }
    }
    //debug();
    for(i=row-1;i>=0;i--)
    {
        double tep=a[i][var];
        for(j=i+1;j<var;j++)
        {
            if(fabs(a[i][j])<=eps) continue;
            tep-=a[i][j]*x[j];
        }
        x[i]=tep/a[i][i];
    }
}

int main()
{
    while(cin>>n>>m)
    {
        int i,j,k;
        for(i=0; i<n; i++) cin>>map[i];
        for(i=0; i<n; i++)
        {
            for(j=0; j<m; j++)
                if(map[i][j]=='@') break;
            if(j!=m) break;
        }
        memset(num,-1,sizeof(num));
        memset(a,0,sizeof(a));
        f=0; //用f判断能不能到达终点
        var=equ=bfs(i,j);
        if(!f)
        {
            puts("-1");
            continue;
        }
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                if(num[i][j]==-1) continue;
                int tep=num[i][j];
                int cnt=0;
                for(k=0;k<4;k++)
                {
                    int xx=i+move[k][0];
                    int yy=j+move[k][1];
                    if(xx<0||yy<0||xx>=n||yy>=m) continue;
                    if(map[xx][yy]=='#'||num[xx][yy]==-1) continue;
                    cnt++;
                    a[tep][num[xx][yy]]-=1;
                }
                a[tep][tep]=cnt;
                a[tep][var]=cnt;
                if(map[i][j]=='$')
                {
                    memset(a[num[i][j]],0,sizeof(a[num[i][j]]));
                    a[tep][tep]=1;
                }
            }
        }
        //debug();
        gauss();
        printf("%.6f\n",x[0]);
    }
}

zjut  1317 掷飞盘

http://cpp.zjut.edu.cn/ShowProblem.aspx?ShowID=1317

当下书我们以简单个飞盘的去吗状态进行转换。
那么E[n]=E[n+2]/4+E[n-2]/4+E[n]/2+1,化简成:2E[n]-E[n+2]-E[n-2]=4。
先是对此有数单飞盘给定的起始距离n,我们好优先找一下能否到达状态0,如果那个,则直接出口INF。在搜寻的经过中,顺便把还标号为拓展了。为什么这书吗要是还标号为?
因该题中,假设m是偶数,那么对自由的n,n+1和n-1都是不可达的状态。请一定记得,如果方程组中生不可达的接触之语句,就会招致无解的气象!

#include"cstdlib"
#include"cstdio"
#include"cstring"
#include"cmath"
#include"queue"
#include"algorithm"
#include"iostream"
#define exp 1e-12
using namespace std;
int equ,var;
int num[505];
double x[500];
double a[500][500];
int move[4][2]={{1,1},{1,-1},{-1,1},{-1,-1}};
int m,n;
void debug()
{
    for(int i=0; i<equ; i++)
    {
        for(int j=0; j<=var; j++) printf("%3.2f ",a[i][j]);
        puts("");
    }
    puts("");
}

struct node
{
    int x,y;
};
int sign(int x)
{
    return x<0?-x:x;
}
void gauss()
{
    int i,j;
    int row,col;
    for(row=0,col=0; row<equ&&col<var; row++,col++)
    {
        int maxr=row;
        for(i=row+1; i<equ; i++) if(fabs(a[i][col])>fabs(a[maxr][col])) maxr=i;
        for(i=0; i<=var; i++) swap(a[row][i],a[maxr][i]);
        for(i=row+1; i<equ; i++)
        {
            if(fabs(a[i][col])>exp)
            {
                double ta=a[i][col]/a[row][col];
                for(j=col; j<=var; j++) a[i][j]-=a[row][j]*ta;
            }
        }
    }
    for(i=row-1; i>=0; i--)
    {
        double tep=a[i][var];
        for(j=i+1; j<var; j++)
        {
            if(fabs(a[i][j])<=exp) continue;
            tep-=a[i][j]*x[j];
        }
        x[i]=tep/a[i][i];
    }
}

int bfs(int x,int y)   //重标号  标记所有可到达的点
{
    int id=0;
    node cur,next;
    queue<node>q;
    cur.x=x;
    cur.y=y;
    q.push(cur);
    while(!q.empty())
    {
        cur=q.front();
        q.pop();
        if(num[min(sign(cur.x-cur.y),sign(min(cur.x,cur.y)+m-max(cur.x,cur.y)))]!=-1) continue;
        num[min(sign(cur.x-cur.y),sign(min(cur.x,cur.y)+m-max(cur.x,cur.y)))]=id++;
        for(int i=0;i<4;i++)
        {
            next.x=cur.x+move[i][0];
            next.y=cur.y+move[i][1];
            if(next.x==0) next.x=m;
            if(next.y==0) next.y=m;
            if(next.x==m+1) next.x=1;
            if(next.y==m+1) next.y=1;
            q.push(next);
        }
    }
    return id;
}

int main()
{

    while(cin>>m>>n)
    {
        if(n>m/2)             // 注意一下 很关键!
            n=m-n;
        memset(num,-1,sizeof(num));
        memset(a,0,sizeof(a));
        equ=var=bfs(1,1+n);
        if(num[0]==-1)       //到达不了直接输出INF
        {
            puts("INF");
            continue;
        }
        int i;
        for(i=1;i<=m;i++)    //注意一下 i-2和i+2之后的距离变化就好了
        {
            if(num[i]==-1) continue;
            int tep=num[i];
            a[tep][num[sign(i-2)]]-=0.25;
            a[tep][num[min(i+2,m-i-2)]]-=0.25;
            a[tep][tep]-=0.5;
            a[tep][tep]+=1;
            a[tep][var]=1;
        }
        a[num[0]][num[0]]=1;
        gauss();
        printf("%.2f\n",x[num[n]]);
    }
}

hdu 4870 Rating

题意:一个人口注册两个账号,初始rating都是0,他老是将低分的百般号去打比赛,赢了加50分,输了拘留100细分,胜率为p,他会见自及直到一个声泪俱下起1000分开了,问比赛场次的期

思路:f(i, j)表示i >=
j,第一只号i分,第二只号j分时节,达到目标的希望,那么可列出转移为f(i,
j) = p f(i’, j’) + (1 – p)f(i” + j”) + 1
f(i’, j’)对应之凡胜利了加分的状态,f(i”,
j”)对应输的扣分的状态,跑同一全找有可高达状态,利用高斯消元去请解方程组,解出f(0,
0)就是答案。

颇显眼此题的极只有来一个 f(950,1000)

#include"cstdlib"
#include"cstdio"
#include"cstring"
#include"cmath"
#include"queue"
#include"algorithm"
#include"iostream"
#define exp 1e-12
using namespace std;
int equ,var;
double x[320];
double a[300][300];
int num[1200][1200];
struct node
{
    int x,y;
};
void debug()
{
    for(int i=0; i<equ; i++)
    {
        for(int j=0; j<=var; j++) printf("%3.2f ",a[i][j]);
        puts("");
    }
    puts("");
}

void gauss()
{
    int i,j;
    int row,col;
    for(row=0,col=0; row<equ&&col<var; row++,col++)
    {
        int maxr=row;
        for(i=row+1; i<equ; i++) if( fabs(a[i][col])>fabs(a[maxr][col])) maxr=i;
        for(i=0; i<=var; i++) swap(a[row][i],a[maxr][i]);
        for(i=row+1; i<equ; i++)
        {
            if(fabs(a[i][col])>exp)
            {
                double ta=a[i][col]/a[row][col];
                for(j=col; j<=var; j++) a[i][j]-=a[row][j]*ta;
            }
        }
    }
    for(i=row-1; i>=0; i--)
    {
        double tep=a[i][var];
        for(j=i+1; j<var; j++)
        {
            if(fabs(a[i][j])<=exp) continue;
            tep-=a[i][j]*x[j];
        }
        x[i]=tep/a[i][i];
    }
}

int bfs(int x,int y)
{
    queue<node>q;
    node cur,next;
    cur.x=x;
    cur.y=y;
    q.push(cur);
    int id=0;
    while(!q.empty())
    {
        cur=q.front();
        q.pop();
        if(num[cur.x][cur.y]!=-1) continue;
        num[cur.x][cur.y]=id++;
        next.x=cur.x+50;
        next.y=cur.y;
        if(next.x<=950)
        {
            if(next.x>next.y) swap(next.x,next.y);
            q.push(next);
        }
        next.x=max(0,cur.x-100);
        next.y=cur.y;
        if(next.x<=950)
        {
            if(next.x>next.y) swap(next.x,next.y);
            q.push(next);
        }
    }
    return id;
}
int main()
{
    double p;
    memset(num,-1,sizeof(num));
    int cont=bfs(0,0);
    num[950][1000]=cont++;
    equ=var=cont;
    while(cin>>p)
    {
        memset(a,0,sizeof(a));
        double q=1-p;
        int i,j,k;
        for(i=0; i<=950; i+=50)
        {
            for(j=i; j<=950; j+=50)
            {
                if(num[i][j]==-1) continue;
                int tep=num[i][j];
                a[tep][tep]+=1;
                a[tep][var]=1;
                int xx,yy;
                xx=max(0,i-100);
                yy=j;
                if(num[xx][yy]!=-1) a[tep][num[xx][yy]]-=q;
                xx=i+50;
                yy=j;
                if(xx>yy) swap(xx,yy);
                if(num[xx][yy]!=-1) a[tep][num[xx][yy]]-=p;
            }
        }
        memset(a[num[950][1000]],0,sizeof(a[num[950][1000]]));
        a[num[950][1000]][num[950][1000]]=1;
        gauss();
        printf("%.6f\n",x[num[0][0]]);

    }
}

相关文章