P7911 题解
Elgo87
·
·
题解
~~蒟蒻刚开此题时一眼就看出这是一道图论题。~~ 其实这是一道不大不小的模拟。模拟？正是蒟蒻最擅长的算法。
## 代码讲解
既然是模拟，就不讲思路了，渗透在代码中。
不妨把地址串存入一个结构体，这个结构体有两个成员：
```cpp
const int ser=1,cli=2; //ser代表Server，cli代表Client
struct address{
int type; //计算机类型：ser / cli
string s; //地址串
};
```
本题比较重要的核心就是判断一个地址串是否合法，要判断是否合法，我们就需要一个判断字符串是否有前导零的函数：
```cpp
bool check(string s)
{
if(s[0]!='0') return true; //第一位不是零，那么不可能有前导零
if(s.size()==1) return true; //只有一位数，不可能有前导零
return false; //其他情况都有前导零
}
```
接着就可以很顺利地写出判断地址串合法的函数了，**写模拟重要的就是要考虑周全，不能有遗漏之处，否则会酿成大错**：
```cpp
bool is_ok(address add)
{
int sum=0,sum2=0; //sum统计串中 '.' 的个数，sum2统计串中 ':' 的个数
if(!isdigit(add.s[add.s.size()-1])) //最后一位不是数字，必然不合法
return false;
for(int i=0; add.s[i]; i++) //统计 sum 和 sum2 ，顺便处理了一些错误的情况
{
if(add.s[i]=='.') //点
{
if(i==0) return false; //第一位不可能是点
if(add.s[i-1]<'0' || add.s[i-1]>'9') //点的左边和右边必须是数字
return false;
sum++;
}
if(add.s[i]==':') //冒号
{
if(sum!=3) return false; //如果出现了冒号且地址串合法，那么sum必然是3，因为冒号之前必然有 3 个 '.'
if(add.s[i-1]<'0' || add.s[i-1]>'9') //同点的情况
return false;
sum2++;
}
}
if(sum!=3 || sum2!=1) return false; //若点和冒号的个数不合法，那么地址串不合法
//以下判断是否满足 a<=255 && b<=255 && ... && e<=65535
int i=0; long long sa,sb,sc,sd,se; //这几个数表示 a,b,c,d,e 的数值
sa=sb=sc=sd=se=0;
string a,b,c,d,e; //首先把a,b,c,d,e的字符串截取下来
for(i; add.s[i]!='.'; i++)
a+=add.s[i]; i++;
for(i; add.s[i]!='.'; i++)
b+=add.s[i]; i++;
for(i; add.s[i]!='.'; i++)
c+=add.s[i]; i++;
for(i; add.s[i]!=':'; i++)
d+=add.s[i]; i++;
for(i; add.s[i]; i++)
e+=add.s[i];
for(i=0; a[i]; i++) //然后将字符串“转换为”数字
sa=sa*10+a[i]-'0';
for(i=0; b[i]; i++)
sb=sb*10+b[i]-'0';
for(i=0; c[i]; i++)
sc=sc*10+c[i]-'0';
for(i=0; d[i]; i++)
sd=sd*10+d[i]-'0';
for(i=0; e[i]; i++)
se=se*10+e[i]-'0';
if(check(a)&&check(b)&&check(c)&&check(d)&&check(e)&&sa>=0&&sa<=255&&sb>=0&&sb<=255&&sc>=0&&sc<=255&&sd>=0&&sd<=255&&se>=0&&se<=65535) //每个数都不含前导零且满足大小要求
return true;
return false; //其他情况全部是不合法的字串
}
```
接着就可以写主函数了，主函数的功能就是读入、连接网络、输出。此处要注意根据计算机的类型连接：
```cpp
address arr[1005]; //输入的地址
int n;
int main()
{
// freopen("network.in","r",stdin);
// freopen("network.out","w",stdout);
cin>>n;
for(int i=0; i<n; i++)
{
string sss1,sss2;
cin>>sss1>>sss2;
if(sss1=="Server") arr[i].type=ser;
else arr[i].type=cli;
arr[i].s = sss2;
}
for(int i=0; i<n; i++)
{
if(arr[i].type==ser) //服务机
{
if(!is_ok(arr[i])) //不合法直接 ERR
{
cout<<"ERR\n";
goto END; //跳至循环末尾
}
for(int j=0; j<i; j++) //尝试建立连接，必须要求：不能有相同名称的字串
{
if(arr[i].s == arr[j].s && arr[i].type == arr[j].type) //有相同字串就是FAIL，但是要注意的是，客户机和服务机有相同字串是允许的
{
cout<<"FAIL\n";
goto END;
}
}
cout<<"OK\n"; //可以建立连接
goto END;
}
else
{
if(!is_ok(arr[i])) //不合法直接ERR
{
cout<<"ERR\n";
goto END;
}
for(int j=0; j<i; j++) //尝试与服务机建立连接，需要满足要求：1.地址串相同 2.必须是一个服务机和一个客户机连接
{
if(arr[i].s == arr[j].s && arr[i].type != arr[j].type)
{
cout<<j+1<<'\n'; //成功建立连接，输出下标（我这里是下标从0开始，所以需要+1）
goto END;
}
}
cout<<"FAIL\n"; //不能建立连接
goto END;
}
END:
continue;
}
return 0;
}
```
## 完整代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int ser=1,cli=2;
struct address{
int idx;
int type;
string s;
};
bool check(string s)
{
if(s[0]!='0') return true;
if(s.size()==1) return true;
return false;
}
bool is_ok(address add)
{
int sum=0,sum2=0;
if(!isdigit(add.s[add.s.size()-1]))
return false;
for(int i=0; add.s[i]; i++)
{
if(add.s[i]=='.')
{
if(i==0) return false;
if(add.s[i-1]<'0' || add.s[i-1]>'9')
return false;
sum++;
}
if(add.s[i]==':')
{
if(sum!=3) return false;
if(add.s[i-1]<'0' || add.s[i-1]>'9')
return false;
sum2++;
}
}
if(sum!=3 || sum2!=1) return false;
int i=0; long long sa,sb,sc,sd,se;
sa=sb=sc=sd=se=0;
string a,b,c,d,e;
for(i; add.s[i]!='.'; i++)
a+=add.s[i]; i++;
for(i; add.s[i]!='.'; i++)
b+=add.s[i]; i++;
for(i; add.s[i]!='.'; i++)
c+=add.s[i]; i++;
for(i; add.s[i]!=':'; i++)
d+=add.s[i]; i++;
for(i; add.s[i]; i++)
e+=add.s[i];
for(i=0; a[i]; i++)
sa=sa*10+a[i]-'0';
for(i=0; b[i]; i++)
sb=sb*10+b[i]-'0';
for(i=0; c[i]; i++)
sc=sc*10+c[i]-'0';
for(i=0; d[i]; i++)
sd=sd*10+d[i]-'0';
for(i=0; e[i]; i++)
se=se*10+e[i]-'0';
if(check(a)&&check(b)&&check(c)&&check(d)&&check(e)&&sa>=0&&sa<=255&&sb>=0&&sb<=255&&sc>=0&&sc<=255&&sd>=0&&sd<=255&&se>=0&&se<=65535)
return true;
return false;
}
address arr[1005];
int n;
int main()
{
freopen("network.in","r",stdin);
freopen("network.out","w",stdout);
cin>>n;
for(int i=0; i<n; i++)
{
string sss1,sss2;
cin>>sss1>>sss2;
if(sss1=="Server") arr[i].type=ser;
else arr[i].type=cli;
arr[i].s = sss2;
}
for(int i=0; i<n; i++)
{
if(arr[i].type==ser)
{
if(!is_ok(arr[i]))
{
cout<<"ERR\n";
goto END;
}
for(int j=0; j<i; j++)
{
if(arr[i].s == arr[j].s && arr[i].type == arr[j].type)
{
cout<<"FAIL\n";
goto END;
}
}
cout<<"OK\n";
goto END;
}
else
{
if(!is_ok(arr[i]))
{
cout<<"ERR\n";
goto END;
}
for(int j=0; j<i; j++)
{
if(arr[i].s == arr[j].s && arr[i].type != arr[j].type)
{
cout<<j+1<<'\n';
goto END;
}
}
cout<<"FAIL\n";
goto END;
}
END:
continue;
}
return 0;
}
/*
5
Server 192.168.1.1:8080
Server 192.168.1.1:8080
Client 192.168.1.1:8080
Client 192.168.1.1:80
Client 192.168.1.1:99999
*/
```