我对USACO Cowpatibility解决方案的说明和代码感到困惑。
问题在这里定义：http://usaco.org/index.php?page=viewproblem2&cpid=862。
他们的解决方案在这里定义：http://usaco.org/current/data/sol_cowpatibility_gold_dec18.html。
我知道他们的线性解决方案需要包含和排除（PIE）的属性，并且我理解此属性，但是我对他们如何实现它感到困惑。我正在寻找这些行的解释：
“这会激发以下包含/排除解决方案：对于每种风味子集，计算每个子集中多少对喜欢所有风味的奶牛。我们将大小1的子集的所有计数相加，然后避免重复计算，我们减去大小为2的子集的所有计数。然后，将大小为3的子集的所有计数相加，减去大小为4的子集的所有计数，并添加大小为5的子集的计数。“
它们如何确定每个可能的子集，这些子集是什么？为什么只有31N个子集？如果有人给出示例子集的子集示例，这也将有所帮助。
有31N个不同的子集，因为每头母牛都有五种可能的口味选择。具体来说，此行解释了这些子集：
我们可以显式生成所有风味子集，其中至少一头母牛喜欢该子集中的所有口味
这样做的方法是遍历所有N母牛，然后构建他们喜欢的风味的强大功能集，不包括空集。电源集中有2^5套，因此除去31中的空白集。因此，共有31N套。
一个示例在这里非常有用，采用示例输入：
4
1 2 3 4 5 # Cow 0
1 2 3 10 8 # Cow 1
10 9 8 7 6 # Cow 2
50 60 70 80 90 # Cow 3
子集将是：
{
{1}, {1, 2}, {1, 3}, ..., {2, 3, 4, 5}, {1, 2, 3, 4, 5}, # Cow 0
{1}, {1, 2}, {1, 3}, ..., {2, 3, 10, 8}, {1, 2, 3, 10, 8}, # Cow 1
...
}
每头牛产生31个子集。从那里开始，该算法会计算生成特定子集的母牛的数量（例如，请注意{1}是由母牛0和1共同生成的，我们只跟踪每个子集产生了多少母牛），并应用包含-根据子集大小进行排除。
[好问题，我曾经做过USACO，他们遇到了非常有趣的问题，这些问题仍然在许多公司给出的“聪明”面试问题中脱颖而出。 ：）