PE 106 Special subset sums: meta-testing （位运算枚举子集）

r囧r小猫 2022-07-13 03:08 111阅读 0赞

## 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:

1.  S(B) ≠ S(C); that is, sums of subsets cannot be equal.
2.  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是一个特殊的和集：

1.  S(B) ≠ S(C)；也就是说，任意子集的和不相同。
2.  如果B中的元素比C多，则S(B) > S(C)。

在这个问题中我们假定集合中包含有n个严格单调递增的元素，并且已知其满足第二个条件。

令人惊奇的是，当n = 4时，在所有可能的25组子集对中只有1组需要检验子集和是否相等（第一个条件）。同样地，当n = 7时，在所有可能的966组子集对中只有70组需要检验。

当n = 12时，在所有可能的261625组子集对中有多少组需要检验？

注意：此题和[第103题][103]及[第105题][105]有关。

题意有点别扭....你要手动写一下样例就明白了。

所有可能的25组子集对，就是 7 + 6 + 5 + 4 + 1 + 1 + 1 = 25。注意这些子集对都是非空的且不相交的。

所以有一组要验证S(B) ≠ S(C)；也就是说，任意子集的和不相同，就是\{1,4\}和\{2,3\}这组子集对。

详细解释见代码：

#include<bits/stdc++.h>
    using namespace std;
    int total = 0;
    void solve (int n)
    {
    	total=0;
    	//不算空集即 0**0这种 
    	for (int x = 1; x < (1 << n); x++)  
        {
        	for (int y = 1; y < (1 << n); y++)
    		{
    			if ((x & y) == 0) //子集对 (x,y) 不相交 
        	   {
               		int d1 = 0, d2 = 0;
                	for (int j = 0; j < n; j++)
               	 	{
                		if ((x & (1 << j)) > 0) d1++; //统计与x有相交元素的子集 
    				}
                   // cout<<"d1="<<d1<<endl;
               		 for (int j = 0; j < n; j++)
               		 {
                		 if ((y & (1 << j)) > 0) d2++;//统计与y有相交元素的子集 
    				}
    			    //cout<<"d2="<<d2<<endl<<"--------"<<endl;
    			    
                	if (d1 == d2)
                	{
                		
                    	int t = 0;
                    	bool ok1 = false;
    					bool ok2 = false;
                    	for (int j = 0; j < n; j++)
                   	 	{
                       	 	if ((x & (1 << j)) > 0) t++; 
                        	if ((y & (1 << j)) > 0) t--;
                       	 	if (t > 0) ok1 = true;
                        	if (t < 0) ok2 = true;
                        //	cout<<"ok1="<<ok1<<endl;
                        //	cout<<"ok2="<<ok 2<<endl<<"-----"<<endl;
                       }
                       //统计需要检验的个数 
                       if (ok1==true && ok2==true) total++; 
                       else if(ok1==false && ok2==false) total++; 
                      
                   }
               }
    	    } 
    	    
    	}
        cout<<"ans="<<total/2<<endl;//除以 2 ,是因为有重复的 
    }
    int main()
    {
    	solve(2);
    	solve(3); 
        solve(4);
        solve(7);
        solve(12);
    	return 0;
    }

[Problem 103]: https://projecteuler.net/problem=103
[Problem 105]: https://projecteuler.net/problem=105
[103]: http://pe-cn.github.io/Problem101-125/#Problem_103
[105]: http://pe-cn.github.io/Problem101-125/#Problem_105