<span>省选模拟14 题解</span>

A. 开车

关系似乎和欧拉回路很大。

所以考虑首先通过构造欧拉回路的方式干掉所有的偶度点。

然后发现问题转化为所有奇度点的最小带权匹配。

刚开始的思路一直局限于靠原有的边匹配。后来发现只要是一条路径连接即可。

考虑利用题中的特殊性质,二进制下所有小边的加和不大于大边。所以直接使用最小生成树就好了。

然后考虑树上每条边的贡献,实际上直接作树上合并就可以了。

 

B. 上分

一个新的知识点:杨氏矩阵。

还有一个不会证明但可以性感感性理解的钩子引理。

然后这道题就比较简单了,直接用阶乘的前缀积搞一下就出来了。

 

C. 隔膜

暴力dp并不难想。

正解用一个set来维护单调下降序列即可实现。

但是证明还没看懂,待补。

全部评论

相关推荐

11-15 17:19
湖南大学 Java
成果成果成果果:这是哪个公司的hr,这么离谱吗,我没见过用性别卡技术岗的,身边女性同学拿大厂offer的比比皆是
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务