https://codeforces.com/gym/100608
题意:
两个人玩游戏,每个人有一个长为d的b进制数字,两个人轮流摇一个$[0,b-1]$的骰子,并将选出的数字填入自己的d个空位之中
最后数字大的人赢
有两种玩法,第一个是轮流玩,一个是第一个人玩d次之后,第二个人玩
两个人都非常聪明,求第一个人的最大胜率
$d,b<=10,(b+1)^d<=3000$
题解:
很有意思的是,他保证了$(b+1)^d<=3000$,也就是b+1进制数字不会超过3000的大小
我们考虑暴搜+剪枝
首先,可以把b进制变成b+1进制,也就是吧$[0,b-1]$的骰子变成$[1,b]$,这个不影响答案
然后快乐暴搜,
对于第一个人的回合,他摇到的所有数字,每一个数字去尝试填所有空位,取该数字的最大值,也就是对于每种数字取最佳决策
对于第二个人的回合,他摇到的所有数字,每一个数字去尝试填所有空位,取该数字的最小值,也就是对于每种数字取对手的最坏决策
题目里的两个玩法其实大同小异,买一送一,预处理好就行了
#include <bits/stdc++.h> #define endl ' ' #define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define rep(ii,a,b) for(int ii=a;ii<=b;++ii) using namespace std; const int maxn=5e3+7,maxm=2e6+10; int n,m,k,casn; double dp[maxn][maxn],ans1[20][20],ans2[20][20]; int vis[maxn][maxn]; double dfs(int a,int b,int time){ if(vis[a][b]==casn) return dp[a][b]; if(time==0) return 1.0*(a>b); vis[a][b]=casn; dp[a][b]=0; if((casn%2==1&&time%2==0)||(casn%2==0&&time>n)){ rep(i,1,m){ double win=0;int now=a,pw=i; rep(j,1,n){ if(now%(m+1)==0) win=max(win,dfs(a+pw,b,time-1)); now/=(m+1),pw*=(m+1); } dp[a][b]+=win/m; } }else { rep(i,1,m){ double lose=1;int now=b,pw=i; rep(j,1,n){ if(now%(m+1)==0) lose=min(lose,dfs(a,b+pw,time-1)); now/=(m+1),pw*=(m+1); } dp[a][b]+=lose/m; } } return dp[a][b]; } int main() { IO; rep(i,1,10)rep(j,2,10) if(pow(j+1,i)<=3000){ n=i,m=j,casn++; ans1[i][j]=dfs(0,0,i*2); casn++; ans2[i][j]=dfs(0,0,i*2); } cout<<fixed<<setprecision(12); while(cin>>n>>m,n|m) cout<<ans1[n][m]<<' '<<ans2[n][m]<<endl; }