题解 P7911 [CSP-J 2021] 网络连接

fz20181223 · 2021-10-23 22:33:58 · 题解

就是个大模拟（

但是由于数据范围的优（过）势（水），导致 O(n^2) 都能过。

具体思路就是读入每个类型和地址，然后看这个地址是否合法。如果不合法输出 ERR，否则继续看。

如果这是服务器（Server），则用 O(n)（事实上不需要 O(n)，复杂度最坏为当前编号，只不过是 O(n) 级别的。下同）判断一下该地址是否被用过。如果扫到了相同的地址则输出 FAIL，否则输出 OK。

如果这是客户端（Client），则用 O(n) 判断一下是否有相同地址的 Server。如果扫到了相同的地址则输出其编号，否则输出 FAIL。

下面给出考场上的代码（freopen 已去除）其中主程序中的 mask 变量中有用的是最后两位二进制位。最后一位为当前 ip 是否可用，倒数第二位为当前计算机的类型。

同时，在判断 ip 是否可行时，需要注意当前数字串是否为空，是否有前导零，当前数串与下一个数串中间间隔符号，数串总数等问题。

#include<bits/stdc++.h>
using namespace std;
const int N=1009;
int n,cnt=0;
int toN(string st){
    int x;stringstream ss;
    ss<<st;ss>>x;
    return x;
}
struct ip{
    int add[5],id;//add[0~3]:ip add[4]:port
    bool type;//0=server 1=client
    bool ava;//0=illegal 1=legal
    bool sti(string st){//string to ip which can check
        int cnt=0;string tmp="";
        for(int i=0;i<st.size();++i){//ip inside
            if(!isdigit(st[i])){
                if(tmp=="") return this->ava=0;
                int t=toN(tmp);
                if(cnt>3) return this->ava=0;
                if(cnt==3){//port next
                    if(st[i]!=':') return this->ava=0;
                    if(tmp[0]=='0'&&tmp.size()>1) return this->ava=0;//prev 0
                    if(t>255) return this->ava=0;//ip too big
                }else{//ip next
                    if(st[i]!='.') return this->ava=0;
                    if(tmp[0]=='0'&&tmp.size()>1) return this->ava=0;//prev 0
                    if(t>255) return this->ava=0;//ip too big
                }
                tmp="";
                add[cnt++]=t;
            }else tmp=tmp+st[i];
        }
        if(tmp=="") return this->ava=0;
        if(tmp[0]=='0') return this->ava=0;//prev 0
        int t=toN(tmp);
        if(t>65535) return this->ava=0;//port too big
        add[cnt]=t;
        return this->ava=(cnt==4);
    }
    bool operator ==(ip x){
        for(int i=0;i<=4;++i)
        if(this->add[i]!=x.add[i]) return 0;
        return 1;
    }
    int fil(string tp,string ip){
        if(tp[0]=='S') this->type=0;
        if(tp[0]=='C') this->type=1;
        int ret=(this->type)<<1;//ret  type,success
        return ret|sti(ip);
    }
}a[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        string tpe,st;
        cin>>tpe>>st;
        int mask=a[i].fil(tpe,st);
        if(!(mask&1)){
            puts("ERR");
            continue;
        }
        mask>>=1;
        bool flag=1;
        switch(mask){
            case 0:{//server
                for(int j=1;j<i;++j){
                    if(a[i]==a[j]&&a[j].type==0){
                        a[j].ava=0;
                        puts("FAIL");
                        flag=0;
                        break;
                    }
                }
                if(flag) puts("OK");
                break;
            }
            case 1:{//client
                for(int j=1;j<i;++j){
                    if(a[j].type==0&&a[i]==a[j]){
                        printf("%d\n",j);
                        flag=0;
                        break;
                    }
                }
                if(flag) puts("FAIL");
                break;
            }
            default:{
//              puts("You ak ioi!");
                break;
            }
        }
    }
    return 0;}