紫丁香
紫丁香 题解
紫丁香 题解 前言 来自一场 \(\text{noip}\) 提高模拟赛的题目。 题目描述 有 \(n\) 点 \(m\) 边的 简单无向连通图,点编号为 \(0\sim n-1\),要求删掉若干条边,最大化奇数度点的个数。 求:能得到最大答案的构造,用 \(m\) 长的 \(01\) 串表示,\( ......
P9393 紫丁香
膜拜 yxcat 考虑二分答案,将问题转换成验证 $A$ 是否由 $S$ 通过若干次操作生成 将操作效果反向,即存在一个操作 $x$,满足 $A_i=1$ 且 $x_i=1$,那么将 $A_i$ 处的 $1$ 消掉, 也就是对于一个串 $A$,如果 $A$ 尽量消 $1$ 之后剩下的消不掉的 $1$ ......