csp-201912

2020-08-22

20191201（报数）

代码1

写一个canSkip(int x) 函数，判断一个数是否可以跳过，设置数组skip[]表示每个人跳过的次数。在循环中，判断num是第a=(num-1)%4的人报数；若num可以跳过，则skip[a]++, 否则，循环计数n减1；然后num++；n==0时循环结束。

//freopen("D://input.txt","r",stdin);
#include<bits/stdc++.h>
using namespace std;

int n;
int skip[4] = {0,0,0,0};

bool canSkip(int x){
    if(x%7==0){
        return true;
    }else{
        while(x != 0){
            int b=x%10;
            x = (x-b)/10;
            if(b == 7){
                return true;
            }
        }
    }
    return false;
}

int main(){
    cin>>n;
    int num=1;
    while(n>0){
        if(canSkip(num)){
            skip[(num-1)%4]++;
        }else{
            n--;
        }
        num++;
    }
    //output
    for(int i=0;i<4;i++){
        cout<<skip[i]<<endl;
    }
}

20191202（回收站选址）

代码1

用vector<array<int,2>> pos 存储所有的垃圾点，然后建立倒排索引：点坐标的哈希值到pos中对应下标的映射map<long long, int> mp。例如，<10e9, 10e9>的哈希值为(10e9+10e9)*(2*10e9+1)+(10e9+10e9)，它对应pos中的下标0。

写一个哈希函数long long hash(int x, int y)。用vector<array<int,8>> flag 表示每个点的8个相邻位置是否有垃圾站，当一个点A的右方检查到有垃圾站B时，B的左方也可以设置为由垃圾站。遍历pos，来更新flag，再遍历一遍pos，看每个垃圾站的分数，并记录每个分数的垃圾站个数，int score[5]。

//freopen("D://input.txt","r",stdin);
#include<bits/stdc++.h>
using namespace std;

int n;
vector<array<int,2> > pos;
vector<array<bool,8> > flag;
map<long long, int> mp;
int score[5] = {0,0,0,0,0};
int dirx[8] = {0,1,0,-1,-1,1,1,-1}; //一个点的第i个相邻位置的x坐标的偏移
int diry[8] = {1,0,-1,0,1,1,-1,-1}; //一个点的第i个相邻位置的y坐标的偏移

long long hash2(int x, int y){
    long long h;
    h = (x+1000000000);
    h = h*(long long)(2000000000+1);
    h += (y+1000000000);
    return h;
}

int reversePos(int x){ //x位置的逆位置，如A的0位置是B，则B的2位置是A
    if(x==0){
        return 2;
    }else if(x==1){
        return 3;
    }else if(x==2){
        return 0;
    }else if(x==3){
        return 1;
    }else if(x==4){
        return 6;
    }else if(x==5){
        return 7;
    }else if(x==6){
        return 4;
    }else{
        return 5;
    }
}

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n;
    //init
    pos.resize(n);
    flag.resize(n);
    for(int i=0;i<n;i++){
        flag[i] = {false,false,false,false,false,false,false,false};
    }

    //input
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        pos[i]={x,y};
        mp[hash2(x,y)] = i;
    }

    for(int i=0;i<n;i++){
        int x=pos[i][0], y=pos[i][1];
        for(int j=0;j<8;j++){
            if(flag[i][j] == false){
                int x1=x+dirx[j], y1=y+diry[j];
                long long h = hash2(x1,y1); //error
                if(mp.find(h) != mp.end()){
                    flag[i][j] = true;
                    flag[mp[h]][reversePos(j)] = true;
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        if(flag[i][0]==true && flag[i][1]==true && flag[i][2]==true && flag[i][3]==true){
            int sm=0;
            for(int j=4;j<8;j++){
                sm+=(flag[i][j]==true?1:0);
            }
            score[sm]++;
        }
    }

    //output
    for(int i=0;i<5;i++){
        cout<<score[i]<<endl;
    }
}

20191203（化学方程式）

代码1

思路：vector<int> numLeft(27*27) 和 vector<int> numRight(27*27)分别表示等式左右两边的各个元素的个数，若numLeft与numRight完全相同，则等式匹配，否则，不匹配。

我们写一个dealItem(string str, int a, vector<int>& num) 来处理一个化合物，也就是加好或等号之间的字符串，例如4Na(Au(CN)2)2，这个函数是个递归函数，递归出口是str是一个只有字母的字符串，而没有数字与括号，a表示对于每个元素，需要乘的倍数，num是输出参数。对于这个例子，处理过程为，进入1层dealItem，处理4Na(Au(CN)2)2，然后进入2层dealItem，处理Na(Au(CN)2)2，a=4，然后累加Na的个数，然后进入3层dealItem，处理Au(CN)2，倍数是8，累加Au的个数，然后进入4层dealItem，处理CN，倍数是16，累加C，N。

//freopen("D://input.txt","r",stdin);
#include<bits/stdc++.h>
using namespace std;

int n;
string input;

//根据元素字符串，得到它的hash值，若为单个字母，则返回字母下标，若为双字母，则返回x*27+y
int hash2(string str){
    if(str.size()==1){
        return str[0]-'A'+1;
    }else{
        return (str[0]-'A'+1)*27+(str[1]-'a'+1);
    }
}
vector<int> numLeft(27*27), numRight(27*27);
void dealItem(string str, int a, vector<int>& num){
    if(isdigit(str[0])){ //有系数
        int k=0, k1=0;
        while(k1<str.size() && isdigit(str[k1])) k1++;
        string s1 = str.substr(k,k1-k);
        int b = stoi(s1); //倍数
        dealItem(str.substr(k1),a*b,num);
    }else{
        int k=0,k1=0;
        while(k<str.size()){
            if(isalpha(str[k])){ //遇到元素
                k1 = k+1;
                if(k1<str.size() && islower(str[k1])) k1++;
                if(k1<str.size() && isdigit(str[k1])){ //元素后面跟数字
                    string s1 = str.substr(k,k1-k);
                    k = k1;
                    while(k1<str.size() && isdigit(str[k1])) k1++;
                    string s2 = str.substr(k,k1-k);
                    int b = stoi(s2);
                    dealItem(s1,a*b,num);
                }else{ //累加元素个数
                    string s1 = str.substr(k,k1-k);
                    int h = hash2(s1);
                    num[h] += a;
                }
                k = k1;
            }else{ //遇到括号
                int b = 1; //表示未匹配的左括号个数
                k++;
                k1=k;
                while(k1<str.size() && b!=0){
                    if(str[k1]=='('){
                        b++;
                    }else if(str[k1]==')'){
                        b--;
                    }
                    k1++;
                }
                string s1 = str.substr(k,k1-k-1);
                if(k1<str.size() && isdigit(str[k1])){ //括号后面跟数字
                    k=k1;
                    while(k1<str.size() && isdigit(str[k1])) k1++;
                    string s2 = str.substr(k,k1-k);
                    int c = stoi(s2);
                    dealItem(s1,a*c,num);
                }else{
                    dealItem(s1,a,num);
                }
                k = k1;
            }
        }
    }
}

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n;
    while(n--){
        cin>>input;
        //cout<<input<<endl;
        //init
        for(int i=0;i<27*27;i++){
            numLeft[i] = numRight[i] = 0;
        }

        int k = input.find('='); //等号的位置
        int k1=0, k2;
        while(k1<k){
            k2 = input.find('+',k1);
            if(k2 != string::npos && k2<k){
                dealItem(input.substr(k1,k2-k1),1,numLeft);
                k1 = k2+1;
            }else{
                dealItem(input.substr(k1,k-k1),1,numLeft);
                k1 = k+1;
            }
        }
        k1 = k+1;
        while(k1<input.size()){
            k2 = input.find('+',k1);
            if(k2 != string::npos){
                dealItem(input.substr(k1,k2-k1),1,numRight);
                k1 = k2+1;
            }else{
                dealItem(input.substr(k1),1,numRight);
                k1 = k2;
            }
        }

        bool flag = true;
        for(int i=0;i<27*27;i++){
            if(numLeft[i] != numRight[i]){
                flag = false;
                break;
            }
        }
        //cout<<"O: "<<numLeft['O'-'A'+1]<<" "<<numRight['O'-'A'+1]<<endl;
        if(flag) cout<<"Y"<<endl;
        else cout<<"N"<<endl;
    }
}

20191204（区块链）

代码1

我们设置一个节点的结构为：

struct Node{
    int u;
    vector<int> link; //初始为{0}
    map<int,int> mp1; //在某个时刻产生了一个块
    map<int,vector<int>> mp2;//在某个时刻接受了一个链
 }

在接收k个处理的时候，若是产生一个新块，则让对应节点的mp1更新。有一个系统时间time=0，当你要查询i时刻的某个节点的链子的时候，要从time开始模拟传播和链更新过程，并把mp1和mp2中已经更新到Link中的项目给删除掉。

//freopen("D://input.txt","r",stdin);
#include<bits/stdc++.h>
using namespace std;

struct Node{
    int u;
    vector<int> link; //初始为{0}
    map<int,vector<int>> mp1; //在某个时刻产生了一个块
    map<int,vector<vector<int>>> mp2;//在某个时刻接受了一个链
 };
int n,m,k,t,time2=0;
vector<Node> nodes; //n+1大小
vector<vector<int>> graph; //n+1大小

//vec1是否可以更新vec2
bool canUpdate(vector<int>& vec1, vector<int>& vec2){
    if(vec1.size() > vec2.size()){
        return true;
    }else if(vec1.size()==vec2.size() && vec1.back()<vec2.back()){
        return true;
    }else{
        return false;
    }
}
//在tim时刻开始传播x号节点的链
void difuse(int tim,int x){
    for(int i=0;i<graph[x].size();i++){
        int v = graph[x][i];
        nodes[v].mp2[time2+t].push_back(nodes[x].link);
    }
}
int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n>>m;
    //init
    nodes.resize(n+1);
    for(int i=1;i<=n;i++) nodes[i].link.push_back(0);
    graph.resize(n+1);

    //input
    while(m--){
        int u,v;
        scanf("%d%d",&u,&v);
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    scanf("%d%d",&t,&k);
    while(k--){
        int a,b,c;
        scanf("%d%d",&a,&b);
        if(cin.get()==' '){
            scanf("%d",&c);
            nodes[a].mp1[b].push_back(c);
        }else{
            for(;time2<=b;time2++){
                for(int i=1;i<=n;i++){
                    bool changed = false;
                    map<int,vector<int>>::iterator it1 = nodes[i].mp1.begin();
                    map<int,vector<vector<int>>>::iterator it2 = nodes[i].mp2.begin();
                    while((it2!=nodes[i].mp2.end()&&(*it2).first==time2) || (it1!=nodes[i].mp1.end() && (*it1).first==time2)){
                        if(it2!=nodes[i].mp2.end()&&(*it2).first==time2){
                            for(int j=0;j<(*it2).second.size();j++){
                                if(canUpdate((*it2).second[j], nodes[i].link)){
                                    nodes[i].link = (*it2).second[j];
                                    changed = true;
                                }
                            }
                            it2 = nodes[i].mp2.erase(it2);
                        }
                        if((it1!=nodes[i].mp1.end() && (*it1).first==time2)){
                            for(int j=0;j<(*it1).second.size();j++){
                                nodes[i].link.push_back((*it1).second[j]);
                                changed = true;
                            }
                            it1 = nodes[i].mp1.erase(it1);
                        }
                    }
                    if(changed){
                        //传播
                        difuse(time2,i);
                    }
                }
            }
            cout<<nodes[a].link.size();
            for(int i=0;i<nodes[a].link.size();i++){
                cout<<" "<<nodes[a].link[i];
            }
            cout<<endl;
        }
    }
}

错误，40分。题目给的测试用例都过了。

测试用例

代码2

可以直接存储<时刻，所有结点产生的块或接收的链>，比如可以这样写数据结构：map<int, unordered_map<int, array<vector<int>,2>>> ，外层map建立时刻与所有结点产生的块或接收的链之间的映射，内层unordered_map建立结点编号与产生的块或接收的链之间的映射，这个时候用无序map更好，因为查询操作更多，array<vector<int>,2>的第一个部分是产生的块，第二各部分是接收的链，其实这个时候可以接收很多链，但是通过比较，只留下最优的那个。