CF1314B解题报告

# CF1314B解题报告 这是个妙题 刚开始想写贪心然后发现考虑条件太多了。。。然后咕咕咕 ## 题目大意 $2^n$个人比赛，你可以决定每场比赛胜负，每场胜者组比赛胜者进胜者组，败者进败者组；败者组胜者与胜者组败者比赛，胜者继续，否则淘汰。 其中有$k$个人是你喜欢的，你要让有他们的比赛最多，求最多比赛数 ## 题解 发现对于一段区间来说，我们只关心这段区间最后的胜者和败者，于是考虑$DP$，$f[l\dots r][0/1][0/1]$表示$[l\dots r]$中最终胜者是否喜欢，败者是否喜欢下的最多比赛场数。 $$ \begin{aligned} init:f[2k\dots 2k+1][0][0]&=0\\ f[2k\dots 2k+1][0][1]&=1\quad if \ like\ 2k\ or\ 2k+1\\ f[2k\dots 2k+1][1][0]&=1\quad if \ like\ 2k\ or\ 2k+1\\ f[2k\dots 2k+1][1][1]&=2\quad if\ like\ 2k\ ans\ 2k+1\\ \end{aligned} $$ 转移时只需分类讨论考虑情况即可 我们将比赛过程看成一个二叉树，那么我们就可以用二叉树的先序遍历方便地标号比赛，又注意到后两维可以压缩为一个$[0,3]$之间的数字 于是新$DP$转移方程如下 $$ f[i][x|y]=max(f[i][x|y],f[2i][x]+f[2i+1][y]+(x|y)) $$ 最后答案$Ans=max(f[1][1]+1,f[1][2]+1,f[1][3]+1,0)$，其中的$+1$是最后一场比赛的$+1$。 ## Code ```c++ #include <bits/stdc++.h> using namespace std; int main() { int n, k, bit, inf = 1e9; scanf("%d %d", &n, &k); bit = 1 << n - 1; vector<vector<int>> f(bit * 2, {0, -inf, -inf, -inf}); for(int i = 1; i <= k; i++) { int a; scanf("%d", &a); a = bit + (a - 1) / 2; f[a][3] = f[a][1]; f[a][1] = f[a][2] = 1; } for(int i = bit - 1; i > 0; i--) for(int x = 0; x < 4; x++) for(int y = 0; y < 4; y++) f[i][x | y] = max(f[i][x | y], f[2 * i][x] + f[2 * i + 1][y] + (x | y)); printf("%d\n", max({f[1][1], f[1][2], f[1][3], -1}) + 1); return 0; } ```