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;
}