当前位置:Gxlcms > mysql > 算法竞赛入门经典(第2版)习题4

算法竞赛入门经典(第2版)习题4

时间:2021-07-01 10:21:17 帮助过:18人阅读

(这题其实不难,但是拖延、畏难的坏习惯吃掉了我十多天,羞愧 ) 相关概念: 异或:^ 按位异或 若参加运算的两个二进制位相同则为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;
}

人气教程排行