1 给定N， 求出最小的M，使得N*M的结果十进制后，只包含0和1
搜索算法，运用余数优化
类似： 最快的办法求最大公约数：
lcd (x, y) = ( if x&1 && y&1: lcd(x, (x-y)/2); else lcd(x/2 if x&1==0, y/2 if y&1==0) )
2 精确表达浮点数（循环节）：
x=x1x2..xi . y1y2...yj (z1 z2... zk) ={ x1x2..xi y1y2...yj}/10^j + m/10^j
其中 循环节 m = z1 z2 ... zk/ (10^k -1)
所以 x = [ { x1x2..xi y1y2...yj} + {z1 z2 ... zk}/ (10^k -1) ] /10^j =
[ { x1x2..xi y1y2...yj}* (10^k -1) +{z1 z2 ... zk}
]/ [ (10^k -1)*(10^j ) ], 化简就可。
反向： 给出 n,m 求 n/m的循环节：
n/m = k + 0.y1y2...yj (z1 z2... zk)
t/m = 0.y1y2...yj (z1 z2... zk) = y/10^j + z/ [ 10^j *(10^k - 1) ]
一个重要的结论是 0.(z1z2...zk) = {z1z2..zk}/(10^k-1), 比如 0.（353） = 353/(1000-1) = 353/999.
2 给定a1~ak，以及推导公式ak+1 <= a1~ak,最快的办法求到 an
方法：矩阵加速（专用于求解k阶递推数列） 或 特征方程（会存在无理数）
3 寻找最近点对距离、最远点距离
二分（ 按照纵线二分）
数组中找相邻数的最大差值（分 桶）
4 数组分割
转化为带物品数量限制的背包重量问题 , O(N^2*Sum),N=obj_cnt, Sum=w_total
//bool[i][j]: 装i个物品，能否装到重量j
bool[0][0] = true
for k=1 to obj_cnt: //背包问题最外层迭代一定是物品，因为物品只能装一次
for i=1 to obj_cnt/2:
for j = w_total to obj_w[k]:
bool[i][j] = bool[i-1][j] || bool[i-1][j-obj_w[k]]
5 最短摘要的生成
类似于leetcode上面的最短包含了 指定数量的字母的字符串 ， 用一个队列去保存当前摘要序列中的各个关键词出现的位置（按顺序），每次遇到一个新单词，把队首的多余单词去掉，更新当前序列的长度。。直到找到最短长度的序列。
6 桶中取黑白球算概率：
排列组合 + DP（类似还有卡特兰数f [ 2n ] = E( f[ 2n-2*i-2 ] * f[ 2*i ], i=0~n-1 ) = C（2n, n) - C(2n, n-1) ）
cnt[sum][white]为还剩下sum个球，白球数量white的概率排列组合数。
cnt[200][100] = 1
cnt[sum][white] = cnt[sum+1] [ white ]*3 + cnt[sum+1] [ white+2] //四种取法，对应四种上一个状态
最后 cnt[1][0] / (cnt[1][0] + cnt[1][1])
int a[21][21];
memset(a, 0, sizeof(a));
a[20][10]=1;
for(int i=19; i>=1; i--){
for(int j=0; j<=10; j++){
a[i][j] = a[i+1][j]*3 + a[i+1][j+2];
}
}
cout<<a[1][0]<<":"<<a[1][1]<<endl;
还有一种方法： 白球的数量每轮减少0 或2， 所以白球数量始终是偶数，如果只剩一个球，则必定是黑球。
7 蚂蚁爬杆
找所有蚂蚁都离开杆子的最短和最长时间。呵呵，简单转化一下就变成同时求最大最小值了。
8 取石子游戏数学推导
9 24 点
带状态压缩（二进制，表示第几个数被用到）的dp
s[ bits ] = map< result, cnt > // bits 表示哪些数字被用到， result表示计算结果， cnt表示得到该结果的方法数
inline int calc(int tt, int a, int op, int b, bool & tag){
if(tt) {int tmp =a; a=b; b=tmp;}
switch(op){
case 0: return a-b;
case 1: return a+b;
case 2: return a*b;
case 3:{
if(b==0) {tag=false; return 0;}
return a/b;
}
}
tag= false; return 0;
}
bool 24Game(vector<int> &num){
vector<map<int, int> > s(16, map<int, int>());
for(int i = 0; i<4; i++)
s[1<<i] [num[i]] = 1;
for(int i= 1; i<16; i++){
for(int j = 1; j<i; j++){
if( i & j != i ) continue;
// merge : f(j) U f(i-j) => f(i),
for(map<int, int>::iterator it = s[j].begin(); it != s[j].end(); it++){
for(map<int, int>::iterator jt = s[i - j].begin(); jt != s[i-j].end(); jt++){
for(int op = 0; op<4; op ++ ){
for(int tt =0; tt<2; tt++){
bool tag = true;
int res = calc(tt, it->first, op, jt->first, tag);
if(tag){// record the result
s[i][res] = s[i][res] + (it->second*jt->second);
}
}
}
}
}
}
}
return s[15][24] > 0;
}
10 数字哑谜和回文
哑谜： 数学推理
回文： 枚举“我”和寺，很快能够 找到人过大佛四*我 = 是佛。的所有解
he^2 = she, 类似， (10*h +e )^2 = h^2*100 + e^2 + 20*h*e = s*100 + 10*h + e, 则 e^2 %10 = e, e = 1、5、6、0
e = 1: 1 + 20h + 100h^2 = 1 + 10h + 100s, 10h = 100(s-h^2), h = 10(s-h^2), s=h^2, h=0, s=0 不行
e = 5....
======================================================
10 俄罗斯方块
二进制表示块
11 扫雷
12 数独
13 饮料供货
方法一： dp
value[ volume ] [ obj_i ] 表示对obj_i饮料物品分组进行装包，得到的最大满意度
value[ volume ] [ obj_i ] = max ( value[volume - k* w[i] ] [ obj_i - 1] + v[i] * k, k = 0 ~ C[i] ) 即对重量为volume状态，轮番使用分组中的物品
for i = 1 to n://分组
for volume=max_volume to k*w[i]://每个重量
for k = 1 to C[i]://每个分组物品
value[ volume ] [ obj_i ] = max ( value[volume - k* w[i] ] [ obj_i - 1] + v[i] * k //上一个分组递推到本分组
或者：
for i = 1 to n://分组
for k = 1 to C[i]://每个分组物品
for volume=max_volume to k*w[i]://每个重量
value[ volume ] [ obj_i ] = max ( value[volume - k* w[i] ] [ obj_i - 1] + v[i] * k
方法二：记忆化搜索（dfs+dp)
一些不需要用到的状态就不用算了
方法三： 贪心法
考虑到 max_volume 是一个二进制的数， 那么每次从最低位找，找到可以用于填充这一位的饮料
比如第 j（j>=0)位， 对应于可以用的饮料为 （ w=2^k, value=xx ),其中k<=j
根据贪心策略找到最好的、这一位可用的饮料。使用 2^(j-k）单位 。
14 光影切割问题
根据交点个数，能够推导直线分割的面数， 即cnt（0）=1， cnt (n) = cnt(n-k) + k+1 ， cnt(n) = E(ki) + n=交点个数+n+1
所以O（n^2) 枚举获得所有交点。O（mlogm）为对交点排序。
另外，可以使用逆序对个数来算交点
如直线跟两边的边框纵线相交，如线1在两条边框上交点分别为(y1=1, y2=10),而另一个线为(y1=10, y2=1),那么他们有一个逆序对，也必有一个交点。
15 买书问题
这道题直觉上可以greedy，但其实不行，必须states dynamic planning
cnt[y1][y2][y3][y4][y5] 表示各种书分别为y1,y2..y5，其中y1>=y2>=y3>=y4>=y5,的最大折扣数
这个dp存在一个优化：
对任意状态cnt[y1][y2][y3][y4][y5] ，后续除了<[1,2,3],4,5>一定存在<[1 2 3] 4>这种含有4而不含5的放书方法,
同理后续除了<[1,2],3,4>一定存在<[1,2] 3>这种含有3不含4的方法
所以递推公式变得简单了：cnt[y1][y2][y3][y4][y5] = max( cnt[y1-1][y2-1][y3-1][y4-1][y5-1] if(y5>=1), cnt[y1-1][y2-1][y3-1][y4-1][y5] if(y4>=1), cnt[y1-1][y2-1][y3-1][y4][y5] if(y3>=1)。。。, cnt[y1-1][y2][y3][y4][y5] if(y1>=1) ).
====================================
第一章：
1 绘制cpu占用率曲线