自动搬运

查看原文

来自洛谷，原作者为

	LYYY 什么都超菜，这个家伙留下了个寂寞

搬运于2025-08-24 21:24:45，当前版本为作者最后更新于2018-10-12 17:58:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

一开始看到这个题的时候，我觉得是一道挺基础的题，但是后来发现，这道题并不是简单的概率dp，更偏像数论。

---

言归正传：

题意

若掷到1，则队首的人获胜；

若掷到2,4,6，则队首的人出队；

若掷到3,5，则队首的人排到队尾。

---

不妨令f[i][j] (j<=i)表示队中共有i个人，第j个人赢的概率,则有f[1][1]=1；

这样我们会发现f[i][j]可以进行转移：

1. 1/6的概率游戏结束，输;

2. 1/3的概率队首的人会到队尾，转移到f[i][j-1];

3. 1/2的概率队首的人出队，转移到f[i-1][j-1];

但是我们转移的时候会发现各个状态形成的网络并不是一个有向无环图，有可能一直没有人出队，从而一直循环下去，形成环，因此不能直接进行动态规划。

怎么办呢？

我们来推理一下QWQ

一共有4个人，小姜排在第3个，我们只关注ta的胜率，我们要求的是f[4][3];

根据上面的转移，可以知道f[4][3]有两部分组成：

一是1/3的概率转移为f[4][2];二是1/2的概率转移为f[3][2] (另一种是1/6的概率直接输，我们要求的是胜率，因此不考虑这种情况)。

故有

f[4][3] = 1/3 × f[4][2] + 1/2 × f[3][2]

同理，

f[4][2] = 1/3 × f[4][1] + 1/2 × f[3][1]

f[4][4] = 1/3 × f[4][3] + 1/2 × f[3][3]

但是f[4][1]要特殊：

1. 1/6的概率游戏结束，赢;

2. 1/3的概率小姜会到队尾，转移到f[4][4];

3. 1/2的概率小姜出队，输;

故有

f[4][1] = 1/3 × f[4][4] + 1/6

到此，我们就把f[4][x]都用表达式表示出来了；

但是我们要求f[4][3]的值啊，这样求不出来怎么办？

不急，将表达式中的f[3][x]也都表示出来：

f[3][1] = 1/3 × f[3][3] + 1/6

f[3][2] = 1/3 × f[3][1] + 1/2 × f[2][1]

f[3][3] = 1/3 × f[3][2] + 1/2 × f[2][2]

还有f[2][x],也都表示出来

f[2][1] = 1/3 × f[2][2] + 1/6

f[2][2] = 1/3 × f[2][1] + 1/2 × f[1][1]

另，

f[1][1] = 1

现在我们就能看出这不过是多元一次方程组嘛，愉快地解方程就好啦

---

---

接下来说一下如何解方程（dalao请忽略）

萌新福利

解方程

f[1][1] = 1

f[2][1] = 1/3 × f[2][2] + 1/6

f[2][2] = 1/3 × f[2][1] + 1/2 × f[1][1]

f[3][1] = 1/3 × f[3][3] + 1/6

f[3][2] = 1/3 × f[3][1] + 1/2 × f[2][1]

f[3][3] = 1/3 × f[3][2] + 1/2 × f[2][2]

f[4][1] = 1/3 × f[4][4] + 1/6

f[4][2] = 1/3 × f[4][1] + 1/2 × f[3][1]

f[4][3] = 1/3 × f[4][2] + 1/2 × f[3][2]

f[4][4] = 1/3 × f[4][3] + 1/2 × f[3][3]

通过观察，我们发现方程们（皮一下很开心）的两点性质：

1. 所有的等式左边都只有一个未知量且其系数为1；

2. 大部分方程长得都差不多，右边未知量（暂且把第二项看做常量）的系数都是1/3;

这两个性质就是解题的关键所在，所以我们循环用代入消元法就行了

结合代码：

f[1][1]=1;//初始化
	for(int i=2;i<=n;i++)//表示想要求到f[n][x]
	{
		double xishu=(double)1/3,changshu=(double)1/6;
        //由于我们无法用代码直接解方程，所以记录下式子的系数xishu和常数changshu，并对它们进行操作，最后再处理就好了
		for(int j=2;j<=i;j++)
		{
			xishu=xishu/3;
			changshu=changshu/3+f[i-1][j-1]/2;
		}
        //不断将f[i][j-1]代入f[i][j],合并成为新的一个等式；
        //最终使之合并成为一个以f[i][i]为未知数的一元一次方程；
		f[i][i]=changshu/(1-xishu);//解出f[i][i]
		f[i][1]=f[i][i]/3+(double)1/6;//解出f[i][1]
		for(int j=2;j<i;j++)
		{
			f[i][j]=f[i][j-1]/3+f[i-1][j-1]/2;
		}
        //递推求出f[i][x];
	}
    
    //其实应该可以化简出多项式解法，这样就不用循环了；只是本人有点懒，加上数据也不大，所以就用循环求解啦

完整代码如下：

#include<cstdio>
#include<iostream>
using namespace std;

int n,m;
double f[1111][1111];

int main()
{
	scanf("%d%d",&n,&m);
	
	f[1][1]=1;
	for(int i=2;i<=n;i++)
	{
		double xishu=(double)1/3,changshu=(double)1/6;
		for(int j=2;j<=i;j++)
		{
			xishu=xishu/3;
			changshu=changshu/3+f[i-1][j-1]/2;
		}
		f[i][i]=changshu/(1-xishu);
		f[i][1]=f[i][i]/3+(double)1/6;
		for(int j=2;j<i;j++)
		{
			f[i][j]=f[i][j-1]/3+f[i-1][j-1]/2;
		}
	}
	
	printf("%.9lf",f[n][m]);
	return 0;
} 

但是这一份代码只得了70分，后来通过看冷dalao的博客才明白；

题面和数据不匹配~~（有大坑）~~：

题面：

---

若掷到1，则队首的人获胜；

若掷到2,4,6，则队首的人出队；

若掷到3,5，则队首的人排到队尾。

---

数据：

---

若掷到1，则队首的人获胜；

若掷到2,4,6，则队首的人排到队尾；

若掷到3,5，则队首的人出队。

---

所以是数据有问题啦（2018.10.12），简单一改就AC了。

AC代码：

#include<cstdio>
#include<iostream>
using namespace std;

int n,m;
double f[1111][1111];

int main()
{
	scanf("%d%d",&n,&m);
	
	f[1][1]=1;
	for(int i=2;i<=n;i++)
	{
		double xishu=(double)1/2,changshu=(double)1/6;
		for(int j=2;j<=i;j++)
		{
			xishu=xishu/2;
			changshu=changshu/2+f[i-1][j-1]/3;
		}
		f[i][i]=changshu/(1-xishu);
		f[i][1]=f[i][i]/2+(double)1/6;
		for(int j=2;j<i;j++)
		{
			f[i][j]=f[i][j-1]/2+f[i-1][j-1]/3;
		}
	}
	
	printf("%.9lf",f[n][m]);
	return 0;
} 

---

10.15补：

其实这道题也可以用数组降维来优化空间，代码（70分的，100分的改改就行了，逃）：

#include<cstdio>
#include<iostream>
using namespace std;

int n,m;
double f[1111];

int main()
{
	scanf("%d%d",&n,&m);
	
	f[1]=1;
	for(int i=2;i<=n;i++)
	{
		double xishu=(double)1/3,changshu=(double)1/6;
		for(int j=2;j<=i;j++)
		{
			xishu=xishu/3;
			changshu=changshu/3+f[j-1]/2;
		}
		f[i]=changshu/(1-xishu);
		double ans=f[1];//存上一层的值以备计算
		f[1]=f[i]/3+(double)1/6;
		for(int j=2;j<i;j++)
		{
			double lll=f[j];//同理，先存上一层的值
			f[j]=f[j-1]/3+ans/2;
			ans=lll;//更新ans给下一层用
		}
	}
	
	printf("%.9lf",f[m]);
	return 0;
}

感谢冷dalao，小江（姜）。

谢谢阅览！