给定一个n*n地图和高度，一个人从左上角地图开始，需要走到右下角的地图，问他走的路程中所到达的最大高度和最小高度的差最小是多少。
二分答案，然后 dfs 看下。
http://www.cnblogs.com/lvpengms/archive/2010/04/21/1717457.html
这又是一个树状数组、LCA、RMQ 相关的问题。仔细看那个幻灯片，弄清楚 LCA 和 RMQ 转化，看算法导论。
题意：给定一棵有n（ n < 100001 ）个结点的带边权的树,处理以下一共q（q < 100001）个操作：
1，改变树的一条边的权；
2，求给定点和某点的距离，后者是编号为1的结点，若是第一次执行操作2，否则为上次执行操作2的给定点。
没有了操作1，这题就是典型的 LCA，于是怎样有效地执行操作1就是这题的关键。还记得LCA到RMQ的转化吗，在这里。
http://www.cnblogs.com/zgmf_x20a/archive/2008/10/15/1311313.html
过程中DFS会生成一条回路，并且产生一个从遍历次序到结点编号的满射，我们称它为 order[]。我们知道，若以结点到根的距离作为树的深度，如果一条边的权增加了delta，那么这条边链接的子树内的所有结点的深度都增加了 delta。又因为子树内的结点的遍历次序是连续的，所以我们可以建立从遍历次序到根的距离的映射 dist[]，于是每次执行操作 1 只需对dist[]的一片连续区域作修改即可，可以用线段树或者树状数组。
搞定了操作1，我们发现操作2也被搞出来了，因为LCA(u,v)=order[RMQ(dist[出现u的任意遍历序号...出现v的任意遍历序号])]。
http://www.cnblogs.com/zgmf_x20a/archive/2009/01/24/1380655.html
求对于 n 个顶点，一共可以组成多少个连通图。
1.随便从 n 个点里面拿出来 2 个点,放到 2 边,当成是 2 个子连通图
2.然后从剩下的 n - 2 个点选 k - 1 个, ans = C(n-2, k-1),放到左边,那么它和我们刚才取出来的某个点组合成了一个大小为 k 的连通图
它的种类数是dp[k], 表示大小为 k 的时候的连通种类数。
显然右边有(n-k)个,所以 ans*=dp[k]*dp[n-k];
3.由于你必须保证 2 个子图最少有一条边连起来, 所以ans*=2^k - 1, 既对于左边的 k 个点,要么和右边的有连边,要么没边,所以一共是 2^k,必须减掉都不连边的情况.
所以，
dp[i]=sigma(dp[j][dp[i-j]*c(i-2,j-1)*(2^j - 1)) (1<=j
排列组合，我心中永远的伤痛。
flymouse 是幼稚园班上的班长，一天老师给小朋友们买了一堆的糖果，由 flymouse 来分发，在班上，flymouse 和 snoopy 是死对头，两人势如水火，不能相容，因此 flymouse 希望自己分得的糖果数尽量多于 snoopy，而对于其他小朋友而言，则只希望自己得到的糖果不少于班上某某其他人就行了。
比如 A 小朋友强烈希望自己的糖果数不能少于 B 小朋友 m 个，即 B - A <= m，A，B分别为 A、B 小朋友的分得的糖果数。这样给出若干组这样的条件，要使 flymouse 最后分得的糖果数 s1 和 snoopy 最后分得的糖果数 s2 差别取到最大！即 s2-s1 取最大.
因此根据题意，可以列出如下的不等式：
Sbi-Sai <= ci(1 <= i <= n)
最终要使得Sn-S1最大；
其实就是一个差分约束系统。
求最短路时用到的三角形不等式中，最终对于每条有向边(u,v)有: d[v]<=d[u]+w(u,v);
将 Sbi-Sai <= ci 变成 Sbi <= Sai + ci;就跟上式的形式相似。
在最短路的松弛过程中每次都是 if(d[v]>d[u]+w(u,v)) then d[v]<=d[u]+w(u,v);
则最后不断的松弛，使得对所有边 d[v]<=d[u]+w(u,v);
对于 Sbi<=Sai+ci;通过做 bellmanford，Sbi 通过不断的松弛,由正的无穷不断减小，直到所有的约束条件都的到满足，所以这时的求出的Sbi是满足约束条件的最大的一组解!!
这样最后的结果就是 Sn-S1，初始时将 S1 设为 0，则最后的结果就是 Sn 的值! 不过直接用 bellman-ford 复杂度高了点！用队列优化的 bellman-ford即 spfa可以承受!
参考：
http://www.cppblog.com/infinity/archive/2008/11/05/66048.html
参考
算法合集之《浅谈信息学竞赛中的“0”和“1”》.pdf
一个矩形区域(h *w )中有一些点，现在给你一个小矩形(t * s)，如何让小矩形尽可能覆盖尽可能多的点。
这个题目可以有多种做法，比如硬搜索，或者树状数组。
Read the rest of this entry »
有 D 种疾病在 N 头牛中，告知每头牛所患的病，问至多能选择多少头牛，使得它们所患的病总数不超过 K。
这是全排列的一个应用，有可能患病的总数是 15 种。可以把患病的序列看成一个二进制数：有该种病表示为 1，没有表示为 0；
这样每头牛对应一个整数，然后利用全排列函数，对 0,0,0,...1,...1 这样一个结尾一个 K 个 1 的序列做全排列（利用全排列函数之前要确保序列升序。。。）。检查每个全排列和每头牛所患疾病的与或关系就知道了。
http://blog.sina.com.cn/s/blog_64675f540100hoxl.html
http://blog.csdn.net/aipb2008/archive/2008/03/29/2227490.aspx
给你两个数字串 S1 和 S2，求 S1 中有多少个长度等于 K 的子串在 S2 中能找到。而没有长度大于 K 的 S1 的子串出线在 S2 中。
思路：后缀数组。
Read the rest of this entry »
有 N 个集合，第 i 个集合 S(i) 元素个数为 C(i)，集合中的元素位于 1 到 10000 之前，同一个集合中的元素可能重复。现在有很多查询，给定两个元素，问它们是否至少同时出现在一个集合中。最多能有 1000 个集合。
位操作，maze[i][j] 表示 i 是否出现在集合 j 中，由于 i*j 可能达到 10000000，实际上是不需要这么大的量的，j 最大只需要达到 32 就可以了。1个 int 为32 位，所以需要 32 个 int 既 1024 位，代表 1000 个 N 的下标。
Read the rest of this entry »
对一批给定的串进行排序，要求按照串的逆序数排。串都是等长的，而且串中出现的字符也是固定的。
要求逆序数相等的串顺序不便。
复习下不同排序算法。
Read the rest of this entry »
由‘a'到‘z'组成的长度不超过10的的字符串序列(字符不重复，且按字典序排序，否则输出0）word所在的位置。
例：a = 1; b = 2; …… z = 26;
ab = 27, …… az = 51;
bc = 52, ……vwxyz = 83681;
思路：组合数学com(n, m) = com(n - 1, m) + com(n - 1, m - 1)的应用。
Read the rest of this entry »
n 个人围成一桌，现在要调换座位，使得每个人的左右邻居呼唤，问要调换多少次。
如果所有人是线性排列,那我们的工作就是类似冒泡程序做的工作,,1,2,3,4,5变为5,4,3,2,1 ,耗时n(n-1)/2。
但是出现了环,也就是说1,2,3,4,5变为3,2,1,5,4也可满足条件；我们可以把这个环等分成两个部分 ,每个部分看成是线性的,再把它们花的时间加起来.
当 n 是偶数时, 每份人数 n/2 ,即 (n/2-1)*(n/2)*2；当 n 是奇数时,两份的人数分别是 n/2 和 n-n/2,即(n/2-1)*(n/2)+ ((n-n/2)-1)*(n-n/2)/2。
题意：求一个实数R的n次幂 即ans = R ^ n;
方法： 模拟高精度乘法
两个大数相乘，以字符串输入，用数组a[], b[]按位存储，最终结果用另外一个数组c[]存储
核心代码：
memset(c, 0, sizeof(c)); //初始化结果数组
for(i = 0; i < l1; i++)
for(j = 0; j < l2; j++) {
c[i + j] +＝ a[i] * b[j];
c[i + j + 1] += c[i + j] / 10;
c[i + j] %= 10;
}
此题方法，将小数点额外运算，计数小数点的最终位置，运用多次大数相乘，计算结果。
1929年10月24日星期一，美国纽约股市出现暴跌，而全球也进入了长达十年之久的大萧条，黑色星期一由此得名。但就在那个黑色星期一来临之前的一个多月，全美第四大零售商Bamberger的老板，高位套现转让了所持全部股份。大萧条来临时，他想也许该为苦难的美国人做些什么。他拜访了一个医生，希望能捐献一座医院，但后者却建议他能建立一个像柏拉图学院那样的知识分子的伊甸园，这就是美国普林斯顿高等研究院的来历。爱因斯坦是被缴请来的首席教授。所有终身教授都被免除作为凡人的许多烦恼，比如交水电费这样的家务活，而且一旦进入研究院，你就得到了完全的信任，可以按自己的兴趣研究，哪怕你经常在喝咖啡、下棋或闲聊。据说最后完成费马大定理（不可能将任何高于2次的幂写成两个同次幂的和）证明的英国数学家怀尔斯，在那里七年没有发表一篇论文。这个故事对大部分中国人来说可能显得比较陌生，虽然据说Google内部也按这个原则设计，十米之内一定可以找到食物，有游池，提供按摩服务，所以公司的一个按摩师在股份解禁后，套现成了百万富翁。
2008年全球也经历了类似1929年的大危机，但很快市场却顽强地止跌，并开始恢复。现在虽然最后答案尚未完全揭晓，不过中国股市的表现预示着市场可能进入一个崭新阶段。这个阶段对大部分个人投资者来说也许就像上文的故事一样是陌生的，突出的表现是赢利难，题材多，股票不认识。对于专业投资者来说，面对如长江潮水一般的新股，最勤奋的投资者还在试图了解每个新上市的公司，但随着时间的推移，相信投资者一定会放弃了解每一个公司的企图。也就是说新阶段股市一个结局是投资者必定要适应在一个海量股票的陌生市场，过去主导股市涨跌的主要因素也会出现根本的变化。
首先是股市的齐涨齐跌至少在现在很难出现。过去的股市由于股票短缺，所以牛市和熊市泾渭分明，牛市到来时，所有股票鸡犬升天。但随着全流通，尤其是海量股票出现后，这种局面应该会发生很大变化。其实今年股票虽然大盘跌了不少，但赢利股票实在为数不少，如果不是新股上市定价偏高，赢利股票的数量还会增加不少。
其次股市上涨空间主要由新兴行业决定。新兴行业主要包括三类，一个是最纯粹的新兴行业，如新能源、新能源汽车、低碳经济及移动互联等，全球同步发展，中国企业很有可能在这些新兴行业率先达到全球领先水平。第二类是因中国转变经济增长而出现机会的高科技、高附加值产业，如精细化工里的电子化学和化学中间体、水处理和固废处理等。这些新兴行业的名单会非常多。第三类是中消费升级相关的企业，包括新医药、新消费、新农业等等。目前这类公司占中国股市总市值不大，可能只有20%，但随着时间推移，也许五年后，这三类公司占中国股市总值的比重会超过50%，到那个时候，中国股市将完成质变，蓝筹股票的行业特征将与发达国家类似，也预示着中国经济转型走上正途。如果那时市场比较乐观，什么股票都涨的大牛市或许会重新再来。
最后股市从时势造英雄转变为英雄造时势。新兴行业与传统行业在核心竞争力上最大的不同是传统行业更依靠各种资源或垄断，而新兴行业更依靠人力资源及创新。所以以前经济高涨时，牛股都成批出现，个股之间差异不是太大。而新兴行业则完全不同，就像没有微软就没微机时代，没有苹果就没有现在移动互联的兴起一样，新兴行业是因为一个优秀企业的出现，才创新出一个行业，而个人又是创新的关键。上文的小故事也许可以看成是20年后美国成为全球霸主的必要准备，同样，中国经济转型的过程也一定是中国经济放松管制及企业在技术和经营模式上不断创新的过程，虽然过程会非常曲折，但相信投资者一定不想错过英雄造时势的精彩。
1,2,3,4，。。。入栈，给定一些出栈序列，问哪些是合法的出栈序列。
Read the rest of this entry »
最小生成树问题。prim 或者基于并查集的 kruskal 算法都可，将已有路径的权值置为 0 。
Read the rest of this entry »