提问人：cracra 提问时间：3/25/2020 更新时间：3/27/2020 访问量：477
奶牛兼容性 USACO
Cowpatibility USACO
问：
我对 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 个子集？如果有人举例说明他们的样本案例的子集是什么，那也会有所帮助。
答：
0赞
kevmo314
3/25/2020
#1
有 31N 个不同的子集，因为每头奶牛有五种可能的口味选择。具体来说，这一行解释了子集：
我们可以显式生成所有类型的子集，其中至少 一头奶牛喜欢该子集中的所有口味
做到这一点的方法是遍历所有 N 头奶牛，然后构建它们喜欢的口味的幂集，不包括空集。幂组中有组，因此删除空组的结果为 31。因此，总共有 31N 套。2^5
这里有一个示例非常有用，以示例输入为例：
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 个子集。从那里，该算法计算生成特定子集的奶牛数量（例如，请注意，由奶牛 0 和 1 生成，我们只跟踪每个子集生成多少奶牛），并根据子集大小应用包含-排除。{1}
很好的问题，我曾经做过USACO，他们有非常有趣的问题，这些问题在许多公司给出的“聪明”面试问题中仍然很突出。:)
2赞
user13133159
3/27/2020
#2
他们生成并存储子集，以跟踪具有 1 种共同口味、2 种共同口味、3 种共同口味、4 种共同口味和所有 5 种共同口味的奶牛对数。为此，他们使用了地图。
现在，有 31N 个子集，因为对于每头奶牛，您可以创建 31 种最喜欢的口味组合。例如，奶牛 1 最喜欢的冰淇淋口味是 1、2、3、4、5。因此，不同的子集是：
{1, 0, 0, 0, 0} {1, 3, 0, 0, 0} {2, 5, 0, 0, 0} {1, 2, 5, 0, 0}
{1, 2, 0, 0, 0} {1, 4, 0, 0, 0} {1, 3, 4, 0, 0} {2, 3, 5, 0, 0}
{1, 2, 3, 0, 0} {1, 5, 0, 0, 0} {1, 3, 5, 0, 0} {3, 4, 5, 0, 0}
{1, 2, 3, 4, 0} {2, 3, 0, 0, 0} {2, 3, 4, 0, 0} {1, 2, 3, 5, 0}
{1, 2, 3, 4, 5} {2, 4, 0, 0, 0} {2, 4, 5, 0, 0} {1, 3, 4, 5, 0}
{2, 3, 4, 5, 0} {2, 0, 0, 0, 0} {3, 0, 0, 0, 0} {4, 0, 0, 0, 0}
{5, 0, 0, 0, 0} {3, 4, 0, 0, 0} {3, 5, 0, 0, 0} {4, 5, 0, 0, 0}
{1, 4, 5, 0, 0} {1, 2, 4, 0, 0} {1, 2, 4, 5, 0}
如您所见，有 31 个子集。（这是因为可以制作 2^5 = 32 个集合，包括一个空集合。 32 - 1 = 31。由于 N ≤ 50,000，因此可以生成 31N 个子集。扫描输入后，代码为每头奶牛生成子集，并将它们添加到地图中：
map<S5, int> subsets;
他们将每个组合映射到被看到的次数。示例输入的一些条目示例如下：
{
[{1, 0, 0, 0, 0}, 2], # 2 cows, Cow 1 and Cow 2 both like flavor 1
[{8, 10, 0, 0, 0}, 2], # 2 cows, Cow 2 and Cow 3 both like flavors 8 and 10
[{50, 60, 80, 0, 0}, 1], # 1 cow, Cow 4 liked flavors 50, 60, 80
# and so on...
}
最后，基于子集中非零数的数量，该算法应用包含-排除原则。它只是遍历所有 31N 个子集，并添加或减去该子集的映射中存储的计数。（如果是 1、3 或 5 个非零数字，则将计数相加;否则将计数相减。然后，它从 N * （N-1） / 2 中减去这个答案，以输出不兼容的奶牛对数。
我希望这个解释对您有所帮助！祝你未来的比赛好运！
评论