给出n个长度为m的数组,求出一个数组,与这些数组各自的不同点最多两个,无解输出NO。
这问题很简洁。
首先看无解的情况,如果设数组集合为S,如果S中数组A和B 有>=5个不同点,显然无解。
因为答案数组与数组A最多两个不同点,这两个不同点最多可以抵消5个不同点中的两个,剩下的三个必然与A一样,从而与B不一样。
因此,假设现在的S中两两数组最多4个不同点。
现在可以考虑三个数组A,B,C的情况,感觉有MO组合题的味道。
假设A和B只有前4个元素不同,那么C与A在前四个元素中,必然至少有2个元素相同,C与B也一样。
?