题目分析
给定长度为 n 的类型数组 a 和状态位数组 b,初始保证相同类型的设备状态位相同。一次操作可对所有类型等于某 v 的设备翻转状态位(0↔1)。要求最少操作次数,使最终状态位序列 b 为回文。
对称位置 (i,j=n+1−i) 且 ai=u, aj=v,操作后需
bi⊕xu=bj⊕xv
其中 xu,xv∈{0,1} 分别表示对值为 u,v 的组是否翻转。即约束
xu⊕xv=bi⊕bj.
建立一个图,节点为不同的 a 值,边 (u,v) 带权 d=bi⊕bj。求在每个连通块中,满足所有异或约束的 x 向量,使得翻转次数 ∑xu 最少。