1.关于求两个集合求交集的下界论证
用的类似0-1原理的思想，将排序规约到求交集，如果能够求出交集就能排序，通过求交集所作的比较，必然可以排好序。构造了两个集合[a1,0]…[an,0] 与[a1,1]…[an,1]。参考：computer algorithms c++
假设待排序的序列为a1,a2,a3…an，设排好序后的序列为k1,k2,k3…kn
构造了两个集合A={[a1,0],[a2,0]…[an,0]},B={[a1,1],[a2,1]…[an,1]}
首先证明：在求解相交问题时，必然对[ki,0],[ki+1,1]进行了比较
因为如果没有进行比较，则把A中的[ki,0]改成[ki+1,1]，这个替换不会改变其他比较的结果，但是已经出现了重复了，也就是造成了相交但是原算法会认为不相交。
然后说明利用不相交集合问题所作的比较可以排好序
根据求相交问题时所作的比较，构造图，节点代表a中元素，如果ai,与ak之间进行过比较则画条边。
首先找到最小的元素am，然后从am出发，寻找相邻中最小的那个，这样逐步扩展就排好序了
因为ki与ki+1必然比较过了，而这个过程最多需要遍历的边的数目就是求相交问题所作的比较数目
2.下面这个可以做到Bit Scan Forward的效果，那个0x783a9b23是怎么搞出来的啊？-,-
如果我要用类似的方法做个128bit的BSF，应该怎么搞？
b 是__int64*
__int64 bb = *b ^ (*b – 1);
uint32_t fold = int(bb) ^ int(bb >> 32);
int idx = BitTable[(fold * 0x783a9b23) >> 26]);
static const int BitTable[64] = { 63, 30, 3, 32, 25, 41, 22, 33, 15, 50, 42, 13, 11, 53, 19, 34, 61, 29, 2, 51, 21, 43, 45, 10, 18, 47, 1, 54, 9, 57, 0, 35, 62, 31, 40, 4, 49, 5, 52, 26, 60, 6, 23, 44, 46, 27, 56, 16, 7, 39, 48, 24, 59, 14, 12, 55, 38, 28, 58, 20, 37, 17, 36, 8};
分析： __int64 bb = *b ^ (*b – 1);做到这，只需要统计bb的bit中1的个数就可以了,所以不一定必须用下面这个表
uint32_t fold = int(bb) ^ int(bb >> 32);
int idx = BitTable[(fold * 0x783a9b23) >> 26]);
这两步实际完成了一个映射，fold的值形成的集合与idx的值形成的集合之间的映射。
如果以8bit的BSF为例,实际上下面两个集合的映射设为
A：{0000 0001 0011 0111 1111 1110 1100 1000}->B:{0,1,2,3,4,5,6,7}要找到一个可以构成这个映射的x 只要 (A[i]*x)%8=B[j],x就相当于那个64位的时候的0x783a9b23。对于x的要求就是对于A中的每个元素A[i],(A[i]*x)%8的结果对应于B中的不重复的元素就可以。最简单的方法，这个x可以通过枚举来做，比如对于这个0x783a9b23，可以枚
举出来，但是对于128位范围就太大了，枚举不太管用了
这个(a*x)%n ={1,2,3…n-1}，感觉在数论上就是一个专门的概念，具体就不太了解了
3.如何求得一个N节点的无向图中所含“三角形”的个数？
转化：将无向图转换为有向图，借此减少重复
一个方法是从一个顶点出发，然后找到距离为1的顶点集，看这些顶点集之间是否有边。但这个方法有个。问题里面的很多三角形会重复出现，为了去重我们不得不对每个三角形开个(A,B,C)的表标识一下，但是这样使算法复杂度上升到必然是n^3。
解决方法是：给所有的顶点赋一个不同整数值，根据顶点见的大小关系，将原来的无向图改成有向图。这样一个三角形ABC就变成唯一的了。
A->B B->C A->C
这样首先求出A中距离为1的点集，然后求出距离为2的点集，二者交集就是三角形的个数。
同时观察当从B C出发，也不会再把它重复计入了。总的复杂度大概是：V*max(degree(vi)*degree(vj))
2009 6月 smth
1.圆覆盖最大权
可以将树木看做平面内的N个点，以点的权值M0，M1，…Mn表示每棵树可出产的木材体积。圆的半径为R(注：在圆边上的点不算圈入圆内)，求以圆圈地，最大可以圈到多大的权值？
实际上有两个不同的思路：
1).把点每个点扩展成半径为R的圆，然后看看哪部分交的加权和最大，那部分就是圆心的位
置。2).枚举三点内接三角形确定的圆 以及二点在圆上+半径=R 的圆 找出它们中满足条件
的最大覆盖圆。
第一个wy不是给出算法了么？就是求圆周上的线段最大重叠。多加一圈排个序就好。
这个方法用直观的角度可以看成，对每个点，用一个半径R的圈卡在其上转一圈。所有其
他点计算一下进圆和出圆的极角。
第二个思路，存在一个很简单的O(n^4)的枚举实现
2.汽车运油
有一个小汽车,跑一公里耗油一升,油箱可储油500L,现准备穿越沙漠,沙漠长度1000公里,现在起始点有无限油可以使用,问在沙漠何处建立补给站,可以达到穿越沙漠用油量最省..
<国际信息学奥林匹克竞赛指导–实用算法的分析与程序设计>上有，应该保证运油的过程刚好耗掉500L，同时将一定量的油运到下一个地点。从后往前间距依次是 500 500/3 500/5。。。也就是说最后那个油站距离终点500公里，只要这个油站有500L油，汽车就刚好用它走到终点，依次逆推。
3.路径走法
坐标系从(0,0)点走到(9,9)点，只能向右或者向上走，其中有些点不能走，问有多少种走法？
如图：假如。的位置不能走。（希望图能分辨清,左下角是(0,0)）
．．．．．．．．．．
．．．．．．．．．．
．．．．．．．．．．
．．。。．．．．．．
．．．．。．．．．．
．．．．．．．．．．
．．．．．．．．．．
．．．．．．．．．．
．．．．．．．．．．
．．．．．．．．．．
4.ILP找一个数列中第二小的数。只能用integer linear programming的方法。
最小值：
sum{xi} = 1
min1 = minimize{a1x1+a2x2+….anxn};
最小2数和：
sum{xi} = 2
min2 = minimize{a1x1+a2x2+….anxn};
次小值 = min2 – min1
5.题目描述：
设有n个正整数，将它们联接成一排，组成一个最小的多位整数。
程序输入：n个数
程序输出：联接成的多位数
例如：
n=2时，2个整数32，321连接成的最小整数为：32132，
n=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355
[题目要求]
1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算法。
2. 给出算法的时间空间复杂度。
3. 证明你的算法。（非常重要）
定义一个这样的比较法则：比较A,B，通过AB和BA的大小来比较.
如果AB>BA则A>B 如果AB<BA则A<B
比如A=32和B=323232321，我们比较AB=32323232321 和BA=32323232132的大小.AB>BA,得
出A>B。
只要能证明：如果A>B B>C 那么 A>C，再加上交换论证，就可以证明按照这个比较函数
排序后从小到大输出即可。如果AB没有前缀关系的话，结果很明显，比如123 45这个123肯定放在45前面。关键是证明具有前缀关系的那些。比如1223 12 122
画了一些感觉是正确的，也没找到反例，谁能找个反例或者证明下吧
6.警报器(alarm)
【题目描述】
一个警报系统为了防范入侵者通过一个正方形的房间，由一系列安装在地板下不同位置的噪声警报器组成。每个警报器都有自己的报警阈值，当到达警报器的噪声超过这个阈值时它就会报警。
入侵者产生的噪声和传递距离满足反比关系，与入侵者距离为r的地方，噪声大小将是A/(r^2)，其中A是入侵者产生的噪声。
房间为正方形，边长为100。西南角坐标为(x=0, y=0)，东北角坐标为(x=100, y=100)。房间入口和出口位于南北正中位置，坐标分别为(50,0)和(50,100)。
给出房间每个警报器的坐标位置和阈值，输出警报系统的最大入侵噪声A（这是一个临界值，入侵者如果产生小于等于A的噪声，不会引起报警，大于A的噪声一定会引起报警）。注意：入侵者可以选择任意路径通过房间，坐标不一定是整数。
【输入】
第一行包含一个整数n，表示警报器的个数。以下3行分别表示坐标x、y和阈值t；每行包含n个整数，第i个数对应表示第i个警报器的值。
【输出】
输出包含一个实数（保留五位小数，第六位四舍五入，不足5位用0补齐5位），表示最大入侵噪声。
解：二分最大入侵噪声
每个警报器的危险范围(A/r*r > t)实际是一个半径为r= sqrt(A/t)的圆。整个问题等价于判断正方形中所有圆组成的图形是否能够隔断源点和目标点。判断这个用图来做，把所有圆与圆的交点，圆与正方形的交点求出，它们构成图的顶点，如果它们之间通过圆的边相连，则对应的在图中两个顶点间画条边。最终转化为判断从源点到目标点左侧正方形边上某个点到源点到目标点右侧正方形边上某个点是否存在一条路，这条路刚好就是隔断它们两个的分界判断正方形区域中一系列的圆组成的图形区域，判断当各个圆的半径多长时可以完全隔断正方形边上的两个点，即无法不通过这些圆而从一个点走到另一个点。
一种方法是二分可能的半径，然后判断某个半径是否可行。将这些圆的交点，以及圆与正方形的交点，把它们作为图的顶点，如果它们之间通过圆的边相连，则画一条边。由此转换为图中的连通性问题。
另一种方法是求各个圆相交的临界条件，然后找到一个能够刚好把这个区域断开的条件。实际上是一条最大边权最小的那条路的最小边权。
转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/70971767200942792156704/