ARC205_B Triangle Toggle题解
ARC205_B Triangle Toggle问题陈述
有一个完整的图，图中有 \(n\) 个顶点，编号为 \(1\) 至 \(n\) 。每条边的颜色为黑色或白色。对于 \(i=1,2,\ldots,m\) ，连接顶点 \(U_i\) 和 \(V_i\) 的边被涂成黑色，其他所有的边都被涂成白色。
您可以执行以下操作零次或多次。
[*]选择满足 \(1\leq a\leq b\leq c\leq N\) 的整数 \((a,b,c)\) ，并将以下三条边分别重新涂色：白色涂成黑色，黑色涂成白色。
[*]连接顶点 \(a\) 和 \(b\) 的边
[*]连接顶点 \(b\) 和 \(c\) 的边
[*]连接顶点 \(a\) 和 \(c\) 的边
请找出在进行适当操作时最多可以被涂成黑色的边的数量。
[!NOTE]
[*]\(3\leq n\leq 2\times 10^5\)
[*]\(0\leq m\leq 2\times 10^5\)
[*]\(1\leq U_i < V_i\leq N\)
[*]\((U_i , V_i) \neq (U_j , V_j)\) \((i \neq j)\)
思路
首先考虑 \(m=0\) 时的最优解
1. \(n\) 为奇数
当顶点数为 \(n\) 时的最优解为 \(f(n)\) ，则需由 \(f(n)\) 推导 \(f(n+2)\) 。
新加入的两个顶点与其余的 \(n\) 个顶点都能构成三角形，但是新加入的两顶点之间的边重复计算 \(n\) 次。
因为 \(n\) 为奇数，所以两顶点之间的边最终为黑色，
所以最后增加的黑色边数为 \(2n+1\) 。
\
2. \(n\) 为偶数
同理：新加入的两个顶点与其余的 \(n\) 个顶点都能构成三角形。
但是因为 \(n\) 为偶数，所以两顶点之间的边经过偶数次计算后为白色，
所以增加的黑色边数为 \(2n\) 。
\
显然: \(f(3)=3,f(4)=4\) 。
整理可得：
\
\
其次考虑 \(m\ne 0\) 的情况
其实就是在 \(m=0\) 时的最优解上进行修改
重点来了！！！
对于
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 过来提前占个楼 东西不错很实用谢谢分享 感谢分享 感谢发布原创作品，程序园因你更精彩 谢谢分享，试用一下 谢谢分享，试用一下 yyds。多谢分享 用心讨论，共获提升！ 收藏一下 不知道什么时候能用到 收藏一下 不知道什么时候能用到 热心回复！ 谢谢楼主提供！ 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 很好很强大我过来先占个楼 待编辑 感谢，下载保存了 新版吗？好像是停更了吧。 感谢发布原创作品，程序园因你更精彩 感谢分享 感谢分享，下载保存了，貌似很强大
页:
[1]
2