【题目来源】https://www.luogu.com.cn/problem/P7911【题目描述】TCP/IP 协议是网络通信领域的一项重要协议。今天你的任务就是尝试利用这个协议还原一个简化后的网络连接场景。在本问题中计算机分为两大类服务机Server和客户机Client。服务机负责建立连接客户机负责加入连接。需要进行网络连接的计算机共有 n 台编号为 1∼n这些机器将按编号递增的顺序依次发起一条建立连接或加入连接的操作。每台机器在尝试建立或加入连接时需要提供一个地址串。服务机提供的地址串表示它尝试建立连接的地址客户机提供的地址串表示它尝试加入连接的地址。一个符合规范的地址串应当具有以下特征1必须形如a.b.c.d:e的格式其中 a,b,c,d,e 均为非负整数20≤a,b,c,d≤2550≤e≤655353a,b,c,d,e 均不能含有多余的前导 0。相应地不符合规范的地址串可能具有以下特征1不是形如 a.b.c.d:e 格式的字符串例如含有多于 3 个字符 . 或多于 1 个字符 : 等情况2整数 a,b,c,d,e 中某一个或多个超出上述范围3整数 a,b,c,d,e 中某一个或多个含有多余的前导 0。例如地址串 192.168.0.255:80 是符合规范的但 192.168.0.999:80、192.168.00.1:10、192.168.0.1:088、192:168:0:1.233 均是不符合规范的。如果服务机或客户机在发起操作时提供的地址串不符合规范这条操作将被直接忽略。在本问题中我们假定凡是符合上述规范的地址串均可参与正常的连接你无需考虑每个地址串的实际意义。由于网络阻塞等原因不允许两台服务机使用相同的地址串如果此类现象发生后一台尝试建立连接的服务机将会无法成功建立连接除此之外凡是提供符合规范的地址串的服务机均可成功建立连接。如果某台提供符合规范的地址的客户机在尝试加入连接时与先前某台已经成功建立连接的服务机提供的地址串相同这台客户机就可以成功加入连接并称其连接到这台服务机如果找不到这样的服务机则认为这台客户机无法成功加入连接。请注意尽管不允许两台不同的服务机使用相同的地址串但多台客户机使用同样的地址串以及同一台服务机同时被多台客户机连接的情况是被允许的。你的任务很简单在给出每台计算机的类型以及地址串之后判断这台计算机的连接情况。【输入格式】第一行一个正整数 n。接下来 n 行每行两个字符串 op,ad按照编号从小到大给出每台计算机的类型及地址串。其中 op 保证为字符串 Server 或 Client 之一ad 为一个长度不超过 25 的仅由数字、字符 . 和字符 : 组成的非空字符串。每行的两个字符串之间用恰好一个空格分隔开每行的末尾没有多余的空格。【输出格式】输出共 n 行每行一个正整数或字符串表示第 i 台计算机的连接状态。其中如果第 i 台计算机为服务机则1如果其提供符合规范的地址串且成功建立连接输出字符串 OK。2如果其提供符合规范的地址串但由于先前有相同地址串的服务机而无法成功建立连接输出字符串 FAIL。3如果其提供的地址串不是符合规范的地址串输出字符串 ERR。如果第 i 台计算机为客户机则1如果其提供符合规范的地址串且成功加入连接输出一个正整数表示这台客户机连接到的服务机的编号。2如果其提供符合规范的地址串但无法成功加入连接时输出字符串 FAIL。3如果其提供的地址串不是符合规范的地址串输出字符串 ERR。【输入样例】10Server 192.168.1.1:80Client 192.168.1.1:80Client 192.168.1.1:8080Server 192.168.1.1:80Server 192.168.1.1:8080Server 192.168.1.999:0Client 192.168.1.1.8080Client 192.168.1.1:8080Client 192.168.1.1:80Client 192.168.1.999:0【输出样例】OK1FAILFAILOKERRERR51ERR【数据范围】对于 100% 的数据保证 1≤n≤1000。【算法分析】● 本题主要考核点1. 字符串处理核心考点- 字符串分割按 . 和 : 分割 IP 与端口判断符号数量是否正确- 前导零判断01、088 属于非法0 本身合法- 字符串转数字数字范围校验0‑255、0‑65535- 空片段判断例如 192..1.1:80 分割出空字符串直接非法。2. 哈希映射STL 容器- 使用unordered_map建立【地址串→服务机编号】映射- Server检查地址是否已存在不存在就存入 map- Client直接查询 map 里有没有该地址。3. 模拟、阅读理解、细节边界- 机器编号从 1 开始按顺序处理 n 条操作- 地址不合法直接忽略操作输出 ERR- Server 合法但地址重复输出 FAIL- Client 合法地址找不到对应 Server 输出 FAIL- 大量坑点前导零、符号数量、数字越界、空片段很容易 WA。4. 边界样例坑总结- 0.0.0.0:0合法- 01.0.0.0:0前导零ERR- 1.2.3.4:0080端口前导零ERR- 256.1.1.1:10数字越界 ERR- 1.2.3:80点数量不对 ERR- 1.2.3.4.5:80点过多 ERR。提示此题不要自己拼接字符串作为 key直接拿原始输入的 ad 字符串作为 map 的键避免拼接出错。● string::find 返回类型1找到返回该字符 / 子串的下标下标从 0 开始。2没找到返回常量 string::nposnpos 的类型是 size_t。● string::npos 等于 find 函数没找到的标记string::npos 是 C 中 std::string 类的一个静态常量size_t是 C/C 标准库定义的一种无符号整数类型通常对应 unsigned int 或 unsigned long取决于平台位数。string::npos 的值为 size_t 类型能表示的最大值即32 位系统429496729564 位系统18446744073709551615。在实际开发中你不需要记住具体数值只需要知道用 string::npos 来判断查找是否失败即可。string sabcdef; size_t poss.find(x); if(posstring::npos) { //Character x was not found. }注意不要用 int 类型变量接收 find() 的返回值再与 npos 比较否则可能因为类型转换导致判断失效。//wrong string sabcdef; int poss.find(x); if(pos-1) {...}● 代码 if(ad.find(:,colon_pos1)!string::npos) return false; 解析- colon_pos第一个冒号 : 的下标。-ad.find(:, colon_pos1)从下标 colon_pos1 的位置开始向后再找下一个冒号。- 如果不等于 string::npos → 又找到了一个冒号说明字符串里至少有两个冒号 :格式非法直接 return false。● 代码 string ip_partad.substr(0,colon_pos); 解析- 第一个参数起始下标从 0 开始-第二个参数截取的字符个数不是结束下标所以这句代码的含义是从下标 0 开始截取一共 colon_pos 个字符正好拿到冒号前面整段 IP 部分a.b.c.d。● 自定义函数中变量 val 的类型要定义为long long型否则会有 8 个样例不过。【算法代码】#include bits/stdc.h using namespace std; bool check(string ad,int a,int b,int c,int d,int e) { size_t colon_posad.find(:); if(colon_posstring::npos) return false; if(ad.find(:,colon_pos1)!string::npos) return false; string ip_partad.substr(0,colon_pos); string port_strad.substr(colon_pos1); //Separate the ip section vectorstring ip_sec; size_t pre0; for(size_t i0; iip_part.size(); i) { if(ip_part[i].) { ip_sec.push_back(ip_part.substr(pre,i-pre)); prei1; } } ip_sec.push_back(ip_part.substr(pre)); if(ip_sec.size()!4) return false; ip_sec.push_back(port_str); //0:a,1:b,2:c,3:d,4:e //Verify each segment: leading zeros range int limit[] {255,255,255,255,65535}; int num[5]; for(int i0; i5; i) { string sip_sec[i]; if(s.empty()) return false; if(s.size()1 s[0]0) return false; long long val0; for(char ch:s) { if(!(ch0 ch9)) return false; valval*10(ch-0); } if(vallimit[i]) return false; num[i]val; } anum[0],bnum[1],cnum[2],dnum[3],enum[4]; return true; } int main() { int n; cinn; unordered_mapstring,int server_map; for(int id1; idn; id) { string op,ad; cinopad; int a,b,c,d,e; bool validcheck(ad,a,b,c,d,e); if(!valid) { coutERR\n; continue; } if(opServer) { if(server_map.count(ad)) coutFAIL\n; else { server_map[ad]id; coutOK\n; } } else { //Client if(server_map.count(ad)) coutserver_map[ad]endl; else coutFAIL\n; } } return 0; } /* in: 10 Server 192.168.1.1:80 Client 192.168.1.1:80 Client 192.168.1.1:8080 Server 192.168.1.1:80 Server 192.168.1.1:8080 Server 192.168.1.999:0 Client 192.168.1.1.8080 Client 192.168.1.1:8080 Client 192.168.1.1:80 Client 192.168.1.999:0 out: OK 1 FAIL FAIL OK ERR ERR 5 1 ERR */【参考文献】https://www.luogu.com.cn/problem/solution/P7911