模拟赛 24 题解

思维+树状数组+最短路+背包+计数+状压

发现中位数是递减的关系，所以我们可以预处理出所有答案。

按权值降序排序，那么随着 $r$ 的增加，中位数一定后移。

只要 $p$ 前面最小的 $r$ 个的和和后面最大的 $r$ 个的和再加它自身 $\leqslant m$ 就是合法的，否则继续后移。

查询动态区间 $k$ 小和，我采用树状数组+二分，也可以树状数组上倍增，更快。

1.注意 $t=0$ ，加入BIT的时候要整体加。

2.注意可能存在多个 $t$ 相等的情况，二分的时候注意一下。

比较有意思，之前没见过。

一开始的想法是先走 $0$ 再走 $1$ ，但这样在 $dis$ 相同的情况下没法确定大小关系。

正确做法就是把 $dis$ 相同的放在一起跑就好了，同时走 $0$ 再走 $1$ 。

注意 $0$ 的特殊性，一开始要找出所有走 $0$ 边能到达的点，代价一样且都是最小的。

jzp yyds！

正解是容斥，可以去wkp's blog，这里提供一下jzp的背包做法。

考虑只有比某个值小才有贡献，那么我们可以钦定 $k$ 为最大值进行 $dp$ 。

设 $f[i][j]$ 表示考虑了前 $i$ 张牌，点数和为 $j$ 的方案数。

那么考虑新来一张牌的影响：如果点数在 $[1,k]$ 内，则可以直接由前面的状态转移，为 $\sum_{p=1}^kf[i-1][j-p]$ ，可以前缀和优化。

如果 $>k$ ，那么不能拿进来，还是从 $f[i-1][j]$ 转移。

考虑统计答案，同样是钦定一个最大值 $k$ ，枚举前面 $<k$ 的张数 $j$ ，它们的和 $t$ 。

由于要钦定 $<k$ ，所以只能从最大值为 $k-1$ 的 $f$ 转移。

还剩下的空间是 $m-t-k$ ，剩下的牌数是 $n-j$ 张。

我们只要保证剩下的 $n-j$ 张牌的总空间小于 $m-t-k$ 就可以了，没必要占满。

这些方案是 $\sum_{i=1}^{m-t-k}f[n-j][i]$ 。一边 $dp$ 一边统计就好了。

好题。

首先 $m\leqslant10$ ，可以想到状压表示每个点是否被映射。

那么我们枚举 $B$ 的根是什么，这样就形成了 “不同“的树的形态。

我们进行树形dp找每个形态对应的位置。

设 $f[u][S]$ 表示 $u$ 的儿子里面对应 $B$ 的状态为 $S$ ，这里不包含 $u$ 自身。定义每个点的儿子集合为 $son[u]$ ，方便转移。

我们枚举 $u$ 的儿子 $v$ ，再枚举它对应的点 $i$ 。如果 $v$ 想对应 $i$ 的话，那么 $v$ 的儿子应该对应 $i$ 的儿子。

所以这个方案数是 $f[v][son[i]]$ ，与 $f[u][S]$ 相乘累加到 $f[u][S|i]$ 上。

最终状态就是 $u$ 的儿子对应了 $son[rt]$ 。

但是这样肯定会算重，因为再枚举根的时候，并不能保证这 $m$ 种形态都是不同的，也就是说它们一开始就是 "同构" 的。

所以只要看 $B$ 中的自身对应了多少种 $B$ 的形态就好了，最后除掉这部分就是最终方案。