算法竞赛入门经典（第2版）习题4

（这题其实不难，但是拖延、畏难的坏习惯吃掉了我十多天，羞愧 ） 相关概念： 异或：^ 按位异或 若参加运算的两个二进制位相同则为0，否则为1 奇偶校验：奇偶校验是一种校验代码传输正确性的方法。根据被传输的一组二进制代码的数位中“1”的个数是奇数或偶

（这题其实不难，但是拖延、畏难的坏习惯吃掉了我十多天，羞愧）

相关概念：

异或：^ 按位异或 若参加运算的两个二进制位值相同则为0，否则为1

奇偶校验：奇偶校验是一种校验代码传输正确性的方法。根据被传输的一组二进制代码的数位中“1”的个数是奇数或偶数来进行校验。采用奇数的称为奇校验，反之，称为偶校验。采用何种校验是事先规定好的。通常专门设置一个奇偶校验位，用它使这组代码中“1”的个数为奇数或偶数。若用奇校验，则当接收端收到这组代码时，校验“1”的个数是否为奇数，从而确定传输代码的正确性。

//#define LOCAL
//#define TESTING
#include
#include

char data[8][102][66], disk[8][6401], data2[32001], pdata[6402];
const char* hex[] = {"0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F"};


int main()
{
    #ifdef LOCAL
    freopen("xt4-7.in","r",stdin);
    #endif
    int d,s,b,kase=0;
    char parity[2];
    for(;;)
    {
        kase++;
        scanf("%d", &d);
        if(!d) break;
        scanf("%d%d%s", &s, &b,parity);
        memset(disk, 0, sizeof(disk));
        memset(data2,0, sizeof(data2));
        memset(pdata,0, sizeof(pdata));
        for(int i = 1; i <= d; i++) scanf("%s",disk[i]);
        //校验数据存入pdata，普通编码存入data2，b每块磁盘的数据块总量，d磁盘数量，s数据块大小
        int byte = 0, pbyte= 0;
        for(int i=1; i <= b ; i++)//处理第i个数据块
        {
            for(int j = 1; j <= d; j++)//处理第j个磁盘
            {
                if(i%d == j || (i%d == 0 && j == d))
                {
                    for(int k=0; k < s; k++)
                    {
                        pdata[pbyte] = disk[j][s*i-s+k];
                        pbyte++;
                    }
                }
                else
                {
                    for(int k=0; k < s; k++)
                    {
                        data2[byte] = disk[j][s*i-s+k];
                        byte++;
                    }
                }
            }
        }
        //for(int i = 1; i <= d; i++) printf("%d %s\n",i,disk[i]);
        //printf("读入数据:%s||%s\n",data2,pdata);
        //校验、复原数据
        bool valid = true;
        int check;
        if(parity[0] =='E') check =0;
        else check = 1;
        int datas = d-1;
        for(int i = 1; i <= b; i++)//处理第i个数据块
        {
            for(int j = 0; j< s; j++)//处理数据块的第j位数据
            {
                int xn = 0,pxn=0,presult = -1,xind=-1;
                if(pdata[i*s-s+j]=='x') pxn++;//校验数据的第i个数据块的第j位数据如果为x，则pxn=1
                for(int k = 0; k <= datas-1; k++)//
                {
                    if(data2[i*s*datas-datas*s+j+k*s]=='x')
                    {
                        xn++;
                        if(pxn||xn>=2) valid = false;
                        else xind = k;
                        if(!valid) break;
                    }
                    else if(presult<0) presult = data2[i*s*datas-datas*s+j+k*s]-'0';
                    else
                    {
                        presult ^= data2[i*s*datas-datas*s+j+k*s]-'0';
                    }
                    
                }
                if(!valid) break;
                if((pxn+xn==0) &&presult^check != pdata[i*s-s+j]-'0')
                {
                    valid = false;
                    break;
                }
                else if(xn&&!pxn)
                {
                    if(presult>=0) data2[i*s*datas-datas*s+j+xind*s] = (presult^check)^(pdata[i*s-s+j]-'0')+'0';
                    else data2[i*s*datas-datas*s+j+xind*s] =check^(pdata[i*s-s+j]-'0')+'0';
                    //printf("-%d:%d %d %d %d\n",data2[i*s*datas-datas*s+j+xind*s],i*s*datas-datas*s+j+xind*s,presult,check,pdata[i*s-s+j]);
                }
            }
            if(!valid) break;
            
        }
        //校验、复原数据结束
        //printf("校验、复原结果:%s||%s\n",data2,pdata);
        while(strlen(data2)%4) data2[strlen(data2)] = '0';
        //校验数据存入pdata，普通编码存入data2结束
        if(!valid) printf("Disk set %d is invalid.\n", kase);
        else
        {
            printf("Disk set %d is valid, contents are: ", kase);
            for(int i = 0; i <= strlen(data2); i+=4)
            {
                int result=0;
                for(int k = 0; k < 4; k++)
                {
                    result = result*2+data2[i+k]-'0';
                }
                if(result <16 && result >=0) printf("%s",hex[result]);
            }
            printf("\n");
        }
        #ifdef TESTING
        printf("%s\n",data2);
        printf("%s\n",pdata);
        printf("\n");
        #endif
    }
    return 0;
}