20联赛集训day8 题解
A我考试的做法是贪心：首先这个题目等价于要求回到根（可以传送），那么如果没有传送操作，答案就是按照 $dfn$ 序走，有了传送只需要在每一步判下是传送回去再走过来优还是直接走优了。注意这样我们要先遍历深度最大值比较小的点，这样就能在最后传送回去，不会浪费。题解的做法是dp。对于这种树上游走的题目我们可以设 $f_{v,0}$ 表示从 $v$ 出发，走完子树，不用回到 $v$ 的代价。$f_{...
A我考试的做法是贪心：首先这个题目等价于要求回到根（可以传送），那么如果没有传送操作，答案就是按照 $dfn$ 序走，有了传送只需要在每一步判下是传送回去再走过来优还是直接走优了。注意这样我们要先遍历深度最大值比较小的点，这样就能在最后传送回去，不会浪费。题解的做法是dp。对于这种树上游走的题目我们可以设 $f_{v,0}$ 表示从 $v$ 出发，走完子树，不用回到 $v$ 的代价。$f_{...
A. Slay the Spire考虑最优的操作是什么：由于强化牌都 $>1$，所以我们肯定是先尽量用强化牌，最后一次用攻击牌。将两种牌分别从大到小排序，可以分别 dp：设 $f_{i,j,0/1}$ 表示考虑前 $i$ 张牌强化牌，选了 $j$ 张，是否选择第 $i$ 张的所有方案的和（每种方案的权值是乘积），$g_{i,j,0/1}$ 考虑攻击牌，这里方案的权值就是和了。转移比较显...
题目太水了，是手速场。A如果 $a,b,c,d,e,f > 0$，那么就是判断转换效率是否 $>1$，也就是 $\frac{bdf}{ace}>1 \Rightarrow bdf > ace$。但是会有 $0$ 的情况，我们发现我们需要特判 $c=0,d \neq 0$ 和 $a=0,b,d \neq 0$ 的情况，剩下的情况都能用上式判断。#include <...
A. 小星星考虑一个大家都会的暴力 dp：设 $f_{v,i,S}$ 表示确定好了 $v$ 的子树内的点映射到集合 $S$ 上，并且 $v$ 对应 $i$ 的方案数。合并子树的时候要保证 $S1$ 和 $S2$ 不交，然后根据图是否有边来判断。复杂度瓶颈显然在每次转移时的枚举子集。我们考虑我们这个第三维的作用是什么：是为了防止多个点映射到同一个点上。我们如果限定这个数的映射只能用 $S$ 然...
A对点权取 $\ln$ 变成加法就行了。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_b...