XieNaoban's Blog
0%

算法竞赛入门经典(第2版) 4-7UVa509 - RAID!

发表于 更新于 分类于 ， 阅读次数： 评论次数：
本文字数： 2.6k 阅读时长 ≈ 2 分钟

书上具体所有题目：http://pan.baidu.com/s/1hssH0KO 代码：（Accepted，0 ms）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//UVa509 - RAID!
#include<iostream>
int d, s, b, t, times = 0;
char disk_data[7][6666], type;

inline char* disk(int x, int y, int z) {//二维数组当作三维数组使,方便运算
	return *(disk_data + x - 1) + (y - 1)*s + z - 1;
}
inline char* parity(int y, int z) {//定位到当前一行blocks的parity
	return *(disk_data + (y - 1) % d) + (y - 1)*s + z - 1;
}
void print_data() {
	int f = 1, n = 0;
	for (int j = 1;j <= b;++j) for (int i = 1;i <= d;++i) for (int k = 1;k <= s;++k) {
		if (disk(i, j, k) == parity(j, k)) continue;
		if (f == 5) {
			printf("%X", n);
			f = 1, n = 0;
		}
		n = (n << 1) + *disk(i, j, k) - 48;
		++f;
	}
	printf("%X\n", (n << (5 - f)));
}

int main()
{
	//freopen("in.txt", "r", stdin);
	while (scanf("%d", &d) && d != 0) {
		scanf("%d%d\n%c", &s, &b, &type);
		t = (type == 'E' ? 0 : 1);
		for (int i = 0;i < d;++i)
			scanf("%s", disk_data[i]);
		for (int j = 1;j <= b;++j) for (int k = 1;k <= s;++k) {//数据读取完毕,开始检测
			int sum = 0;
			bool flag = false;//0:没有x问题;1:有一个x;
			char *p;//定位x的位置
			for (int i = 1;i <= d;++i) {
				if (*disk(i, j, k) != 'x') sum += *disk(i, j, k) - '0';
				else if (flag) goto o_O;//invalid:two or more disks are unavailable for that block
				else p = disk(i, j, k), flag = true;//出现第一个x,并定位
			}
			if (flag) *p = (sum % 2 == t ? '0' : '1');//计算x
			else if (sum % 2 != t) goto o_O;//invalid:a parity error is detected
		}
		printf("Disk set %d is valid, contents are: ", ++times);//能执行完所有循环的才是真男人
		print_data();
		continue;
	o_O:printf("Disk set %d is invalid.\n", ++times);//我就是用goto了怎么着!跳出三重循环用goto多方便
	}
	return 0;
}

题意：好几块硬盘组RAID，组的方法是每个硬盘都平均划分成b个块(block)，每块硬盘的第i个块一起组成一个区域（也就是一块数据平均保存在n个硬盘里，实际上说是保存在n-1个硬盘里更合理，因为其中一块硬盘的这个区域保存的是用于数据恢复用的，名为parity block）同时不同parity还错开保存在不同的硬盘里，这样就有效防止了某个硬盘损坏导致全盘数组丢失。 而这个parity存的又到底是什么呢，是这一行每个data block对应的每个bit进行某种运算得来。运算法则可理解为，每个bit存的0或1进行相加，若结果(在我的代码里用sum表示)为偶数，parity对应bit储存为0，否则为1（even的情况。odd反过来：若为奇数储存为0。没什么意义，就是个标准不同）。 然后就是校验数据是否损坏。若直接告诉你一行里有一个损坏(表示为x)，那么没关系，可以通过其他那几个盘恢复。若一行里有俩损坏，那就没戏了。若一行没有出现x，那么所有数据相加，结果若为0（E的情况。O为1）则数据正常，否则出错。

分析：没什么特殊的思路，就一步步按照题目来呗。输入的格式和题目给的图表格式坐标是反的，比较讨厌。得用到三重循环，不同地方循环的顺序还不一样，比较绕，思路要理清了。然后三重循环跳出麻烦（因为我把其中两个循环写在了一行，这样理解上方便，代码看着也清楚，所以不方便加大括号），我就用了goto。是的我就是用goto了怎么着啦o_O！你咬我啊！在这种情况下多好用！具体算法都在代码注释里了。 还有那个print_data()函数，那个三重循环里面我本来写的是

1
2
3
4
5
6
7
8
9
for (int j = 1;j <= b;++j) for (int i = 1;i <= d;++i) for (int k = 1;k <= s;++k) {
        if (f == 5) {
            printf("%X", n);
            f = 1, n = 0;
        }
        if (disk(i, j, k) == parity(j, k)) continue;
        n = (n << 1) + *disk(i, j, k) - 48;
        ++f;
}

也就是三个步骤（是否输出、当前数据是否是parity的、是否读入数据到n）顺序不一样。我原本的目的是除了最后一个十六进制数字，其他均在三重循环里输出。理由是最后一个数据比较特殊，它有可能不满4bit，要手动添加0直至其满4bit，而且顺便要输出换行。下面这个版本有个bug，就是如果最最后一个block是parity block，那么会多输出一个0。原因很简单我就不说了，但是怎么改动我倒是想了很久，怎么改都要加变量、加好几个if，代码瞬间复杂很多，我不太情愿。最后发现只需要顺序倒一下即可！ 果然编程这个东西，顺序很重要啊。