B01:篮球联赛
描述
校篮球队每年都会举办“年级联赛”。篮球队的队员们将根据年级分为一年级、二年级、三年级和四年级4支队伍，参与角逐。
在年级联赛中，不同队伍两两之间比赛一场，胜者积1分，负者积0分（篮球比赛无平局）。最终队伍将按照积分从高到低排名，若出现同分，则年级较低的排名靠前。
现在年级联赛正在进行中，有些比赛已经结束，有些比赛则因种种原因还未进行。请你根据当前的比赛情况，计算出一年级队在联赛结束后，有可能得到的最高名次。
输入输入包含多组数据。第一行是一个整数T(1 <= T <= 100)，表示数据组数。
对于每组数据，用一个4*4的字符矩阵表示当前的比赛情况。第i行第j列表示i年级与j年级的比赛情况，其中：
“-”表示i与j相同，无比赛
“W”表示i年级胜j年级
“L”表示i年级负j年级
“?”表示i年级和j年级的比赛还未进行
输入
数据保证正确不存在矛盾，且无多余空格或空行。
输出
对于每组数据，输出一个整数，即一年级队在联赛结束后，有可能获得的最高名次。
样例输入
2
-LL?
W-L?
WW-L
??W-
-WL?
L-?L
W?-L
?WW-
样例输出
3
1
1 #include <cstdio> 2 #include <string> 3 #include <memory> 4 #include <algorithm> 5 #include <stdlib.h> 6 #include <math.h> 7 #include <iostream> 8 using namespace std; 9 10 int main() 11 { 12 int t; 13 scanf("%d", &t); 14 while (t--) { 15 char info[5][5]; 16 int point[5] = { 0 }; 17 for (int i = 1; i <= 4; i++) 18 for (int j = 1; j <= 4; j++) 19 { 20 cin >> info[i][j]; 21 if (j > i) 22 { 23 if (info[i][j] == 'W') 24 point[i]++; 25 else if (info[i][j] == 'L') 26 point[j]++; 27 } 28 } 29 int notdefined[4][3],h=1; 30 for(int i=1;i<=3;i++) 31 for(int j=i+1;j<=4;j++) 32 if (info[i][j] == '?') { 33 if (i == 1) 34 point[1]++; 35 else if (point[i] > point[1]) 36 point[i]++; 37 else if (point[j] > point[1]) 38 point[j]++; 39 else 40 notdefined[h][0] = i,notdefined[h][1]=j,notdefined[h++][2]=0; 41 } 42 int _point[5], ans = 4; 43 for (int i = 1; i <=1<<(h-1); i++) { 44 int tmp = 1; 45 notdefined[1][2]++; 46 while (notdefined[tmp][2] > 1) { 47 notdefined[tmp][2] = 0; 48 tmp++; 49 notdefined[tmp][2]++; 50 } 51 for (int j = 1; j <= 4; j++) 52 _point[j] = point[j]; 53 for (int j = 1; j <= h - 1; j++) { 54 if (notdefined[j][2] == 1) 55 _point[notdefined[j][0]]++; 56 else 57 _point[notdefined[j][1]]++; 58 } 59 int _ans = 1; 60 for (int i = 2; i <= 4; i++) 61 if (_point[i] > _point[1]) 62 _ans++; 63 ans = min(_ans, ans); 64 } 65 printf("%d ", ans); 66 } 67 return 0; 68 }
实现得不怎么样，除了这种笨拙的枚举以外想不到还有什么方法了
B02:夺宝探险
描述
你无意中发现了装满了宝藏的迷宫，你想要获得尽可能多的宝藏，但是迷宫里的机关阻碍了你的计划。迷宫的地面是M行N列的矩形网格，每格是一块带有机关且放置了1个宝藏的地砖，宝藏一共有K种，用1-K表示其种类，迷宫的入口只有一个，为迷宫的第一行第一列。地砖的机关如下：
1. 每次你只能踏到你与你所在地砖相邻的地砖上（即前后左右4块）；
2. 当你踏上某块地砖后，其上的宝藏（假设种类为k）自动归属你，同时所有放置了种类为k的宝藏的地砖碎裂，你无法踏上，你当前所在的地砖在你离开后也会立刻碎裂；
3. 当你无路可走的时候，你会被传送回迷宫出口，无法再进入迷宫。
你想知道你最多能获得多少宝藏。
输入
输入的第一行是三个用空格隔开的整数，分别是M、N和K（1 <= M,N <= 20, 1 <= K <= 100）
之后是M行，每行包含N个范围为1-K的整数，用空格隔开，表示放置的宝藏种类
输出
只有一行，为一个整数，表示最多能获得的宝藏个数。
样例输入
3 4 5
1 2 3 3
2 1 4 3
1 5 1 2
样例输出
4
1 #include <cstdio> 2 #include <string> 3 #include <memory> 4 #include <algorithm> 5 #include <stdlib.h> 6 #include <math.h> 7 #include <iostream> 8 #include<queue> 9 using namespace std; 10 11 int m, n, k,ans; 12 int map[25][25]; 13 int dir1[4] = { 0,0,1,-1 }, dir2[4] = { 1,-1,0,0 }; 14 15 struct node { 16 int x, y; 17 bool visited[105]; 18 int kind; 19 node(int _x, int _y) { 20 x = _x,y=_y; 21 kind = 0; 22 } 23 }; 24 queue<node> all; 25 26 void bfs() { 27 while (!all.empty()) { 28 node now = all.front(); 29 all.pop(); 30 for (int i = 0; i < 4; i++) { 31 int xx = now.x + dir1[i], yy = now.y + dir2[i]; 32 if (map[xx][yy] < 1 || now.visited[map[xx][yy]] == 1) 33 continue; 34 node newone(now); 35 newone.x = xx, newone.y = yy; 36 newone.visited[map[xx][yy]] = 1; 37 newone.kind++; 38 ans = max(ans, newone.kind); 39 all.push(newone); 40 } 41 } 42 } 43 44 int main() 45 { 46 scanf("%d%d%d", &m, &n, &k); 47 for (int i = 1; i <= m; i++) 48 for (int j = 1; j <= n; j++) 49 scanf("%d", &map[i][j]); 50 node origin(1, 1); 51 origin.kind = 1; 52 for (int i = 1; i <= k; i++) 53 origin.visited[i] = false; 54 origin.visited[map[1][1]] = 1; 55 all.push(origin); 56 bfs(); 57 printf("%d ", ans); 58 return 0; 59 }
用广搜似乎有点慢
深搜不知道怎样 我永远都判断不了深搜的速度到底有多慢……
B03:寻找边缘
描述
给定一张 R*C 的地图，由 "X" 和 "O" 组成。
现在需要重新处理这张地图，找到地图边缘的那些 "O"。你需要将这些地图边缘上的 "O" 保留下来，然后将其他的 "O" 全部替换为 "X"。
地图边缘的 "O" 指的是那些处于第一行/列或最后一行/列上的 "O"，以及从这些 "O" 的相邻位置（上下左右）延伸出去的 "O"。
输入
第一行是一个正整数 T，表示一共有 T 组数据。
对于每组数据，其第一行是两个正整数 R 和 C，表示地图的大小，用一个空格分开。
接下来的 R 行，每行包含了 C 个字符，分别是 "X" 或 "O"。
其中，0 < T <= 10，0 < R, C <= 500。
输出
对于每组数据，输出 R 行，每行包含了 C 个字符，分别是 "X" 或 "O"。
每组数据之间需要额外输出一个空行。
样例输入
2
2 3
OXX
XXO
5 5
XXXOX
XXXOX
XOOXX
XXOXX
XOXXX
样例输出
OXX
XXO
XXXOX
XXXOX
XXXXX
XXXXX
XOXXX
1 #include <cstdio> 2 #include <string> 3 #include <memory.h> 4 #include <algorithm> 5 #include <stdlib.h> 6 #include <math.h> 7 #include <iostream> 8 #include<queue> 9 using namespace std; 10 11 int map[505][505]; 12 int r, c; 13 int dir1[4] = { 0,0,1,-1 }, dir2[4] = { 1,-1,0,0 }; 14 int kept[505][505]; 15 16 void dfs(int x, int y) { 17 kept[x][y] = 1; 18 for (int i = 0; i < 4; i++) { 19 int xx = x + dir1[i], yy = y + dir2[i]; 20 if (kept[xx][yy] != 1 && map[xx][yy] == 1) 21 dfs(xx, yy); 22 } 23 } 24 25 int main() 26 { 27 int t; 28 scanf("%d", &t); 29 while (t--) { 30 memset(kept, 0, sizeof(int) * 505 * 505); 31 memset(map, 0, sizeof(int) * 505 * 505); 32 scanf("%d%d", &r, &c); 33 char ch; 34 for(int i=1;i<=r;i++) 35 for (int j = 1; j <= c; j++) { 36 cin >> ch; 37 if (ch == 'O') 38 map[i][j] = 1; 39 else 40 map[i][j] = 2; 41 } 42 for (int i = 1; i <= r; i++) { 43 if(map[i][1]==1&&kept[i][1]==0) 44 dfs(i, 1); 45 if (map[i][c] == 1 && kept[i][c] == 0) 46 dfs(i, c); 47 } 48 for (int i = 1; i <= c; i++) { 49 if (map[1][i] == 1 && kept[1][i] == 0) 50 dfs(1, i); 51 if (map[r][i] == 1 && kept[r][i] == 0) 52 dfs(r, i); 53 } 54 for (int i = 1; i <= r; i++) 55 { 56 for (int j = 1; j <= c; j++) { 57 if (map[i][j] == 2) 58 printf("X"); 59 else if (kept[i][j]) 60 printf("O"); 61 else 62 printf("X"); 63 64 } 65 printf(" "); 66 } 67 printf(" "); 68 } 69 return 0; 70 }
最后一行是有换行符的
深搜
B04:猴子摘桃
描述
一只猴子正在赶路，发现了一排桃树。它想去摘桃子，但桃树上可能有马蜂。幸好它带着一罐蜂蜜。每次它接近一个桃树时，只要给树上的每只马蜂一克蜂蜜，就可以放心经过和摘桃，不用担心了被蜇，否则就过不了这棵树且会蜇。幸运的是，猴子可以直接跳到任意一颗桃树开始采摘，然后就只能沿着桃树所在的直线单向走且不可跳过桃树，一旦离开桃树所在的直线就不能再回去。请问被马蜂蜇之前，猴子最多可以摘到多少桃子。
输入
包含多个案例。每个案例的第一行是一个正整数，表示猴子所带蜂蜜的重量，单位为克，接着若干行，每行两个整数，分别表示一颗桃树上的桃子数量和马蜂数量，每个案例的最后一行是两个-1。排在前面的桃树先输入。输入的最后一行是-1。(桃树的数量最大为100)
输出
每个案例输出一个整数，表示猴子被马蜂蛰之前可以摘到的最大桃子数。
样例输入
50
30 25
24 8
45 17
38 20
27 8
18 5
10 20
-1 -1
-1
样例输出
128
提示输入数据确保输入数据和计算结果均可表示为4字节的整数。
1 #include <cstdio> 2 #include <string> 3 #include <memory.h> 4 #include <algorithm> 5 #include <stdlib.h> 6 #include <math.h> 7 #include <iostream> 8 #include<queue> 9 using namespace std; 10 11 int info[105][2]; 12 int hon,sum,ans; 13 14 int main() 15 { 16 while (cin >> hon) 17 { 18 if (hon == -1)break; 19 sum = 0, ans = 0; 20 int p = 1; 21 while (1) { 22 scanf("%d%d", &info[p][0], &info[p][1]); 23 if (info[p][0] == -1)break; 24 sum++; 25 p++; 26 } 27 for (int i = 1; i <= sum; i++) { 28 int _hon = hon, peach = 0; 29 for (int j = i; j <= sum; j++) { 30 _hon -= info[j][1]; 31 if (_hon < 0) 32 break; 33 peach += info[j][0]; 34 } 35 ans = max(ans, peach); 36 } 37 printf("%d ", ans); 38 } 39 return 0; 40 }
B05:分形盒
描述
分形，通常被定义为一个粗糙或零碎的几何形状，可以分成数个部分，且每一部分都（至少近似地）是整体缩小后的形状，即具有自相似的性质。它跟分数维、自组织、非线性系统和混沌等具有非常重要的联系。
分形盒就是这样一种分形，它的定义如下：
维度是1的分形盒：
X
维度是2的分形盒：
X X
X
X X
如果已知维度是(n-1)的分形盒，那么维度是n的分形盒的递归定义如下所示：
Box(n-1) Box(n-1)
Box(n-1)
Box(n-1) Box(n-1)
你的任务是画一个维度为n的分形盒。
输入
输入包含多组测试数据。每一行包含一个正整数n表示分形盒的维度，n不大于7；最后一行是一个-1，表示输入结束。
输出
对于每组测试数据，输出要求维度的分形盒，注意X为大写字母。每组测试数据之后包含一行，改行只包含一个破折号。
样例输入
1
2
3
4
-1
样例输出
X
-
X X
X
X X
-
X X X X
X X
X X X X
X X
X
X X
X X X X
X X
X X X X
-
X X X X X X X X
X X X X
X X X X X X X X
X X X X
X X
X X X X
X X X X X X X X
X X X X
X X X X X X X X
X X X X
X X
X X X X
X X
X
X X
X X X X
X X
X X X X
X X X X X X X X
X X X X
X X X X X X X X
X X X X
X X
X X X X
X X X X X X X X
X X X X
X X X X X X X X
-
1 #include <cstdio> 2 #include <string> 3 #include <memory.h> 4 #include <algorithm> 5 #include <stdlib.h> 6 #include <math.h> 7 #include <iostream> 8 #include<queue> 9 using namespace std; 10 11 int pic[1000][1000]; 12 13 void draw(int x, int y, int dimension) { 14 if (dimension == 1) 15 { 16 pic[x][y] = 1; 17 return; 18 } 19 int epson = pow(3, dimension - 2); 20 draw(x, y, dimension - 1); 21 draw(x + epson, y + epson, dimension - 1); 22 draw(x + 2 * epson, y, dimension - 1); 23 draw(x, y + 2 * epson, dimension - 1); 24 draw(x + 2 * epson, y + 2 * epson, dimension - 1); 25 } 26 27 int main() 28 { 29 int t; 30 while (1) { 31 memset(pic, 0, sizeof(int) * 1000 * 1000); 32 scanf("%d", &t); 33 if (t == -1) 34 break; 35 draw(1, 1, t); 36 int dim = pow(3, t-1); 37 for (int i = 1; i <= dim; i++) 38 { 39 for (int j = 1; j <= dim; j++) { 40 if (pic[i][j]) 41 printf("X"); 42 else 43 printf(" "); 44 } 45 printf(" "); 46 } 47 printf("- "); 48 } 49 return 0; 50 }
复健中……好久没有编代码了……
之后的三天要沉浸在代码中惹
以上是16年的水题归类……