求 1 集 合 算 法。
集合{S0,S1,S2,S3,.....Sn}；
集合中元素Si ={X1,X2, ...X10} (则由10个自然数组成)，其中 1<=Xi<=100.
对于任一有限集合
A = { {1,2,3,4,5,6,7,8,9, 10 },...{...} };
B = { {1,2,3,4,5,6,7,8,9, 11 },...{...} };
A、B的元素都各不相同(S的元素没有顺序性, 如{1,2,3,4,5,6,7,8,9,10} 和{1,10,2,3,4,5,6,7,8,9}是相同的)
问题: 怎么组织A的数据，从B任意抽取一个元素Sb, 能基本以Q(1)时间内从A中
找出一个与Sb最相似的元素Sa,
其中最相似: Sb与Sa交集，则相同Xi最多。
[解决办法]
相同的问题：高度为10的二叉树，每过结点值域为 1 <=Xi <=100，最多可有100个孩子，从左到右排序；则查找有无相同时间为o(1)，插入和删除也是o(1);
可是相似的问题嘛：
如果用集合作为结点储存，计算两个集合的相交数是o(1)；
如果用散列表的话，目的是把查找的范围缩小吧，可是散列函数无法得到：
如：
{1，2，3，4，5，6，7，8，9，10}这个集合，跟它最相似的集合不知道有什么特点，也无法归类，因为这个归类是和输入分布相关的，而一般来说输入分布是未知的！
换句话说就是每个集合和它是最相似的概率都是一样的！
个人觉得最好的实现：
集合中元素Si ={X1,X2, ...X10} (则由10个自然数组成)，其中 1 <=Xi <=100；
结点属性：
区间域：取最大和最小数的作为一个区间值
关键字域：以该节点为根的子树，所含所有结点的区间值的最大值；
来建立一个区间树（具体参见算法导论第二版，其中的数据结构的扩张。
对区间树里每一个和它相交的节点作比较，统计就行了；
这样就从我所能想到的最大程度上缩小了检查范围！
[解决办法]
不管怎么说要解决问题的核心就是缩小比较范围，区间树应该是最适合的了！
注意二叉树一定要用红黑树或者其他的平衡树来实现!
由于不方便书写的原因，我就不画图讲解了，但是我保证这个能解决你的问题！详细请看算法导论，如果有什么不懂的，这里是我的邮箱：
odiwlykwia@live.cn
[解决办法]
既然数据每次都是变化的,能够做的优化就是利用类似动态规划的方法,尽量将已经算过的数据重复利用,
做到重复的运算可以直接从hash表里读取。
另一点就是利用分治，缩小待处理数据的范围。
最后就是利用剪枝，减少一些不必要的运算，不用所有运算都算到最后一步。
除此之外，并没有什么更好的方法。O(1)似乎是不可能的，能做到log(n)就很不错了！
[解决办法]
哦，我有这么个想法，每个集合用一个数组a[..][100]来储存,如a[1][100]来表示{1，2，3，4，5，6，7，8，9，10}：
1 2 3 4 5 6 7 8 9 10 11....99 100
a[1][100] 1 1 1 1 1 1 1 1 1 1 0....0 0;
这样就可以用dp来做了，可是这样的时间复杂度是：T(n,m)=T(n-x,m-1)+T(x,m-1)+O(n);这里的x是含该元素的集合数目，n为|A|，m=10;
如果正向迭代的话，就是平方时间了；最好是反向剪枝来做；
[解决办法]
应该还是不满足你的要求，一般说来dp的时间是Ω（n）的，除非可以把以前查找过的集合的计算数据重复使用；
分治和剪枝可以是o(n)的，如我上面所说可以利用区间来剪枝，或者其它特点来剪，那么关键就是寻找相似集合的特点；
至于你说的有和待查找的区间没有交集的集合数目只有百分之几，我不同意你的观点
[解决办法]
既然你已经想到了100维的01向量，那完全可以进一步想想与当前集合相似的集合集的特点，
比如可以按照一定的方法统计一个向量中1的分布特点（比如偶数位的1的个数，前50位1的个数......)
虽然并不是满足这些分布条件的向量都与当前向量相似，但所有与当前向量相似的向量应当都满足前面所提到的特点。
如果用这种方法的话，可以将A的数据规划为一个树型结构，可以很快地降低搜索范围。
[解决办法]
每个集合都是10个元素。一般来说是小于机器字长的。那么用一个CPU指令就可以了。
那么如果采用类似shiftor的方式，
在开始得时候构造一个匹配表格，那么o（1）的时间就够了。