题解 P2988 【[USACO10MAR]考试Test Taking】

sxyugao · 2018-06-27 10:27:47 · 题解

总的证明楼下的yyhhenry大佬已经写了，如果想了解更多细节或者看不懂他证明的可以去我博客上看。

我主要是证明他的那个引理：

对于两个长度为n的01串，A中a个1，B中b个1，任一排列中相同位置元素相同的数量至少为max(a+b-n,n-a-b)，通过分别分析0和1就可以得到。

我们仍然使用引理中的变量，进行分类讨论：

1、a+b>n，即 A 和 B 匹配1。

我们为了让相同元素尽可能少，考虑把 A 中的1全移到前端，B 中的1全移到后端，变成线段覆盖问题，重合部分为 a+b-n。

2、a+b<n，即 A 和 B 匹配0.

同理，我们考虑把 A 中的0全移到前端，B 中的0全移到后端，用同样的方法得出该情况下结果为 n-a-b。

3、a+b=n，显然答案为0。

主要证明和代码请移步：https://sxyugao.top/p/1192747.html#solution