题目描述题目要求验证和恢复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表示不可用需要判断数据是否有效若有效则恢复所有数据并转换为十六进制输出。输入格式每个数据集包含第一行三个整数磁盘数ddd2≤d≤62 \le d \le 62≤d≤6、块大小sss1≤s≤641 \le s \le 641≤s≤64、每磁盘块数bbb1≤b≤1001 \le b \le 1001≤b≤100。第二行一个字符E偶校验或O奇校验。接下来ddd行每行s×bs \times bs×b个字符0、1或x表示该磁盘上所有位的值高位在前。输入以d0d 0d0结束。输出格式对于每个数据集输出一行若有效输出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索引的奇偶校验块位置为pi mod dp i \bmod dpimodd。每个位位置jjj000到s−1s-1s−1的ddd个位构成一组。处理流程对于每列iii和每个位位置jjj收集ddd个磁盘的对应位统计x的数量和位置。若x数量≥2\ge 2≥2则数据无效。若x数量1 11则根据奇偶规则恢复该位异或所有已知位后确定缺失位的值。若x数量0 00则验证异或结果是否符合奇偶规则。若不符合则数据无效。将所有非校验块的数据位收集起来按顺序拼接成二进制字符串。末尾补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//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases0;intdisk,size,block;charparity,bit;charhexadecimal[]{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F};while(cindisk,disk0){cinsizeblockparity;vectorvectorstringdata(block,vectorstring());// read input.for(inti0;idisk;i)for(intj0;jblock;j){string bits;for(intk0;ksize;k){cinbit;bitsbit;}data[j].push_back(bits);}boolvalidtrue;string content,hexText;// p is the index of parity block.for(inti0,p0;iblock;i,p,p%disk){for(intj0;jsize;j){string bits;for(intk0;kdisk;k)bitsdata[i][k][j];intunavailableBits0,unavailableIdx-1;for(intx0;xbits.size();x){if(bits[x]x){unavailableBits;if(unavailableIdx-1)unavailableIdxx;}}// too many unavailable bitsif(unavailableBits2){validfalse;gotoprint;}// reconstructe unavailable bitelseif(unavailableBits1){// replace the unavailable bit and checkbits[unavailableIdx]1;intrbits.front()-0;for(intx1;xbits.size();x)r^(bits[x]-0);if((parityEr1)||(parityOr0))bits[unavailableIdx]0;// setdata[i][unavailableIdx][j]bits[unavailableIdx];}// check parity error or notelse{intrbits.front()-0;for(size_t x1;xbits.size();x)r^(bits[x]-0);if((parityEr1)||(parityOr0)){validfalse;gotoprint;}}}// merge all data block but prity blockfor(intj0;jdisk;j)if(j!p)contentdata[i][j];}// translate the binary text to hexadecimal text.while(content.size()%4!0)content0;for(inti0;icontent.size();i4)hexTexthexadecimal[stoi(content.substr(i,4),0,2)];// output.print:coutDisk set cases;if(valid)cout is valid, contents are: hexText\n;elsecout is invalid.\n;}return0;}