牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共3篇）

省选模拟10 题解

A. 食物链在拓扑序上dp。 B. 选点游戏要求支持合并两棵树，并同时维护树上最大独立集。考虑特殊情况，每次只加一个标号最大的点，问题是一个简单的动态dp。离线出最终树的形态，考虑加入的一个叶子节点，更新该节点到1号节点的轻链上信息就可以了。其实想到这里，一个动态dp的做...

拓扑排序树链剖分 dp 期望动态dp

2020-01-29

0 365

省选模拟57 题解

A. Max 看到这个数据范围就想一下是不是可以状压。然后发现只有 $m$ 压的下。容易发现题目中的顺序并不关键，其实可以无视掉原有的操作顺序。然后现在给 $1... n$ 每个元素分配一些操作就好了。这样在给第 $i+1$ 个元素分配操作之前，我们只关注已经分配的操作集合、最大的...

树剖扫描线动态dp dp 线段树状压

2020-03-29

0 353

省选模拟69 题解

A. 最小生成树因为最小生成树上一条非树边的权值必须大于两点的路径上的最大值，所以最优的策略肯定是将这棵树弄成一个菊花图。然后考虑把所有的边权按顺序列出来。如果当前还没有超出 $m$ 条边的限制，那么第 $i$ 条边的贡献就是 $(i-1)*w_i$。那考虑一个特殊的情况，如果说...

二项式反演多项式动态dp dp 分治构造题结论题容斥贪心

2020-04-13

0 381