洞察探讨小游戏SDK接入的最佳实践以及对企业跨平台开发的优势
590
2022-10-20
PE 106 Special subset sums: meta-testing (位运算枚举子集)
Special subset sums: meta-testing
Problem 106
Let S(A) represent the sum of elements in set A of size n. We shall call it a special sum set if for any two non-empty disjoint subsets, B and C, the following properties are true:
S(B) ≠ S(C); that is, sums of subsets cannot be equal.If B contains more elements than C then S(B) > S(C).
For this problem we shall assume that a given set contains n strictly increasing elements and it already satisfies the second rule.
Surprisingly, out of the 25 possible subset pairs that can be obtained from a set for which n = 4, only 1 of these pairs need to be tested for equality (first rule). Similarly, when n = 7, only 70 out of the 966 subset pairs need to be tested.
For n = 12, how many of the 261625 subset pairs that can be obtained need to be tested for equality?
NOTE: This problem is related to Problem 103 and Problem 105.
题解:
特殊的子集和:元检验
记S(A)是大小为n的集合A中所有元素的和。若任取A的任意两个非空且不相交的子集B和C都满足下列条件,我们称A是一个特殊的和集:
S(B) ≠ S(C);也就是说,任意子集的和不相同。如果B中的元素比C多,则S(B) > S(C)。
在这个问题中我们假定集合中包含有n个严格单调递增的元素,并且已知其满足第二个条件。
令人惊奇的是,当n = 4时,在所有可能的25组子集对中只有1组需要检验子集和是否相等(第一个条件)。同样地,当n = 7时,在所有可能的966组子集对中只有70组需要检验。
当n = 12时,在所有可能的261625组子集对中有多少组需要检验?
注意:此题和第103题及第105题有关。
题意有点别扭....你要手动写一下样例就明白了。
所有可能的25组子集对,就是 7 + 6 + 5 + 4 + 1 + 1 + 1 = 25。注意这些子集对都是非空的且不相交的。
所以有一组要验证S(B) ≠ S(C);也就是说,任意子集的和不相同,就是{1,4}和{2,3}这组子集对。
详细解释见代码:
#include
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~