CCF-CSP Questions (three)

Algorithms change the world. The importance of algorithms is self-evident to a programmer, so the practice of some algorithms is indispensable. Next, I will share some algorithmic problems.

Question

question

Analysis

Arrays or stacks can be used to store data, multiply and divide first, convert all operations into additions, and then add.

Solution

Here is the solution to this problem.The following are two solutions, the result is 100 points.

Program

Method One

//
//  main.cpp
//  DRAIDF
//
//  Created by gang du on 2019/4/27.
//  Copyright © 2019 gang du. All rights reserved.
//

#include <iostream>
#include <string>
#include <cstdio>

using namespace std;

const int BLOCK_SIZE=4;
string disk[1000];

int main(){
    int disk_num, band_size, disk_remain, output_num, output_block[1000], disk_band=0;
    
    cin >> disk_num >> band_size >> disk_remain;
    for(int i=0; i<disk_remain; i++){
        int j;
        cin >> j >> disk[j];
        // disk_band -> the number of band in a disk;
        if(disk_band==0)
            disk_band = (int)disk[j].size()/(band_size*BLOCK_SIZE*2);
    }
    
    cin >> output_num;
    for(int i=0; i<output_num; i++){
        cin >> output_block[i];
        
        int block_longitude, block_latitude, band_longitude, band_latitude, band_num;
        band_num = output_block[i]/band_size;
        
        // block_longitude -> block in which disk; block_latitude -> block's position in disk;
        // band_longitude -> band in which disk; band_latitude -> band's position in disk;
        band_latitude = band_num/(disk_num-1);
        int check_disk;
        check_disk = (disk_num-1)-band_latitude%disk_num;
        band_longitude = check_disk+band_num%(disk_num-1)+1;
        while(band_longitude>=disk_num)
            band_longitude -= disk_num;
        
        block_longitude = band_longitude;
        block_latitude = band_latitude*band_size+output_block[i]%band_size;
        
        // cout << block_longitude << " " << block_latitude << endl;
        
        if((disk[block_longitude].empty() && (disk_num-disk_remain)>1) || output_block[i]>(disk_band*band_size*(disk_num-1)-1) || disk_band==0)
            cout << "-" << endl;
        else{
            int block_start = block_latitude*BLOCK_SIZE*2;
            if(!disk[block_longitude].empty())
                cout << disk[block_longitude].substr(block_start, BLOCK_SIZE*2) << endl;
            else{
                for(int j=0; j<BLOCK_SIZE*2; j++){
                    int temp = 0;
                    for(int k=0; k<disk_num-1; k++){
                        if(k!=block_longitude && disk[k][block_start]>='A' && disk[k][block_start]<='Z'){
                            temp=temp^((int)disk[k][block_start]-55);
                        }else if(k!=block_longitude && disk[k][block_start]>='0' && disk[k][block_start]<='9'){
                            temp=temp^((int)disk[k][block_start]-48);
                        }
                    }
                    cout << uppercase << hex << temp;
                    block_start ++;
                }
                cout << endl;
            }
        }
    }
}

Method Two

//
//  main.cpp
//  DRAIDF
//
//  Created by gang du on 2019/4/27.
//  Copyright © 2019 gang du. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <string>

using namespace std;
int len = 0;

char getc(char c){
    if(c<10)
        return c+'0';
    else if(c<=16)
        return c+'A'-10;
    else if(c<='9')
        return c-'0';
    else if(c<='F')
        return c-'A'+10;
    else
        return c;
}
void cxor(string &a,string b){
    for(int i=0;i<8;i++){
        a[i]=getc(getc(a[i])^getc(b[i]));
    }
}
void getdata(string dskd[], int n, int s, int l, int r){
    int level=r/((n-1)*s);                           //获取读取的数据层数
    int curp=(n-level%n)-1;                          //获取读取的数据层数P块所在位置
    int blk=level*s+r%s;                             //获取数据所在硬盘的块索引
    int disk=r%((n-1)*s)/s+curp+1;                   //获取读取的数据所在硬盘索引
    disk=disk%n;
    if(len<blk*8+8||len==0){                         //如果获取的长度超过了硬盘数据长度，直接输出减号退出
        cout<<"-"<<endl;
        return;
    }
    if(dskd[disk].length()!=0)                       //如果当前盘存在，直接输出
        cout<<dskd[disk].substr(blk*8,8)<<endl;
    else if(dskd[disk].length()==0&&n-l==1){         //如果当前盘缺失，且可以恢复，则通过异或读取对应的数据
        string str="00000000";
        for(int i=0;i<n;i++){
            if(i!=disk)
                cxor(str,dskd[i].substr(blk*8,8));
        }
        cout<<str<<endl;
    }else
        cout<<"-"<<endl;                             //如果当前盘缺失且不可以恢复，输出减号。
}
int main(){
    int n,s,l;
    cin>>n>>s>>l;
    string dskd[1010];
    int dpos;
    for(int i=0;i<l;i++){
        cin>>dpos;
        cin>>dskd[dpos];
    }
    int m;
    cin>>m;
    int a[1000];
    for(int i=0;i<m;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        if(dskd[i].length()!=0){
            len = dskd[i].length();
            break;
        }
    }
    for(int i=0;i<m;i++){
        getdata(dskd,n,s,l,a[i]);
    }
    return 0;
}

Remarks

This program is written in C++ and uses standard input and output functions.

If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !

...

00:00

This is the third question of CCF-CSP in March 2019.