自动搬运

查看原文

来自洛谷，原作者为

	Hope2075 时间的流沙，淹没梦境里的夏

搬运于2025-08-24 22:10:33，当前版本为作者最后更新于2019-06-22 20:47:35，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

这是YNOI的题目（

高斯消元

考虑DP

首先，发现只需要记录当前所在位置以及擂主的连局数

设$a_{i,j}$表示当前在第$i$个位置，擂主连局数为$j$时的胜率

这时候需要分类讨论一下

边界情况：已经连胜$m$局

如果擂主是自己，那么胜率为$1$

$a_{1,m}=1$

否则，胜率为$0$

$a_{i,m}=0,2 \leq i \leq n$

情况1：是擂主

两种可能：

$\frac{1}{4}$的概率当擂主，$\frac{3}{4}$的概率到第$n-2$个位置，连局数变为$1$

$a_{1,j}=\frac{1}{4}a_{1,j+1}+\frac{3}{4}a_{n-2,1},1\leq j <m$

情况2：将要进行游戏

这时候需要根据位置讨论每个人胜利后的结果

$a_{2,j}=\frac{1}{4}a_{1,1}+\frac{1}{4}a_{n-2,j+1}+\frac{1}{2}a_{n-1,1},1\leq j <m$

$a_{3,j}=\frac{1}{4}a_{1,1}+\frac{1}{4}a_{n-1,j+1}+\frac{1}{4}a_{n-1,1}+\frac{1}{4}a_{n,1},1\leq j <m$

$a_{4,j}=\frac{1}{4}a_{1,1}+\frac{1}{4}a_{n-2,j+1}+\frac{1}{2}a_{n,1},1\leq j <m$

情况3：在队伍中

这时就看当前擂主是否能胜利即可

$a_{i,j}=\frac{1}{4}a_{i-3,j+1}+\frac{3}{4}a_{i-3,1},5\leq i\leq n,1\leq j <m$

最后答案：

很简单，就是$a_{k,0}$

然而，搞完这些，发现了问题：这些状态间依赖关系有环

也就是：不能直接DP

不过发现状态最多$n(m+1)$个

而$n\leq 10,m\leq 10$

于是就可以高斯消元了

如果不会，就去题库搜板子学习一下

最后复杂度$O(n^3m^3)$

其实有种做法可以做到$O(n^2m+m^3)$

另外，可以发现可能的输入只有$490$种

于是可以考虑打表（滑稽

最后是代码：

高斯消元：

#include<cstdio>
int t,m,n,k;
const int N=128;
const bool DEBUG=0;
double list[N][N];
#define abs(x) ((x)>=0?(x):-(x))
void solve(int c){
	double maxn;int maxp;
	for(int i=0;i<c;i++){
		maxn=0;
		for(int j=i;j<c;j++){
			if(abs(list[j][i])>maxn){
				maxn=abs(list[j][i]);
				maxp=j;
			}
		}
		if(maxn==0)throw 1;
		double t;
		for(int j=0;j<=c;j++){
			t=list[i][j];list[i][j]=list[maxp][j];list[maxp][j]=t;
		}
		t=list[i][i];
		for(int j=0;j<=c;j++){
			list[i][j]/=t;
		}
		for(int j=i+1;j<c;j++){
			t=list[j][i];
			for(int k=0;k<=c;k++){
				list[j][k]-=t*list[i][k];
			}
		}
	}
	for(int i=c-1;i>=0;i--){
		for(int j=i-1;j>=0;j--){
			list[j][c]-=list[j][i]*list[i][c];
			list[j][i]=0;
		}
	}
}
#define gid(x,y) ((m+1)*(x-1)+(y))
#define ls (n*(m+1))
int cnt;
double ans;
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d",&n,&m,&k);
		cnt=0;
		for(int i=0;i<ls;i++){
			for(int j=0;j<=ls;j++){
				list[i][j]=0;
			}
		}
		//1,m
		list[cnt][gid(1,m)]+=1;
		list[cnt][ls]+=1;
		cnt++;
		//i,m
		for(int i=2;i<=n;i++){
			list[cnt][gid(i,m)]+=1;
			list[cnt][ls]+=0;
			cnt++;
		}
		//1,j
		for(int j=0;j<m;j++){
			list[cnt][gid(1,j)]+=1;
			list[cnt][gid(n-2,1)]+=-0.75;
			list[cnt][gid(1,j+1)]+=-0.25;
			list[cnt][ls]+=0;
			cnt++;
		}
		//2,j
		for(int j=0;j<m;j++){
			list[cnt][gid(2,j)]+=1;
			list[cnt][gid(1,1)]+=-0.25;
			list[cnt][gid(n-2,j+1)]+=-0.25;
			list[cnt][gid(n-1,1)]+=-0.5;
			list[cnt][ls]+=0;
			cnt++;
		}
		//3,j
		for(int j=0;j<m;j++){
			list[cnt][gid(3,j)]+=1;
			list[cnt][gid(1,1)]+=-0.25;
			list[cnt][gid(n-1,j+1)]+=-0.25;
			list[cnt][gid(n-1,1)]+=-0.25;
			list[cnt][gid(n,1)]+=-0.25;
			list[cnt][ls]+=0;
			cnt++;
		}
		//4,j
		for(int j=0;j<m;j++){
			list[cnt][gid(4,j)]+=1;
			list[cnt][gid(1,1)]+=-0.25;
			list[cnt][gid(n,j+1)]+=-0.25;
			list[cnt][gid(n,1)]+=-0.5;
			list[cnt][ls]+=0;
			cnt++;
		}
		//i,j
		for(int i=5;i<=n;i++){
			for(int j=0;j<m;j++){
				list[cnt][gid(i,j)]+=1;
				list[cnt][gid(i-3,j+1)]+=-0.25;
				list[cnt][gid(i-3,1)]+=-0.75;
				list[cnt][ls]+=0;
				cnt++;
			}
		}
		solve(ls);
		ans=list[gid(k,0)][ls];
		printf("%.6lf\n",ans);
	}
	
}

打表生成器：

//将标程编译后，重命名为5415.exe
//然后就会自动生成5415_biao.cpp
#include<bits/stdc++.h>
using namespace std;
ofstream fout,gans;ifstream anf;
string res;
int main(){
	gans.open("5415_biao.cpp");
	gans<<"#include<iostream>"<<endl;
	gans<<"using namespace std;"<<endl;
	gans<<"const string ans[11][11][11]={"<<endl;
	gans<<"    ";
	for(int n=0;n<4;n++){
		gans<<"{},";
	}
	gans<<endl;
	for(int n=4;n<=10;n++){
		gans<<"    {"<<endl;
		gans<<"        {},"<<endl;
		for(int m=1;m<=10;m++){
			gans<<"        {\"\",";
			for(int k=1;k<=n;k++){
				fout.open("5415.in");
				fout<<1<<endl;
				fout<<n<<" "<<m<<" "<<k<<endl;
				fout.close();
				system("5415.exe <5415.in >5415.out");
				anf.open("5415.out");
				anf>>res;
				anf.close();
				gans<<"\""<<res<<"\",";
			}
			gans<<"},"<<endl;
		}
		gans<<"    },"<<endl;
	}
	gans<<"};"<<endl;
	gans<<"int t,n,m,k;"<<endl;
	gans<<"int main(){"<<endl;
	gans<<"    cin>>t;"<<endl;
	gans<<"    while(t--){"<<endl;
	gans<<"        cin>>n>>m>>k;"<<endl;
	gans<<"        cout<<ans[n][m][k]<<endl;"<<endl;
	gans<<"    }"<<endl;
	gans<<"}"<<endl;
}