Codeforces Round #704 Almost Fault-Tolerant Database 枚举+模拟

题意

你有一条n次备份的长度为m的数组。现在由于一些原因,这些数组中有些数据被意外的修改了。已知每个备份被修改的地方不超过2个。现在给你被修改后的所有数据,问你有没有可能构造出原始数据,如果可能,原始数据是什么。


题解

考量$n=2$的场景。因为被修改的地方最多2个,那么两个数据差异点最多就是4个。

于是,不论n是多少,我以第一个数据为模板,和其他数据做对比。只要超过4就直接挂。然后选出其中差异最大的那个,后分情况讨论:

  1. 如果最大的差异就是4个。$C_4^2=6$暴力枚举改变情况。这样改好的结果就是确定的。然后拿着改好的结果让其他备份照着改。能改就改,不能改就直接挂。
  2. 如果最大差异$\leq2$个,那还说什么,直接输出第一个,所有备份照着改就完事了。

现在剩下了最麻烦的情况,最大差异是3个。

还是因为最多只能改两个。所以这3个差异点中,至少有两个分别来自两组数据。比如(1, 2, 3)和(4, 5, 6)。那么你至少要从第一排挑一个(也就是123里面挑一个),同时,你至少从第二排挑一个(也就是456里挑一个)。

现在剩下一个怎么办呢?我们$3\times2$的枚举上面挑选的情况。然后剩下那一个标记为待定。

接着拿着这个带有待定标记的结果去扫描。当第一次发现这个待定为不得不采取某个值的时候,把待定改了。如果后面匹配出问题,那就是No。不然输出最终结果。

就纯模拟,各种分情况讨论……


代码

Submission #112153393 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论