2020-2021:teams:farmer_john:jjleo:wqs二分
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:jjleo:wqs二分 [2020/06/06 21:19] jjleo [CF739E] |
2020-2021:teams:farmer_john:jjleo:wqs二分 [2020/06/25 23:07] (当前版本) jjleo ↷ 链接因页面移动而自动修正 |
||
|---|---|---|---|
| 行 9: | 行 9: | ||
| =====CF739E===== | =====CF739E===== | ||
| * 题意:抓宝可梦，有$n$个宝可梦和$a$个普通球和$b$个超级球，每种球抓到每个宝可梦的概率不同，对一个宝可梦可以不用球、只用普通球或超级球、两种球都用（抓到只算一个），求抓到宝可梦数量期望的最大值。 | * 题意:抓宝可梦，有$n$个宝可梦和$a$个普通球和$b$个超级球，每种球抓到每个宝可梦的概率不同，对一个宝可梦可以不用球、只用普通球或超级球、两种球都用（抓到只算一个），求抓到宝可梦数量期望的最大值。 | ||
| - | * 题解:可以发现，固定用多少个普通球的情况下，用$x$个超级球能抓到宝可梦数量期望是上凸的，因此可以wqs二分套wqs二分。 | + | * 题解:可以发现，只考虑某一种球的情况下，用$x$个该球能抓到宝可梦数量期望是上凸的，因此可以wqs二分套wqs二分。外层二分普通球的斜率，内层二分超级球的斜率。 |
| =====林克卡特树===== | =====林克卡特树===== | ||
| - | * 题意: | + | * 题意:给出一颗$n$个节点的树，每条边有边权，从中挑选$k+1$个互不相交的链，使得所有被选中的边的权值和最大。 |
| - | * 题解: | + | * 题解:设$f(x)$为选择$x$个互不相交的链的边权最大值，这个函数也是上凸的，太菜了不会证。然后就可以wqs二分转化为树形dp，每条链附加一个$-mid$的权值即可。这个树形dp的过程非常巧妙，通过微调枚举顺序减少了代码的复杂度。设$f[x][i]$表示只考虑点$x$所在的子树，且点$x$的度为$i$时的最大权值，因为只能出现链所以$0 \le i \le 2$，子树中代码如下，注意枚举顺序不能改，因为前两个转移都用到了上次的结果。<code cpp>void dfs(int i, int fa){ |
| + | f[i][0] = Data(0, 0), f[i][1] = f[i][2] = Data(-mid, 1); | ||
| + | for(int j = 0;j < v[i].size();j++){ | ||
| + | int x = v[i][j].first, y = v[i][j].second; | ||
| + | if(x == fa) continue; | ||
| + | dfs(x, i); | ||
| + | Data g = max(f[x][0], max(f[x][1], f[x][2])); | ||
| + | f[i][2] = max(f[i][1] + f[x][1] + Data(y + mid, -1), f[i][2] + g); | ||
| + | f[i][1] = max(f[i][0] + f[x][1] + Data(y, 0), f[i][1] + g); | ||
| + | f[i][0] = max(f[i][0], f[i][0] + g); | ||
| + | } | ||
| + | }</code> | ||
| =====Tree I===== | =====Tree I===== | ||
| 行 21: | 行 32: | ||
| =====CF1279F===== | =====CF1279F===== | ||
| - | * [[Educational Codeforces Round 79 (Rated for Div. 2) Virtual participation|F题]] | + | * [[educational_codeforces_round_79_rated_for_div._2_virtual_participation|F题]] |
2020-2021/teams/farmer_john/jjleo/wqs二分.1591449556.txt.gz · 最后更改: 2020/06/06 21:19 由 jjleo
