CSP第18次 201912-4 区块链 C/C++答案

CSP第18次 201912-4 区块链 C/C++ 0分答案

尽管分析了这么多还是零分哈哈哈，找不到问题在哪，放这先不管了日后再更

#include #include #include #include #include #include using namespace std;const int max_n=510,max_m=10010,max_k=30010;int n,m,t,k,chaxun_num=0;//如果op队列里没有查询了就可以停止下来了int arr[max_n][max_n]={-1};int vertex_len[max_n];//main函数开头初始化为1了string vertex_lian[max_n];//main函数开头初始化为\"0 \"了string vertex_last[max_n];//无需初始化，如果是要用到的时候必然已经赋值了string out_str=\"\";struct op{    int type;//1为处理邻居传来的链,2为增加块，3为查询    int a,b;    string c;    string change_lian;    string change_last;    int change_len;};struct que_cmp{    bool operator () (const op &op1,const op &op2)    {        if(op1.b!=op2.b)            return op1.b>op2.b;        else            return op1.type>op2.type;//同一时刻:先接受链，再产生块,再查询    }};priority_queue<op,vector<op>,que_cmp> que;void get_lian(op top_op){    int i,int_a_last,int_change_last;    sscanf(vertex_last[top_op.a].c_str(),\"%d\",&int_a_last);    sscanf(top_op.change_last.c_str(),\"%d\",&int_change_last);    if(top_op.change_len>vertex_len[top_op.a] || top_op.change_len==vertex_len[top_op.a] && int_a_last>int_change_last)//如果发生改变    {        vertex_len[top_op.a] = top_op.change_len;        vertex_lian[top_op.a] = top_op.change_lian;        vertex_last[top_op.a] = top_op.change_last;        for(i=1;i<=n;i++)//告诉周围的点我变了            if(arr[top_op.a][i]!=-1 && i!=top_op.a)            {                op o;                o.type=1;                o.a=i;                o.b=top_op.b+t;                o.change_lian = vertex_lian[top_op.a];//把发生改变时整条链状态塞进op队列应该是唯一的做法了（因为有更新延迟的存在）                o.change_len = vertex_len[top_op.a];                que.push(o);            }    }}void zengjia(op top_op){    int i;    vertex_len[top_op.a]++;    vertex_lian[top_op.a]+=top_op.c+\" \";    vertex_last[top_op.a]=top_op.c;    for(i=1;i<=n;i++)//告诉周围的点我变了        if(arr[top_op.a][i]!=-1 && i!=top_op.a)        {            op o;            o.type=1;            o.a=i;            o.b=top_op.b+t;            o.change_lian = vertex_lian[top_op.a];//把发生改变时整条链状态塞进op队列应该是唯一的做法了（因为有更新延迟的存在）            o.change_len = vertex_len[top_op.a];            que.push(o);        }}void chaxun(op top_op)//天呐查询居然是最简单的,我太感动了{    char tmp_c[10];    sprintf(tmp_c,\"%d\",vertex_len[top_op.a]);    out_str+=tmp_c;    out_str+=\" \";    out_str+=vertex_lian[top_op.a];    out_str.erase(out_str.end()-1);//删掉每行最后多出的一个空格    out_str+=\"\\n\";}int main(){    int i;    fill(vertex_len,vertex_len+max_n,1);    scanf(\"%d %d\",&n,&m);    for(i=1;i<=n;i++)        vertex_lian[i]=\"0 \";    for(i=0;i<m;i++)    {        int u,v;        scanf(\"%d %d\",&u,&v);        arr[v][u] = arr[u][v] = 1;    }    scanf(\"%d %d\",&t,&k);    for(i=0;i<k;i++)    {        int a,b,type=3;        char tmp_c[10];        op o;        scanf(\"%d %d\",&a,&b);        if(getchar()==\' \')//若三个数增加，两个数查询            scanf(\"%s\",tmp_c),type=2;        else            chaxun_num++;        o.a=a,o.b=b,o.c=tmp_c,o.type = type;        que.push(o);    }    while(!que.empty())    {        op top_op = que.top();        que.pop();        if(chaxun_num==0)            break;        if(top_op.type ==1)        {            get_lian(top_op);        }        else if(top_op.type ==2)        {            zengjia(top_op);        }        else        {            chaxun(top_op);            chaxun_num--;            printf(\"\\n  chaxun_num  %d         time:%d\",chaxun_num,top_op.b);        }    }    out_str.erase(out_str.end()-1);    cout<<out_str;    return 0;}

下面这段是写的第一版本，还没写完，中途想到行不通
改变时传递给身边这个功能要注意，因为有延迟的存在，所以如果仅将块链条 存储在任务外是行不通的，原因如下
1、将发生改变时的块数 塞进队列 任务pop时判断 若可替换为任务pop时的队列 不可行
2、任务pop时判断 任务pop时的块数 若可替换为任务pop时的队列 不可行
3、将发生改变时的块数 判断 将发生改变时的块数 不可行
所有一定要把块链的状态也一起塞进任务队列，所以我就想到了上方的代码。用string来存储，也方便后续输出

#include #include #include using namespace std;const int max_n=510,max_m=10010,max_k=30010;int n,m,t,k;int arr[max_n][max_n]={-1};int BCJ[max_k]={-1};//并查集,其实也不算是，就是思路跟并查集有点像，用这个数组来存储所有后来加上的块，通过父节点来互相指着int vertex_to_BCJ[max_n]={-1};//图中的点 指向 BCJ数组int vertex_len[max_n]={-1};struct op{    int type;//1为处理邻居传来的链,2为增加块，3为查询    int a,b,c;    int who_change,change_len;};struct que_cmp{    bool operator () (const op &op1,const op &op2)    {        if(op1.b!=op2.b)            return op1.b<op2.b;        else            return op1.type<op2.type;//同一时刻:先接受链，再产生块,再查询    }};priority_queue<op,vector<op>,que_cmp> que;void get_lian(op top_op){    if(who_change_len>a_len)    {        a_len = who_change_len;        vertex_len[top_op.a] = a_len;    }}void zengjia(op top_op){    int i;    vertex_len[top_op]++;    if(vertex_to_BCJ[top_op.a]==-1)        vertex_to_BCJ[top_op.a]=top_op.c;//指向BCJ    else    {        int index = vertex_to_BCJ[top_op.a];        while(BCJ[index]!=-1)            index = BCJ[index];        BCJ[index]=top_op.c;    }    for(i=0;i<n;i++)//告诉周围的点我变了        if(arr[top_op.a][i]!=-1)        {            op o;            o.type=3;            o.a=i;            o.b=top_op.b+t;            o.who_change = top_op.a;            o.change_len = vertex_len[top_op];//这里要重点注意！！！是传了当时的            que.push(o);        }}void chaxun(op top_op){}int main(){    int i;    fill(vertex_len,vertex_len+max_n,1);    scanf(\"%d %d\",&n,&m);    for(i=0;i<m;i++)    {        int u,v;        scanf(\"%d %d\",&u,&v);        arr[v][u] = arr[u][v] = 1;    }    scanf(\"%d %d\",&t,&k);    for(i=0;i<k;i++)    {        int a,b,c=-1,type=3;        op o;        scanf(\"%d %d\",&a,&b);        if(getchar()==\' \')//三个数增加，两个数查询            scanf(\"%d\",&c),type=2;        o.a=a,o.b=b,o.c=c;        que.push(o);    }    while(!que.empty())    {        op top_op = que.top();        que.pop();        if(top_op.type ==1)            get_lian(top_op);        else if(top_op.type ==2)            zengjia(top_op);        else            chaxun(top_op);    }    return 0;}