The Castle
问题描述：
给定一张室内平面图，图上画着不同的房间，房间用墙间隔，（1）请计算图中房间的数目。（2）最大的房间的面积。（3）拆掉哪堵墙可使得到的房间最大。输出最大面积，和要拆的墙。
初步分析：
图的表示方式很诡异—每一格用四个整数的和表示其四周墙的情况：1: 在西面有墙，2: 在北面有墙，4: 在东面有墙，8: 在南面有墙。不过可以用四个连续的if来解决(用map[i][j][0..3]表示东南西北是否有墙)
if(t>=8)
{ map[i][j][2]=true;t-=8;}
if(t>=4)
{ map[i][j][3]=true;t-=4;}
if(t>=2)
{ map[i][j][0]=true;t-=2;}
if(t==1)
map[i][j][1]=true;
数据结构设计：
一个三维布尔数组记录格子与四周的连通，用P[i][j]记录i,j格子处于哪个房间，S[2500]记录各个房间的面积，一个二维布尔数组记录格子是否被访问过。
算法设计：
既然各格的连通性已知，那么我们就需要想办法找到各个连通在一起的区域，用种子填充法可以很方便的解决这一问题，遍历整个图，如果某点未被访问，则利用广搜扩展可行的格子，统计已连通的格子数，计入S[]中。
遍历S，即可解决任务1、2。再遍历数组P，根据题目要求，从左下角开始，优先考虑上面的格子（题目有点问题）若与当前格子不属同一房间，计算S[P[i][j]]+S[P[i-1][j]]，再与右边格子做相同计算，不断更新最大值，和获得最大值所需拆的墙即可。
void BFS(Point s)
{ int i;
queue<Point> Pq;
Point current;
Pq.push(s);
int Count=1;
while(!Pq.empty())
{ current=Pq.front();
Pq.pop();
for(i=0;i<4;i++)
{ Point tem;
tem.c=current.c+tc[i];
tem.r=current.r+tr[i];
if(tem.c<=Col&&tem.c>=1&&tem.r<=Row&&tem.r>=1)
if(!map[current.r][current.c][i]&&!visit[tem.r][tem.c])
{ visit[tem.r][tem.c]=true;
P[tem.r][tem.c]=Sp;
Pq.push(tem);
Count++;
}
}
}
S[Sp]=Count;
}
Ordered Fractions
问题描述：
输入一个自然数N,对于一个最简分数a/b（分子和分母互质的分数）,满足1<=b<=N,0<=a/b<=1,请找出所有满足条件的分数。
这有一个例子，当N=5时，所有解为：
0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
给定一个自然数N，1<=n<=160，请编程按分数值递增的顺序输出所有解。
数据结构设计：
设计一个结构体Num：double n；int a,b; a为分子，b为分母，n为比值。Num num[]
算法设计：
比较简单，暴力枚举即可，i : 1…N, j : 1…N.利用gcd判断最大公约数是否为1，加入num[]中。最后对num根据n排序，输出num即可。
Sorting a Three-Valued Sequence
问题描述：
排序是一种很频繁的计算任务。现在考虑最多只有三值的排序问题。一个实际的例子是，当我们给某项竞赛的优胜者按金银铜牌序的时候。在这个任务中可能的值只有三种1，2和3。我们用交换的方法把他排成升序的。
写一个程序计算出，给定的一个1,2,3组成的数字序列，排成升序所需的最少交换次数。
数据结构设计：
必然得有个数组记录给出的数据，再设立一个二维数组S[4][4]，作用在下面会讲到。
算法设计：
利用样例分析可知，有些数字只需互换其位置就可以保证它们处于应在的位置。而其余数字最多只需交换两次即可到达应处位置。利用S[i][j]记录在i数字段出现数字j的个数，比如S[1][2]表示在1应该出现的区域里出现2的次数，则min{S[1][2],S[2][1]}即为交换一次就能使1回到1段2回到2段的情况的个数，找到所有属于情况一的个数后，剩余的未处于原位的数字的个数必然是三的倍数（观察可知），除以3得到情况二的个数，情况一的个数加上情况二的个数的两倍就是答案。
Healthy Holsteins
问题描述：
给出牛所需维生素种数，和所需量。以及饲料种数，每种饲料提高的维生素含量。每种饲料只能用一份。求出使牛达到营养需求的最少饲料种数，并输出所需饲料。
初步分析：
显然是要求出最理想的饲料组合，一般可以用BFS和DFS，利用BFS可以很容易地找出满足最少饲料种数的解，对于此题来说，每种饲料只能用一份，所以个人认为，用DFS方便一点。
数据结构设计：
两个个布尔数组，一个标记是否使用，另一个用以记录答案。int Vneed[26],Vkind;记录维生素需求及种数。int Ttype,Tpro[16][26];记录饲料种数，和各种饲料提供的维生素含量。
算法设计：
DFS(int dep,int d) dep表示已用的饲料种数，d表示最后一项用的饲料号数。剪枝：如果dep>Ttype显然不可能，返回；如果dep>ans则已经有更优的答案了，返回；判断当前解是否满足题意，满足则与ans比较，更新答案；接着从d+1起搜索未使用过的饲料号数，接下来就是朴素的DFS，没什么好说的了。
Hamming Codes
问题描述：
给出 N，B 和 D：找出 N 个编码（1 <= N <= 64）（实际评测中2 <= N <= 60），每个编码有 B 位[二进制]（1 <= B <= 8），使得两两编码之间至少有 D 个单位的“海明距离”（1 <= D <= 7）。“海明距离”是指对于两个编码，他们的二进制表示法中的不同二进制位的数目。
初步分析：
数据的范围不是很大，暴力枚举即可得出结果。
算法设计：
设计一个函数F统计两个数的海明码。先把0作为答案放入答案数组中，i从一开始枚举，调用函数F比较i和答案数组中的数的海明码是否大于等于D，满足则加入答案数组中，找到N-1个数就退出，
下面是函数F：
int cmp(int a,int b)
{ int ta,tb;
int Count=0;
while(a||b)
{ ta=a%2;
tb=b%2;
if(ta!=tb)
Count++;
a/=2;b/=2;
}
return Count;
}