CF1492E Almost Fault-Tolerant Database

给出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也一样。

CF1492E Almost Fault-Tolerant Database

上一篇:JDBC


下一篇:mac mysql: command not found如何解决?