分析：如果点i有一个消防站，那么i到其它各点的最近距离是多少？如果点j又有一个消防站呢？如果用矩阵表示图g，用Floyd算法求出每对顶点的最短距离（直接更新图g），那么g[i]就是i点的消防站到各点的最近距离的向量。如果j点又有一个消防站，则按如下方式把g[i]和g[j]合并起来就得到各点到最近消防站的距离向量（即下面的merge函数）：
继续阅读 »
分析：在坐标点构成的图上应用最小生成树算法即可。注意几点：
1）边权是动态计算出来的
2）每对坐标之间都可以有一条边
3）由于图的顶点不再由整数标识，因此用map代替典型算法中的vector
继续阅读 »
分析：按字典序排列的n个单词构成了一个隐式的有向无环图：每个单词单词都有一条出边指向在它字典序之后的每一个单词。要在这张图里找出符合条件的最长路径包含的顶点数。简单的想法就是“暴力”回溯了：对每个顶点进行一次回溯，找出以该点开始的最长的edit step ladder——这个时间复杂度高得能上了火星！思考一下就会发现，回溯包含了大量的重复计算：假设以单词w开始的最长ladder长度为l，那么对于字典中排在w之前的每一个单词（实际上是edit step为1的那些单词），在回溯经过w时都要做同样的重复计算，浪费了大量时间。如果我们计算好了以w开始的最长ladder的长度l，那么对于w的每一个one edit step前驱顶点，其最长la
继续阅读 »
分析：假设从起点s到终点d的路径是a1->a2->..->an，这条路径上容量（权值）最小的边的权值为p，则p即为这条路径的最大容量。在所有s到d的路径中，我们要找出容量最大的一条，设其容量为P。则往返次数n可由
n * P >= T + n
继续阅读 »
分析：对图做广度优先遍历，一边对节点v着色一边检查v是否与某个已着色的临接点同色。more
```cpp
include
include
include
define RED 1
define BLACK (-1)
继续阅读 »
分析：考虑两点：
第一，国际象棋棋盘的格子由黑白两色交替填充，黑色格子里的象吃不到白色格子里的象，反之亦然。
第二，把棋盘顺时针旋转４５度，象就变成了车！虽然棋盘也从正方形变成了菱形，但其边界不难确定。
由此形成解法：首先把棋盘拆为黑、白两部分，然后旋转棋盘，接着把ｋ个象分为两组，一组ｉ个，一组ｋ－ｉ个，分别放在黑、白棋盘里，各有mb(n, i)和mw(n, k - i)种放置方法，则总的方法数为more
继续阅读 »
分析：只要注意到当n为偶数时
(a^n) mod n = (((a^(n/2)) mod n)*((a^(n/2)) mod n)) mod n
当n为奇数时
(a^n) mod n = (((a^(n/2)) mod n)*((a^(n/2)) mod n)*a) mod n
继续阅读 »
分析：若m是合数，把m分解为质因数的乘积
m=(p1^k1)(p2^k2)...(pi^ki)
对于m的每一个质因数pi，若其次数ki都不大于n!里pi的最大次数Ki，则m可以整除n!，反之则不能。
若m是质数，只要m不大于n即可整除n!；若m等于1，m可以整除任何n!。more
继续阅读 »
分析：迈开大步走当然会比较快，理想的步伐是：
1 2 3 ... N ... 3 2 1 或者 1 2 3 ... N N ... 3 2 1
但世事并非所愿，我们先来看看间距从3开始的最少步数的走法：more
间距 步数 走法
继续阅读 »
分析：如果已知深度为d - 1的k叉树(以下代称T(d-1))一共有a(k, d - 1)种标号法，那么深度为d的k叉树（以下代称T(d)）的a(k, d)如何计算？more
对T(d)来说，除去根节点，恰好有k棵T(d-1)子树，考虑到根节点的标号必须是1，则T(d)的标号方法可以分两步进行：首先把2~n的标号分成k组，每组m个，共有
继续阅读 »