CCF CSP 201903-3.损坏的RAID5

---

分析：

本题的难点在于读懂题目>_<。

定义哈希表disks，用于存储输入的磁盘信息。disks以磁盘的顺序号为键，以该磁盘上存储的数据为值。

阵列中的条带大小为s（单位：块），现存的硬盘数目为l。

1.块、条带、磁盘均从0开始连续编号。

2.块的大小是4个字节，而输入的是16进制数字。1个字节需要用2个16进制数字表示，因此，1个块中的数据需要用8个16进制数字表示。

3.编号为b的块，在阵列中的条带编号band为
$$
band = \left \lfloor \frac {b}{s} \right \rfloor
$$
4.编号为band的条带，所在的磁盘编号diskId为
$$
diskId = band \ \% \ 磁盘数量
$$
5.“对于有(n+1)块硬盘的RAID5存储，我们利用每块硬盘上编号为k的条带，存储编号为[kn, (k+1)n)的条带（共n个）。”编号为band的条带，在磁盘diskId上的条带编号k为
$$
k = \frac{band}{n} = \frac{条带编号}{磁盘数量-1}
$$
6.阵列中编号为b的块，在磁盘diskId上的块号block为
$$
block = k \times s + b \ \% \ s
$$
7.如果读操作由于下列情形之一无法进行，则输出一个减号（-）：

（1）阵列不完整，且被读取的块所在的硬盘缺失，且该数据无法由现存的硬盘数据推算出来，即 disks不包含diskId && n - l > 1；

（2）指定的块超出阵列总长度，即(block + 1) * 8 > diskId上存储的数据的长度

8.如果disks包含块b所在的磁盘编号diskId，则直接输出块block中存储的数据；否则，需要对其他磁盘上第block块中存储的数据进行异或运算。

9.由于磁盘数量n的最大值为$10^3$，而每块硬盘上的数据长度小于40KB（$40 \times 1024 \times 2 \approx 8 \times 10^4$个字符）。因此，输入的磁盘数据将多达$8 \times 10^4 \times 10^3 = 8 \times 10^7$个字符。因此，在C++中使用scanf或者cin（Java中使用Scanner）读取数据，都将会出现运行超时。

实践发现：在C++中，使用fgets读入磁盘存储的数据；在Java中，使用BufferedReader，能够正确通过所有的测试用例。

• C++版

#include <cstdio>
#include <map>
#include <string>

using namespace std;

// 将十六进制字符串转换为十进制整数
int toDecimal(string s) {
	int result = 0;
	for (int i = 0; i < s.size(); i++) {
		result *= 16;
		if ('A' <= s[i] && s[i] <= 'Z') {
			result += s[i] - 'A' + 10;
		} else {
			result += s[i] - '0';
		}
	}
	return result;
}

const int MAX = 40 * 1024 * 2 + 1;
char str[MAX];

int main() {
	int n, s, l, m, b;
	scanf("%d %d %d", &n, &s, &l);

	map<int, string> disks;
	int index;
	string content;
	for (int i = 0; i < l; i++) {
		scanf("%d", &index);
		getchar();
		// 最大输入为40kb，如果使用scanf或者cin，会超时
		fgets(str, MAX, stdin);
		content = str;
		disks[index] = content;
	}

	scanf("%d", &m);
	while (m--) {
		// 读取的块编号
		scanf("%d", &b);
		// 块b所在的条带编号
		int band = b / s;
		// 块b所在的磁盘编号（编号从0开始）
		int diskId = band % n;
		// 条带band，在磁盘diskId上的条带编号（编号从0开始）
		int k = band / (n - 1);
		// 块b，在磁盘diskId上的块号（编号从0开始）
		int block = k * s + b % s;

		// 1.被读取的块所在的硬盘缺失，且该数据无法由现存的硬盘数据推算出来;指定的块超出阵列总长度。
		if ((!disks.count(diskId) && n - l > 1)
				|| (block + 1) * 8 > disks[diskId].size()) {
			printf("-\n");
			continue;
		}
		// 2.磁盘数据完好
		if (disks.count(diskId)) {
			printf("%s\n", disks[diskId].substr(8 * block, 8).c_str());
			continue;
		}
		// 3.磁盘数据缺失，但可以由现存的磁盘数据推算出来
		int result = 0;
		for (map<int, string>::iterator iter = disks.begin();
				iter != disks.end(); iter++) {
			string str = iter->second.substr(8 * block, 8);
			if (iter == disks.begin()) {
				result = toDecimal(str);
			} else {
				result ^= toDecimal(str);
			}
		}
		printf("%08X\n", result);
	}
	return 0;
}

• Java版

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

public class Main {

	public static void main(String[] args) throws IOException {
		// 读入的字符数量过大，使用Scanner会超时
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sArr = br.readLine().split(" ");
		int n = Integer.parseInt(sArr[0]);
		int s = Integer.parseInt(sArr[1]);
		int l = Integer.parseInt(sArr[2]);

		Map<Integer, String> disks = new HashMap<>();

		for (int i = 0; i < l; i++) {
			String[] sArr2 = br.readLine().split(" ");
			int index = Integer.parseInt(sArr2[0]);
			String content = sArr2[1];
			disks.put(index, content);
		}

		int m = Integer.parseInt(br.readLine());
		for (int i = 0; i < m; i++) {
			// 读取的块编号
			int b = Integer.parseInt(br.readLine());
			// 块b所在的条带编号
			int band = b / s;
			// 块b所在的磁盘编号（编号从0开始）
			int diskId = band % n;
			// 条带band，在磁盘diskId上的条带编号（编号从0开始）
			int k = band / (n - 1);
			// 块b，在磁盘diskId上的块号（编号从0开始）
			int block = k * s + b % s;

			// 1.被读取的块所在的硬盘缺失，且该数据无法由现存的硬盘数据推算出来;指定的块超出阵列总长度。
			if ((block + 1) * 8 > disks.get(diskId).length() || (!disks.containsKey(diskId) && n - l > 1)) {
				System.out.println('-');
				continue;
			}
			// 2.磁盘数据完好
			if (disks.containsKey(diskId)) {
				System.out.println(disks.get(diskId).substring(8 * block, 8 * (block + 1)));
				continue;
			}
			// 3.磁盘数据缺失，但可以由现存的磁盘数据推算出来
			int result = 0;
			boolean flag = false;
			for (Entry<Integer, String> entry : disks.entrySet()) {
				String str = entry.getValue().substring(8 * block, 8 * (block + 1));
				if (!flag) {
					result = Integer.parseInt(str, 16);
					flag = true;
				} else {
					result ^= Integer.parseInt(str, 16);
				}
			}
			System.out.printf("%08X\n", result);
		}

		br.close();
	}
}