题目描述
题目要求验证和恢复RAID\texttt{RAID}RAID磁盘阵列中的数据。系统使用多个磁盘，每个磁盘被划分为若干块（block\texttt{block}block），每个块由若干位（bit\texttt{bit}bit）组成。数据块和奇偶校验块按列分布，奇偶校验块在每列中轮换位置。奇偶校验可以是偶校验（E\texttt{E}E，所有数据位和校验位的异或结果为000）或奇校验（O\texttt{O}O，异或结果为111）。输入给出每个磁盘上所有位的状态（0、1或x表示不可用），需要判断数据是否有效，若有效则恢复所有数据并转换为十六进制输出。
输入格式
每个数据集包含：
- 第一行三个整数：磁盘数ddd（2≤d≤62 \le d \le 62≤d≤6）、块大小sss（1≤s≤641 \le s \le 641≤s≤64）、每磁盘块数bbb（1≤b≤1001 \le b \le 1001≤b≤100）。
- 第二行一个字符：
E（偶校验）或O（奇校验）。 - 接下来ddd行，每行s×bs \times bs×b个字符（
0、1或x），表示该磁盘上所有位的值（高位在前）。
输入以d=0d = 0d=0结束。
输出格式
对于每个数据集，输出一行：
- 若有效，输出
Disk set X is valid, contents are: 十六进制字符串。 - 若无效，输出
Disk set X is invalid.
样例
输入
5 2 5 E 0001011111 0110111011 1011011111 1110101100 0010010111 3 2 5 E 0001111111 0111111011 xx11011111 3 5 1 0 11111 11xxx x1111 0输出
Disk set 1 is valid, contents are: 6C7A79EDF Disk set 2 is invalid. Disk set 3 is valid, contents are: FFC题目分析
本题的核心是按列处理磁盘数据，每列包含ddd个磁盘的相同位置位。奇偶校验块在该列中轮换位置，需要识别出校验块的位置，并根据校验规则恢复缺失位和验证正确性。
数据结构
将数据组织为b×db \times db×d的块矩阵，每个块是一个长度为sss的二进制字符串。按列处理：第iii列（000索引）的奇偶校验块位置为p=i mod dp = i \bmod dp=imodd。每个位位置jjj（000到s−1s-1s−1）的ddd个位构成一组。
处理流程
对于每列iii和每个位位置jjj：
- 收集ddd个磁盘的对应位，统计
x的数量和位置。 - 若
x数量≥2\ge 2≥2，则数据无效。 - 若
x数量=1= 1=1，则根据奇偶规则恢复该位（异或所有已知位后，确定缺失位的值）。 - 若
x数量=0= 0=0，则验证异或结果是否符合奇偶规则。若不符合，则数据无效。 - 将所有非校验块的数据位收集起来，按顺序拼接成二进制字符串。
- 末尾补
0使长度为444的倍数，转换为十六进制。
奇偶计算
- 偶校验：所有位的异或结果为000。
- 奇校验：所有位的异或结果为111。
复杂度分析
总数据位数为d×s×bd \times s \times bd×s×b，每个位处理一次，时间复杂度O(d×s×b)O(d \times s \times b)O(d×s×b)。
代码实现
// RAID!// UVa ID: 509// Verdict: Accepted// Submission Date: 2017-04-26// UVa Run Time: 0.010s//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases=0;intdisk,size,block;charparity,bit;charhexadecimal[]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};while(cin>>disk,disk>0){cin>>size>>block>>parity;vector<vector<string>>data(block,vector<string>());// read input.for(inti=0;i<disk;i++)for(intj=0;j<block;j++){string bits;for(intk=0;k<size;k++){cin>>bit;bits+=bit;}data[j].push_back(bits);}boolvalid=true;string content,hexText;// p is the index of parity block.for(inti=0,p=0;i<block;i++,p++,p%=disk){for(intj=0;j<size;j++){string bits;for(intk=0;k<disk;k++)bits+=data[i][k][j];intunavailableBits=0,unavailableIdx=-1;for(intx=0;x<bits.size();x++){if(bits[x]=='x'){unavailableBits++;if(unavailableIdx==-1)unavailableIdx=x;}}// too many unavailable bitsif(unavailableBits>=2){valid=false;gotoprint;}// reconstructe unavailable bitelseif(unavailableBits==1){// replace the unavailable bit and checkbits[unavailableIdx]='1';intr=bits.front()-'0';for(intx=1;x<bits.size();x++)r^=(bits[x]-'0');if((parity=='E'&&r==1)||(parity=='O'&&r==0))bits[unavailableIdx]='0';// setdata[i][unavailableIdx][j]=bits[unavailableIdx];}// check parity error or notelse{intr=bits.front()-'0';for(size_t x=1;x<bits.size();x++)r^=(bits[x]-'0');if((parity=='E'&&r==1)||(parity=='O'&&r==0)){valid=false;gotoprint;}}}// merge all data block but prity blockfor(intj=0;j<disk;j++)if(j!=p)content+=data[i][j];}// translate the binary text to hexadecimal text.while(content.size()%4!=0)content+='0';for(inti=0;i<content.size();i+=4)hexText+=hexadecimal[stoi(content.substr(i,4),0,2)];// output.print:cout<<"Disk set "<<++cases;if(valid)cout<<" is valid, contents are: "<<hexText<<'\n';elsecout<<" is invalid.\n";}return0;}
