总结

初十初十，哎哟哎哟。今天的模拟赛很有难度，也很有技巧性。阿巴阿巴。

题解

来简单说一说吧。今天的题目涉及到一些方面，增长经验。

A. nnntxdy

对方有个随从，生命值分别是。 txdy 的 nnn 发动了一次技能，会连续攻击次，每次在当前生命值为正的随从中随机选择一个，使得它的生命值减一。当一个随从的生命值降到 0 时它就死掉了。

问期望能干掉几个随从，答案模输出。

还是比较容易想到的。就是怎么说，处理一下一个集合几个位置都不会死的摆放方式，然后再一下每个位置死的集合然后转移就可以了。然后前面那一坨直接来会爆炸。使用 meet in the middle 就能减少很多操作数了，然后最后合并，相当于把复杂度给摊开。我这里用的弱智方法使用 ntt，但是能过。

B. 集合

几个数，每个数对应两个权值。然后要选出一组基来，然后权值对应相加，两个的乘积要最小，求这个值。

是很显然的最小乘积生成树的那种题目。正解是维护大小变换，交换相邻两个之后的变化。但显然凸包上的点是很难构造出级别的，然后呢我也不会去证上界到底是啥。

然后讲题人提供了一个很好的链接，这种题：link 。

这是新的知识点，最小乘积生成树！

C. PolarSea 与遗忘的森林

简化版题意：有一棵个点的基环森林，给定某些点到环的距离以及某些点所在连通块中环的长度，让你判断是否存在符合条件的森林，如果存在则给出方案。允许自环。

给的话就是给出每个点的那两个值，然后不知道就是。

很容易想到去先把基环树的结构补完整。就是让环上的点满足倍数的关系，然后最大深度到根路径上满足都有点就行，然后有个二分图，跑一跑。问题在于一些不知道环大小的知道深度的点把它们一起插在哪个环上面呢？我们可以枚举，然后跑就行了。

分析一下复杂度，不同的环有种，然后每次跑是的，总共就是的。容易发现其实连边可以做到，也就是把输入相同的点给归到一起，然后给每条边容量改一下就行了。这样的话复杂度就变成了的了。

但是显然，我写的是的匈牙利（doge）。

原题来自 CF739D Recover a functional graph 。

后记

没什么好记的了。希望明天会更好！拉拉♪(^∇^*)。