NKOJ 4087 （SDOI 2017）硬币游戏（高斯消元）

发表于 |
字数统计: 710字 | 阅读时长 ≈ 4min

P4087【SDOI2017】硬币游戏

问题描述

这里写图片描述

输入格式

这里写图片描述

输出格式

这里写图片描述

样例输入

3 3
THT
TTH
HTT

样例输出

0.3333333333
0.2500000000
0.4166666667

提示

这里写图片描述

这题显然的想到高斯消元，关键是如何建立方程。
不妨设每个人赢的概率分别为$P_1,P_2…P_n$,那么显然我们需要寻找他们之间的关系。
此题的关键在于假设一个状态$N$，他表示所有的没有人获胜的状态。

举个例子来说明，就以样例为例。
这三个人分别猜的是$THT,TTH,HTT$
考虑第一个人胜利的概率，那么如果在$N$后面接上一个$THT$，显然第一个人就胜利了。那么$P_1=\frac {1}{8}P_N$。这表示$N$后面三次扔硬币恰好是$THT$的概率。

但是显然这样不对，因为如果$N$的结尾是在T，那么扔出$TH$时，第二个人就已经赢了，也有可能结尾是$TH$,那么在扔出$T$时，第一个人已经赢了。需要把这些情况发生的概率减掉。

那么应该有$P_1=\frac {1}{8}P_N-\frac{1}{4}P_1-\frac{1}{2}P_2-\frac{1}{4}P_3$
对应的系数就是对应串出现的概率。实际上，当某个串的一个后缀等于当前串的一个前缀时，就会对当前串的概率造成影响。

由于此题数据较弱，可以暴力匹配。当然也可以用KMP。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 1005
using namespace std;
int n,m;
char S[N][N];
double A[N][N],B[N],X[N];
void Gauss(int row,int col)
{
	int i,j,x,y,MR;double t,tmp;
	for(x=1,y=1,MR=1;x<=row&&y<col;x++,y++,MR=x)
	{
		for(i=x+1;i<=row;i++)if(abs(A[i][y])>abs(A[MR][y]))MR=i;
		if(i!=x)for(i=1;i<=col;i++)swap(A[x][i],A[MR][i]);
		if(!A[x][y]){x--;continue;}
		for(i=x+1;i<=row;i++)
		if(A[i][y])
		{
			t=A[i][y]/A[x][y];
			for(j=y;j<=col;j++)A[i][j]-=A[x][j]*t;
		}
	}
	for(i=row;i>=1;i--)
	{
		tmp=A[i][col];
		for(j=i+1;j<col;j++)tmp-=X[j]*A[i][j];
		X[i]=tmp/A[i][i];
	}
	for(i=1;i<=n;i++)printf("%.10lf\n",X[i]);
}
int main()
{
	int i,j,k,p,t;
	scanf("%d%d",&n,&m);B[0]=1.0;
	for(i=1;i<=n;i++)scanf("%s",S[i]),A[i][i]=1.0;
	for(i=1;i<=m;i++)B[i]=B[i-1]/2;
	for(i=1;i<=n;i++)
	{
		A[i][n+1]=-1.0;
		for(j=1;j<=n;j++)
		for(k=1,t=0;k<m;k++,t=0)
		{
			while(k+t<m&&S[j][k+t]==S[i][t])t++;
			if(k+t==m)A[i][j]+=B[k];
		}
	}
	for(i=1;i<=n;i++)A[n+1][i]=1.0;A[n+1][n+2]=1.0;
	Gauss(n+1,n+2);
}