contest5 题解
A. 星际穿越感觉也很神。。先将询问拆成前缀和的形式，我们要对于一组询问 $(l,r)$ 求出 $[l,r]$ 内所有点到 $r$ 的最短距离的和。考虑 $r$ 往左走的最短路径是怎么走的：引理一：往右走之前一定不会往左走反证法。如果先往左走在往右走，那么这个右边的点一定能 cover 到起点，所以可以第一步就先往右走，答案不会变劣。引理二：不会存在连续的两次往右走反证法。如果存在两次连续的...
A. 星际穿越感觉也很神。。先将询问拆成前缀和的形式，我们要对于一组询问 $(l,r)$ 求出 $[l,r]$ 内所有点到 $r$ 的最短距离的和。考虑 $r$ 往左走的最短路径是怎么走的：引理一：往右走之前一定不会往左走反证法。如果先往左走在往右走，那么这个右边的点一定能 cover 到起点，所以可以第一步就先往右走，答案不会变劣。引理二：不会存在连续的两次往右走反证法。如果存在两次连续的...
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$ 然...