Felix021

from http://hi.baidu.com/trooper/blog/item/ad377fd9ee6d072d10df9bc2.html

p.s. Felix终于看懂了, 建议先看看RMQ的实现算法之sparse table

一、最近公共祖先(Least Common Ancestors)

对于有根树T的两个结点u、v，最近公共祖先LCA(T,u,v)表示一个结点x，满足x是u、v的祖先且x的深度尽可能大。另一种理解方式是把T理解为一个无向无环图，而LCA(T,u,v)即u到v的最短路上深度最小的点。

这里给出一个LCA的例子：

一个类的两个实例A.B之间是可以访问对方的私有元素的。
示例程序：

WOJ1041 MagicForest解题报告 By Felix021

题目路径: http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1041

描述：给出一个N*N的矩阵，每个格子有a, p, r, d, k 5种状态，需要从p出发点到a点，初始生命值为2，r是一般通路，d使生命值减1，k使生命值减到0。问是否可以从p点走到a点。

分析：显然这是一道搜索题，搜索从p到a的路径。在搜索的过程中遇到d生命值减1，遇到k则视为无路径。由于生命值存在0、1、2三种状态，所以不能像走普通的迷宫那样来简单标记某个格子是否可走，而是要用更复杂些的规则来判断一个格子是否需要走：如果曾经有一次以不比当前值低的生命值走过这个这个格子，那么就没有必要再走一次，否则有必要。实现方法是建立一个初始化为0的二维数组，在每次通过某个格子的时候，比较历史走过此格子的最高生命值和当前生命值，如果历史最高生命值不低于当前生命值，则忽略此路径，否则继续此路径。由于本题不要求最短路径，而且可能需要完全的搜索，所以BFS和DFS都可以。

代码如下：

08年6月开发语言排行榜


1、Java           (20.0%)
2、C               (15.5%)
3、C++           (10.8%)
4、PHP           (10.2%)
5、Visual Basic  (9.8%)
6、Perl           (5.5%)
7、Python     (4.9%)

  武大计算机学院教C语言时用的IDE都是TurboC2，矬的让人无语，于是学长们都推荐Devcpp，但是Devcpp和TurboC2不一样，TurboC2提供一个UserScreen，运行完可以切换回去查看运行时的输出，但是Devcpp编译出的是32位控制台程序，运行的时候由Windows提供一个控制台界面，在程序运行完后就退出，于是很多大一新生刚开始用Devcpp总是要问，怎么Devcpp一运行就退出啊，怎么让Devcpp停在结果页面啊——首先要纠正，主语不应该是Devcpp，而是Devcpp编译出的程序。其实解决办法很简单。
  最简单的解决办法是，在程序的最后加上一句 getchar(); 就行了。但是如果程序在运行过程中有输入，这一招就不灵。因为scanf函数读取键盘输入的缓冲区的时候不会读取用户最后按下的回车('\n')，所以在缓冲区还有一个回车字符，这个字符会被getchar()读取，所以如果有输入的话这一招就不够灵了。不过可以打个补丁——用两个gerchar()即可。
  稍微麻烦一点的解决办法是使用system("pause")。在C语言中system()函数包含在头文件"stdlib.h"中，用途是执行一条命令行下的命令，效果相当于你在命令提示符下执行一条命令。而system("pause")的意思就是执行一条pause命令，于是程序会输出一行"Press any key to continue..."并等待你的按键。注意一定要在源文件前面加上 #include
  最矬最简单的办法是 while(1); 。死循环可以让程序停住，按下CTRL+C就可以退出，但是这是很不好的习惯，尽量不要这么用。

WHUACM 20080608 DAY4个人赛A题

描述：通配符*代表0个或多个字符，?代表不多不少正好一个字符。*和?的某些组合是等价的，比如*??*和?*?等价。给出一串只包含a-z、A-Z、*、?的字符串，把它转换成最短小的等效字符串——注意这里的小：比如*?比?*小。

分析：

WHUACM 20080608 Day4个人赛B题

描述：在一个N*M的矩阵中有两个人AB分别处于行列都不相同的两个位置。AB轮流走动，可以在棋盘范围内上下左右走任意步数。若某个人停在或走过对方当前所在的行或列，则对方赢。给出矩阵的大小和AB的初始位置，A先走，如果AB都尽可能走好，问谁会赢。

分析：

WHUACM 20080608 Day4个人赛C题

描述：给出图的顶点数以及每个顶点的度数（每两个顶点之间最多只有一条边），证明该图的存在性。

证明：
将图的顶点按度数排序，找到度数最大的顶点（设度数为n0）
去掉这个顶点，同时使接下来n0个顶点的顶点数减一。
重复上述步骤，直至剩余顶点的度数都为0，则图存在，否则图不存在。

C代码: