* On every 1 cm x 1 cm square of the board, a 1 cm x 1 cm block is placed.
This block has some integer height B (1 <= B <= 1,000,000,000)
The blocks are all glued together carefully so that punch will not drain through them. They are glued so well, in fact, that the corner blocks really don't matter!
Dr.Kong can never figure out, however, just how much punch their bowl designs will hold. Presuming the bowl is freestanding (i.e., no special walls around the bowl), calculate how much juice the bowl can hold. Some juice bowls, of course, leak out all the juice on the edges and will hold 0.
【Standard input】
* Line 1: Two space-separated integers, W and H
* Lines 2..H+1: Line i+1 contains row i of bowl heights: W space-separated
integers each of which represents the height B of a square in the bowl. The first integer is the height of column 1, the second integers is the height of column 2, and so on.
【Standard output】
* Line 1: A single integer that is the number of cc's the described bowl will hold. 【Sample input】 4 5 5 8 7 7 5 2 1 5 7 1 7 1 8 9 6 9 9 8 9 9
【Sample output】 12
河南省第一届ACM程序设计大赛答案
题数 类型 1 2 3 4 5 6 7 8 几何 图论 组合；分治 多重背包 模拟 贪心 深度优先搜索（剪枝） 拓扑排序（有向图） 【T1】提示：每个物资在每个圆形区域的有效性可以转化为数学公式：
(
是圆心坐标，R是半径，x、y是落点坐标)。
然后就是利用双层循环，在每个圆中探测每个投放物资的坐标点，有效则输出”YES”, 无效则输出”NO”。
【T2】解法：把相关数据存入图的边结构之后，求最小生成树。有两种简单算法供选择：Prim和Kruskal。其中，Prim算法适合求边稠密的最小生成树，而Kruskal算法适合求边稀疏的最小生成树。本题的“很多基站之间不能直接建立通信”说明边是稀疏的，那么选择Kruskal算法。
先对各个边按照权值进行升序排序，然后把各个顶点各自归为一组。依次取出各条边的两个顶点编号，判断是不是同一组：若两个顶点不在一组则可加入最小生成树，标记这条边加入了最小生成树；若两个顶点在一组（会构成回路）则放弃这条边。由于各条边已经按照权值递增排序，最后被标记为最小生成树的一边的所有边的权值之和则为题中所求最小代价。最后计算最小生成树中各条边的权值总和并输出。
【T3】提示：对所有可能的钥匙组合进行穷举是个方法，但应该注意到：要求两个钥匙的长度之和恰好为此密码的长度，那么其中一把钥匙的长度必定大于等于密码长度的一半。先对钥匙进行升序排序，然后使用二分搜索法定位到第一个大于L/2(L为密码的长度)的元素位置，得到相邻两钥匙的长度之和and，如果and大于L则向左端搜索，否则向右端搜索，遇到and==L，保存两把破译的钥匙的编号。搜索完毕还没有相符的and，则无法找到破译此密码的钥匙。最后，如果相符的and只有一个，则直接输出；如果相符的and有多个，则选择起始编号最小的一组数据输出。
【T4】提示：多重背包问题描述是这样的，有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
【T5】提示：对于每一个灾区，如果没有达到平均水平，则分别向左右（注意环形）搜索到最近的超过平均水平的灾区，并索取物资
【T6】提示：比勇士先出发的不用管了（一定不会跟在他们后面），勇士会跟着在他之后出发的并且最先到达目的地的士兵一块到达。
【T7】提示：对这些木棍逆序排序，然后假定最长的木棍为最优解，检查是否可以砍断为这些木棍，如果不行，长度加1继续检查。检查过程是：从这些木棍中选取第一个（最长的）开始尝试组合第一根棍子，如果不够长，加入下一根，直到组合成功，接着组合下一根棍子。
【T8】提示：
1、注意拓扑排序只在有向无环图中有效，关键在于要在每次输入关系后做一次有无环的判断。
：如果已经输入的有向图中的点,不存在入度为0的点,则该有向图存在回路
：如果已经输入的入度为0的点大于一个,则该有向图肯定不存在一个可以确定的拓扑序列但并不妨碍拓扑排序，还要检测是否已经出现了环（存在回路）。
2、还可以使用深度优先搜索来实现拓扑排序，根据每个结点的结束访问时间的降序对结点进行拓扑排序，如果在某个结点的扩展过程中发现反向边，则出现了矛盾；否则对所得到的结点序列，进行一次遍历，对于相邻的结点检测是否存在连接边（存在则表示它们的顺序已经可以确定），如果所有的相邻结点都可确定顺序，则这个序列是完全有序的，对于后面的输入可以忽略；如果处理完所有的输入还不能得到完全有序序列，则输出序列顺序不能确定。 3、Warshall算法（求二元关系的传递闭包），但时间复杂度为O(n3)。
河南省第二届ACM程序设计大赛答案
题数 类型 1 2 3 4 5 6 7 8 最短路径（广度优先搜索） 模拟 树形DP；数学推导 数论（置换群） 关键路径 数论（进制转换） 二叉排序树（递归） 记忆化搜索 【T1】提示： 1、BFS，从A到B求最短路径（每条边的权值为1），可以采用Dijkstra算法（需要遍历计算的节点相当多，效率较低），利用BFS，构造队列，从A遍历到B的步数即最优解。 2、其实，求最短路径的方法有很多：Dijkstra算法、A*算法、SPFA算法、Bellman-Ford算法和Floyd-Warshall算法，各有各的优势，选择一个合适的就行。 【T2】提示：可以使用链表结构，在Java中可以利用Vector来模拟操作这些构件（保存编号、所在层数等信息），完成所有搬动后，取出顶层的编号。 【T4】提示：此题类似于“篝火晚会”，只是需要排序得到元素有序序列，而且是直线型的，剩下的工作就是对比原序列与有序序列，利用置换群找出交换难度小（交换对象的值*交换次数）的方案。 【T6】提示：很明显的九进制，只是不是真正的9进制，0~9缺少4，那么可以对每一位数字做处理，大于4的减1，使得每一位数字0~8，构造成9进制的数，在转换为十进制的数字输出即可。 【T7】提示：很容易推出递推公式：f[x]=f[l[x]]*f[r[x]]*combination(s[x]-1,s[l[x]]),问题的关键不在递归，而在算combination.即两个大数的商对9901的模。这需要用到乘法逆元，也是刚刚学会的： 若有b*x% M =1 ,则有 a/b % M = a/b * (b*x) %M=a*x % M. x称为b的乘法逆元。 【T8】 #include
inline int max (int a, int b) { if (a > b) return a; else return b; } inline int min (int a, int b) { if (a < b) return a; else return b; } const int mi = 19931117;
inline unsigned int onec (unsigned int x) {
x = (x & 0x55555555) + ((x >> 1) & 0x55555555); x = (x & 0x33333333) + ((x >> 2) & 0x33333333); x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F); x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF); x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF); return x; }
int mem[300010];
char si[21], ti[21]; int slen, tlen; int kmp[21][21], ttos[21];
void kmpinit (int *ka, char *st) {
int i, j;
ka[0] = -1;
for (i = 1; st[i - 1]; i++) {
j = ka[i - 1]; while (j != -1) {
if (st[i - 1] == st[j]) break; j = ka[j]; }
ka[i] = j + 1;
} }
int maxtogo[300010][21]; bool called[300010]; void calmax (int serial) {
int i, j, k, m, r = onec(serial),*opt = maxtogo[serial]; if (called[serial]) return; for (i = tlen - 1; i >= 0; i--) {
if (serial & (1 << i)) opt[i] = -1; else opt[i] = opt[i + 1] + 1; if (opt[i] == 0) opt[i]++; }
for (i = 0; i < tlen; i++) {
if (opt[i] == -1) continue; else {
m = ttos[i];
k = 0; for (j = 0; j < tlen && m < opt[i] && m < r; j++) {
if (serial & (1 << j)) {
while (k != -1 && ti[j] != ti[i + k]) k = kmp[i][k]; k++;
m = max(m, k); }
else k = 0; }
k = 0; for (j = tlen - 1; j >= 0 && m < opt[i] && m < r; j--) {
if (serial & (1 << j)) {
while (k != -1 && ti[j] != ti[i + k]) k = kmp[i][k]; k++;
m = max(m, k); }
else k = 0; }
opt[i] = min(m, opt[i]); } }
called[serial] = true;
}
int dfs (int curs) {
int tars, i, j, nrt, prlen, *opt = maxtogo[curs], ans = mi; if (mem[curs] >= 0) return mem[curs];
if (curs == (1 << tlen) - 1) return mem[curs] = 0; calmax(curs); prlen = 0; for (i = 0; i < tlen; i++) {
if (opt[i] == -1) {
prlen = 0; continue; }