UVA - 509 RAID!

淡淡的烟草味﹌ 2021-09-29 14:16 220阅读 0赞

/*
      这题用了挺久才彻底明白题意...值得特别注意的一点是，输入数据中，是将同一个Disk作为一个横排输入的，但是入门经典上的表格，是将同一个Disk作为一个竖列输入的...因此用了很久才明白，为什么数据会是这样 T^T
      
      题意的说明可参考：
      http://blog.csdn.net/xienaoban/article/details/52164099
      
      我的代码是参考了题解：
      http://blog.csdn.net/wcr1996/article/details/43834545
      
      一些说明：
      1.三重循环以输出十六进制的部分，十分精妙的应该时不时理清思路从头再想一次再敲一次
      
      2.注意如入门经典P98的图所示，在输出时，对同一个部分，枚举d个Disk中的s个字节数字，再进入下一部分，直到b部分循环完毕，故而循环的嵌套顺序应为：对部分的循环 => 对磁盘的循环 -> 对区间的每个bit的循环
      
      3.还有要注意下，每个磁盘是有 b*s 个bit放置数据的，在三层循环的最后一层，即确定某一个disk中的bit的位置时，借助区间数目b做乘法，会更加容易，这也是最外层循环b的真正原因
      
      自己曾经踩过/差点踩下的坑：
      1. if (i % d == j) 处，考虑到i和j的范围，千万不要把i、j弄混了，即使样例数据不会有错，但是，也要注意到 b的上限是比d要大的，在 b 大于 d的情况下若将i j 位置交换，就一定WA了 
      
    */

#include <iostream>
    #include <cstring>
    #include <cstdio>
    using namespace std;
    int d, s, b, n;
    const int maxn = 6500;
    char a[7][maxn];
    bool parity; // 1 odd; 0 even 
    
    bool read()
    {
    	cin >> d;
    	if (!d) return false;
    	cin >> s >> b;
    	getchar(); //加上这句话十分关键，否则就WA了！！！因为会把换行符作为 ch 
    	memset(a, 0, sizeof(a));
    	char ch = getchar();
    	parity = ch == 'O';
    	if (ch == '\n') cout << "Wrong Answer because of this fault!!!" << endl;
    	getchar();
    	n = s * b;
    	for (int i = 0; i < d; i++) cin >> a[i];
    	return true;
    }
    
    
    bool solve()
    {
    	int i, j;
    	for (i = 0; i < n; i++) //对每列做检查，看是否需要恢复数据，以及检查是否满足所给校验规律 
    	{
    		bool flag = false;
    		int broke = -1; // 用来标记是否出现两次x，若是则退出，无法恢复 
    		for (j = 0; j < d; j++)
    		{
    			char &ch = a[j][i]; // 用引用，则数据的使用和修改都非常方便
    			if (ch == '1') flag = !flag;
    			if (ch == 'x')
    			{
    				if (broke == -1) broke = j;
    				else return false;
    			} 
    		}
    		if (broke == -1 && flag != parity) return false; //磁盘没有损坏，不需恢复，但校验不合法 
    		if (broke != -1) a[broke][i] = (parity == flag) ? '0':'1'; // 恢复 
    	} 
    	return true;
    }
    
    void print(bool ch)
    {
    	if (!ch)
    	{
    		cout << "invalid." << endl;
    		return;
    	} 
    	else cout << "valid, contents are: ";
    	
    	int cnt = 0, sum = 0;
    	 
    	for (int i = 0; i < b; i++) //枚举硬盘被分为的b个部分 
    	{
    		int pos = i * s;
    		for (int j = 0; j < d; j++)
    		{
    			if (i % d == j) continue; //若为校验位，应该跳过
    			for (int k = 0; k < s; k++)
    			{
    				sum <<= 1; sum += a[j][pos + k] == '1'; cnt++;
    				if (cnt == 4)
    				{
    					printf("%X", sum);
    					sum = 0; cnt = 0;
    				}
    			}
    		}
    	}
    	// 若最后一个数不满4位，不能直接构成16进制，则末尾补0 
    	if (cnt) printf("%X", sum << (4 - cnt));
    	cout << endl;
    	
    }
    
    int main()
    {
    	int kase = 0;
    	while (read())
    	{
    		cout << "Disk set " << ++kase << " is ";
    		print(solve());
    	}
    	return 0;
    }

转载于:https://www.cnblogs.com/mofushaohua/p/7789474.html