当前位置:首页 » Project Euler » 详细页

Special subset sums: meta-testing 题号:106 难度: 50 中英对照

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.

Solution

题意比较难理解,首先解释一下题意: 1. 这里的集合不一定是特殊子集。 2. 这里集合的元素可以认为是严格递增排列的。 3. 这里的集合满足条件2,意味着任意两个不交的子集,元素个数多的那个子集的sum值一定大于另一个的sum值(sum值是指集合内所有元素的和)。 4. 任取两个不交的子集,它们的sum值可能相等的含义是:不包含一定不相等的所有情况。 那么任取两个不交的子集B和C,如下几种情况B和C的sum值是一定不等的: 1. B和C的元素个数不同,根据条件2可知其sum值一定不等。 2. 当B集合的最小元素大于集合C的最大元素时,显然B和C的sum值不等。 反过来,当B和C元素个数相同,且存在B中的元素大于C中某元素,且存在C中的元素大于B中某元素,则应被计入答案。 按上述流程枚举即可。

Code

import java.util.*;

public final class p106 {
    
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }	

    public static String run(){
        int a[] = {1219 ,1183, 1182, 1115, 1035, 1186, 591, 1197, 1167, 887, 1184, 1175};
        Arrays.sort(a);
        // 所有的子集
        ArrayList<ArrayList<Integer>> sets = MakeSubsets(a);
        int size = sets.size();
        int ans = 0;
        for(int i=0;i<size;i++){
            ArrayList<Integer> set1 = sets.get(i);
            for(int j=i+1;j<size;j++){
                ArrayList<Integer> set2 = sets.get(j);
                //不相交
                if(set1.size() == set2.size()){ 
                	if(!isDisjoint(set1,set2) ){
                        boolean s=false,t=false;
                        for(int k=0;k<set1.size() && (!s||!t);k++){
                            if(set1.get(k) > set2.get(k))
                                s=true;
                            if(set1.get(k) < set2.get(k))
                                t=true;
                        }
                        if(s&&t)
                        	ans++;
                            
                    }
                        
                    
                }
            }
        }
        return Integer.toString(ans);
    }

    // 两个子集元素是否相交 true 相交 false 不相交 
    public static boolean isDisjoint(ArrayList<Integer> set1,ArrayList<Integer> set2){
    	for(int x:set1)
    		if(set2.contains(x))
    			return true;
    	return false;
    }
    
    
    // 求出所有的子集
    public static ArrayList<ArrayList<Integer>> MakeSubsets(int a[]){
        ArrayList<ArrayList<Integer>> sets = new ArrayList<ArrayList<Integer>>();
        for(int i=1;i< (int) Math.pow(2,a.length);i++){
            ArrayList<Integer> set = MakeSubset(a,i);
            sets.add(set);
        }
        return sets;
            
    }
    // 求出子集
    // 利用 和  1 进行与运算 并移位
    //  001001 相当于根据 1 所在的位置取 第 2 第 5的位置对应的数
    // &000001
    //----------
    //       1 取出该位置对应的数
    // 下面右移一位后
    //  000100
    // 下面同理了
    public static ArrayList<Integer> MakeSubset(int[] a,int m){
        ArrayList<Integer> set = new ArrayList<Integer>();
        for(int i=0;i<a.length && m>0 ;i++,m>>=1){
            if((m&1)==1)
                set.add(a[i]);
        }
        return set;
    }
}
21384
264ms