2017ICPC南宁E题题解

题意：2^r个人打比赛，一共比r轮决出冠军，主角的实力排在第k位，并且对于所有人，打败比他弱的人概率是p，打败比他强的人概率是(1-p);主角要尽可能的提高获胜的概率，求这个概率即可

思路：我们想一想就知道，让比我厉害的个人先出局这样一定是获胜概率最大的。所以每一轮让比自己厉害的m个人内斗，自己去选择和比自己弱n个人的pk，最后到m为0或n为0的时候获胜概率就是固定的了。为p^n或者（1-p ) ^ m;把过程记忆化一下即可；

#include<cstdio> #include<string> #include<algorithm> #include<map> using namespace std; typedef unsigned long long ll; ll pw[66]; map<pair<ll,ll>,double>mp; double p; double spow(double a,ll cnt){ double res = 1.0; while(cnt){ res*=a; cnt>>=1; } return res; } double dfs(ll m , ll n){ //printf("%llu %llu\n",m,n); if(mp[make_pair(m,n)] != 0) return mp[make_pair(m,n)];//printf("???\n"); if(m == 0) return mp[make_pair(m,n)] = spow(p,n); if(n == 0) return mp[make_pair(m,n)] = spow(1.0 - p,m); ll newm = (m>>1),newn = (n>>1);///m，n都大于0，且一个奇数，另一个为偶数 if(m%2){///比我强的有m个人，是奇数，有一个人强者必须和弱者打 ///那么最后有两种转移情况 m/2 + 1，n/2-1,以及m/2,n/2 return mp[make_pair(m,n)] = p*(p*dfs(newm + 1,newn-1) + (1.0-p)*dfs(newm,newn)); }else///ż return mp[make_pair(m,n)] = p*dfs(newm,newn); } int main(){ int t; scanf("%d",&t); pw[0] = 1; for(int i = 1 ; i<= 63 ; i++) pw[i] = pw[i-1]*2; //for(int i = 1 ; i <= 63; i++) printf("%llu\n",pw[i]); while(t--){ ll r,k; mp.clear(); scanf("%llu %llu %lf",&r,&k,&p); printf("%.6f\n",dfs(k-1,pw[r]-k)); } return 0; }