哪些网站是.net开发的/北海seo快速排名

题目：

我是超链接

题意：

有2^n个队，相邻两两打淘汰赛，求最后哪个队夺冠的概率最大

题解：

dp[i][j]表示第i轮比赛，j队赢的几率

dp[i][j]=Σ(dp[i-1][k]*dp[i-1][j]*f[j][k])    上一场j的对手k必须赢了

那谁可以成为j的对手呢？

可以用位运算解决，0^1=1    1^1=0    

如果他们早就应该比过赛了，那么x<<(i-1)==y<<(i-1)

如果太远就配不上对

只有^1是完美的配对才ok

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n,i,j,k;
double f[1024][1024],dp[1024][1024];
int main()
{while (scanf("%d",&n)){if (n==-1) return 0;for (i=1;i<=(1<<n);i++)for (j=1;j<=(1<<n);j++)scanf("%lf",&f[i][j]);memset(dp,0,sizeof(dp));for (i=1;i<=(1<<n);i++) dp[0][i]=1;for (i=1;i<=n;i++)for (j=1;j<=(1<<n);j++)for (k=1;k<=(1<<n);k++) if ((((j-1)>>(i-1))^1)==(((k-1)>>(i-1))))dp[i][j]+=dp[i-1][k]*dp[i-1][j]*f[j][k];double ans=0;int ai=0;for (i=1;i<=(1<<n);i++)if (ans<dp[n][i]){ans=dp[n][i];ai=i;}printf("%d\n",ai);}
}