POJ 3071 Football

1 题目大意

给定 $2^n$ 个整数,从 $1$ 到 $2^n$ 编号

给定 $p_{i,j}(1\leq i \leq n, 1 \leq j \leq n)$

定义一次操作为

选中 $2k$ 和 $2k+1$ ( $0 \leq k, k \in Z, 2k+1 \leq n$ )
其中有 $p_{2k,2k+1}$ 的概率选中 $2k$
其中有 $p_{2k+1,2k}$ 的概率选中 $2k+1$

把所有选择的数字组成一个新的数列,大小为 $\frac{n}{2}$

显然最后会只剩 $1$ 个数字

问剩哪个数字的概率最大

Continue reading “POJ 3071 Football”