The Castle
问题描述:
给定一张室内平面图,图上画着不同的房间,房间用墙间隔,(1)请计算图中房间的数目。(2)最大的房间的面积。(3)拆掉哪堵墙可使得到的房间最大。输出最大面积,和要拆的墙。
初步分析:
图的表示方式很诡异—每一格用四个整数的和表示其四周墙的情况:1: 在西面有墙,2: 在北面有墙,4: 在东面有墙,8: 在南面有墙。不过可以用四个连续的if来解决(用map[i][j][0..3]表示东南西北是否有墙)
if(t>=8)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{ map[i][j][2]=true;t-=8;}
if(t>=4)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{ map[i][j][3]=true;t-=4;}
if(t>=2)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{ map[i][j][0]=true;t-=2;}
if(t==1)
map[i][j][1]=true;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
数据结构设计:
一个三维布尔数组记录格子与四周的连通,用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)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{ int i;
queue<Point> Pq;
Point current;
Pq.push(s);
int Count=1;
while(!Pq.empty())
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{ current=Pq.front();
Pq.pop();
for(i=0;i<4;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{ 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])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{ visit[tem.r][tem.c]=true;
P[tem.r][tem.c]=Sp;
Pq.push(tem);
Count++;
}
}
}
S[Sp]=Count;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
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)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{ int ta,tb;
int Count=0;
while(a||b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{ ta=a%2;
tb=b%2;
if(ta!=tb)
Count++;
a/=2;b/=2;
}
return Count;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)