• 欢迎光临~

[abc262E] red and blue gragh 题解

开发技术 开发技术 2022-10-24 次浏览

挺喜欢这道题的,但是因为 vp 时过了不能写成做题笔记,所以只能写成题解了。

绿太配这道题了,实现难度极低,但思维难度较大。AT 评了 #1719,倒也算恰当。

题意:给定一张 (n)(m) 边的无向图,每个点染成红或蓝,恰 (k) 点染红,使得两端点不同色的边的数目为偶数,输出方案数。

两端点不同色,两端点同色,这其实和膜二加法很像。或者说,通过膜二加法区分。

如果把蓝色赋值为 (0),红色赋值为 (1),则一条边的边权为两边点权和膜二。因为边权为奇数的边的数目为偶数,边权和为偶数。

现在从点的视角看问题。每个点对边权和贡献点权与度数的乘积。所以只用看度数为奇数的点。

因此,红色的点中,度数为奇数的点为偶数个。换句话说,度数为奇数的点中,红色的点有偶数个。

枚举几个红色奇数度点,组合数直接算,做完了。

作为近三个月前的 abc,这道题居然有翻译和三十余发提交,说明这道题确实是一道令人印象深刻的好题。

这道题蕴含了一些 MO 组合中常用的思想:赋值、算两次。

事实上,这种奇偶问题,赋值法几乎是最通用的方法。

代码不给了,确实很好写。

程序员灯塔
转载请注明原文链接:[abc262E] red and blue gragh 题解
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com