首页 > 数据库技术 > 详细

CF1492E Almost Fault-Tolerant Database

时间:2021-03-13 15:45:22      阅读:51      评论:0      收藏:0      [点我收藏+]

给出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

原文:https://www.cnblogs.com/angelknows/p/14528165.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!