csp-201812

2020-08-25

20181201（小明上学）

代码1

若经过道路，则直接累加时间；若经过路口，则看亮的是什么灯，然后写一个函数getWaitTime(int type, int leftTime) 来计算要等多久。

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

int r,y,g,n;
int time2 = 0;

int getWaitTime(int type, int leftTime){
    if(type==1){
        return leftTime;
    }else{
        return leftTime+r;
    }
}
int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>r>>y>>g>>n;
    for(int i=0;i<n;i++){
        int type, leftTime;
        cin>>type>>leftTime;
        if(type==0){
            time2+=leftTime;
        }else if(type!=3){
            time2+=getWaitTime(type, leftTime);
        }
    }
    cout<<time2<<endl;
}

测试数据

20181202（小明放学）

代码1

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

int r,y,g,n;
long long time2 = 0;

int getWaitTime(int type,int leftTime){
    long long a;
    if(type==1){
        a = r-leftTime;
    }else if(type==2){
        a = r+g+y-leftTime;
    }else{
        a = r+g-leftTime;
    }
    a += time2;
    a = a%(r+y+g);
    if(a>=0 && a<r){
        return r-a;
    }else if(a>=r && a<r+g){
        return 0;
    }else{
        return (r+g+y-a+r);
    }
}

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>r>>y>>g>>n;
    for(int i=0;i<n;i++){
        int type, leftTime;
        cin>>type>>leftTime;
        if(type==0){
            time2+=leftTime;
        }else{
            int temp = getWaitTime(type,leftTime);
            time2+=temp;
        }
    }
    cout<<time2<<endl;
}

这题要注意一点，因为1e6*1e5大于int的表示范围，所以计算绝对时间时用到long long，同时计算总的时间time2也要用long long。

20181203（CIDR合并）

代码1

我们设置一个结构体来表示标准的IP前缀。

struct Ippre{
    array<int,4> ip;
    int len; //[0,32]
}

写一个函数bool isContain(Ippre& ip1,Ippre& ip2) 来看ip1是否包含ip2。写一个函数bool merge2(Ippre& ip1,Ippre& ip2, Ippre ip3)来判断ip1和ip2是否可以合并，若可以则返回true，并把合并结果放到ip3中，否则，返回false。

一开始，输入数据，来将形形色色的Ip前缀转化为标准形式。Ippre convert(string str) 来完成转换的功能。将所有的ip前缀存放在set<Ippre> ipSet 中。

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

struct Ippre{
    array<int,4> ip;
    int len; //[0,32]
    bool operator<(const Ippre& ip2)const{
        if(ip[0]!=ip2.ip[0]){
            return ip[0]<ip2.ip[0];
        }else if(ip[1]!=ip2.ip[1]){
            return ip[1]<ip2.ip[1];
        }else if(ip[2]!=ip2.ip[2]){
            return ip[2]<ip2.ip[2];
        }else if(ip[3]!=ip2.ip[3]){
            return ip[3]<ip2.ip[3]; 
        }else{
            return len<ip2.len;
        }
    }
};

int n;
set<Ippre> ipSet;

Ippre convert(string str){
    Ippre ip;
    int k1=0,k2,dotNum=0;
    k2 = str.find('.',k1);
    while(k2 != string::npos){
        ip.ip[dotNum] = stoi(str.substr(k1,k2-k1));
        k1 = k2+1;
        k2 = str.find('.',k1);
        dotNum++;
    }
    if(dotNum==3 && str.find('/')!=string::npos){ //标准型
        k2 = str.find('/');
        ip.ip[dotNum] = stoi(str.substr(k1,k2-k1));
        ip.len = stoi(str.substr(k2+1));
    }else if(str.find('/')!=string::npos){ //省略后缀型
        k2 = str.find('/');
        for(int i=dotNum;i<4;i++){
            if(i==dotNum){
                ip.ip[i] = stoi(str.substr(k1,k2-k1));
            }else{
                ip.ip[i] = 0;
            }
        }
        ip.len = stoi(str.substr(k2+1));
    }else{ //省略长度型
        for(int i=dotNum;i<4;i++){
            if(i==dotNum){
                ip.ip[i] = stoi(str.substr(k1));
            }else{
                ip.ip[i] = 0;
            }
        }
        ip.len = (dotNum+1)*8;
    }
    return ip;
}

bool isContain(const Ippre& ip1,const Ippre& ip2){
    if(ip1.len > ip2.len){
        return false;
    }else if(ip1.len == ip2.len){
        for(int i=0;i<4;i++){
            if(ip1.ip[i] != ip2.ip[i]){
                return false;
            }
        }
        return true;
    }else{
        for(int i=0;i<ip1.len/8;i++){
            if(ip1.ip[i]!=ip2.ip[i]){
                return false;
            }
        }
        int a = ip1.len%8;
        int num1=ip1.ip[ip1.len/8], num2=ip2.ip[ip1.len/8];
        num1 = (num1>>(8-a));
        num2 = (num2>>(8-a));
        return num1==num2;
    }
}

bool merge2(const Ippre& ip1,const Ippre& ip2, Ippre& ip3){
    if(ip1.len != ip2.len){
        return false;
    }
    for(int i=0;i<ip1.len/8;i++){
        if(ip1.ip[i]!=ip2.ip[i]){
            return false;
        }
    }
    int a = ip1.len%8;
    int num1=ip1.ip[ip1.len/8], num2=ip2.ip[ip1.len/8];
    num1 = (num1 >> (8-a+1));
    num2 = (num2 >> (8-a+1));
    if(num1==num2){
        num1 = (num1<<(8-a+1));
        ip3.ip = ip1.ip;
        ip3.ip[ip1.len/8] = num1;
        ip3.len = ip1.len-1;
        return true;
    }else{
        return false;
    }
}
void outputIp(Ippre ip){
    for(int i=0;i<4;i++){
        if(i<3){
            cout<<ip.ip[i]<<".";
        }else{
            cout<<ip.ip[i]<<"/";
        }
    }
    cout<<ip.len;
}
int main(){
    //freopen("D://input.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin>>n;
    string ip;
    for(int i=0;i<n;i++){
        cin>>ip;
        ipSet.insert(convert(ip));
    }

    set<Ippre>::iterator it = ipSet.begin();
    for(;it!=ipSet.end();){
        set<Ippre>::iterator it2 = ++it;
        it--;
        if(it2 == ipSet.end()){
            it++;
            continue;
        }
        if(isContain(*it, *it2)){
            ipSet.erase(it2);
        }else{
            it++;
        }
    }

    it = ipSet.begin();
    for(;it!=ipSet.end();){
        set<Ippre>::iterator it2 = ++it;
        it--;
        if(it2 == ipSet.end()){
            it++;
            continue;
        }
        Ippre ip3;
        if(merge2(*it,*it2,ip3)){
            it2 = ipSet.erase(it);
            ipSet.erase(it2);
            it = ipSet.insert(ip3).first;
            if(it != ipSet.begin()){
                it--;
            }
        }else{
            it++;
        }
    }

    //output
    it = ipSet.begin();
    for(;it!=ipSet.end();it++){
        outputIp(*it);
        cout<<endl;
    }
}
//num>>2不会改变num的值

第17行我把3错写成2了，好坑啊。

80分。答案错误

20181204（数据中心）

代码1

仔细观察$T_{MAX}$ 的定义，发现它其实就是最小支撑树的最大边。我们直接使用Kruskal算法。

我们定义一个数据结构：

1
2
3

struct Edge{
    int u,v,w;
}

然后把每个输入的边作为Edge存入vector<Edge> edges 中。按照w属性排序。由于要用到并查集，所以要设置vector<int> father 数组，然后再写int findFather(int x)，以及void union2(int a,int b) 函数。

在运行kruskal时，记录选择的边的最大权值。

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

struct Edge{
    int u,v,w;
};
int n,m,root;
vector<Edge> edges;
vector<int> father;
int ans = 0;

int findFather(int x){
    if(father[x] == x){
        return x;
    }
    int fx = findFather(father[x]);
    father[x] = fx;
    return fx;
}
void union2(int a,int b){
    int fa=findFather(a), fb=findFather(b);
    if(fa!=fb){
        father[fa]=fb;
    }
}
bool cmp(const Edge& e1, const Edge& e2){
    return e1.w<e2.w;
}
void Kruskal(){
    //init
    sort(edges.begin(),edges.end(),cmp);
    for(int i=0;i<n+1;i++) father[i]=i;

    int cnt=0;
    for(int i=0;i<m&&cnt<n-1;i++){
        int u=edges[i].u, v=edges[i].v, w=edges[i].w;
        int fu=findFather(u), fv=findFather(v);
        if(fu != fv){
            union2(u,v);
            ans = max(ans,w);
            cnt++;
        }
    }
}
int main(){
    //freopen("D://input.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin>>n>>m>>root;
    //init
    edges.resize(m);
    father.resize(n+1);

    //input
    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        edges[i] = {u,v,w};
    }

    Kruskal();

    cout<<ans<<endl;
}