ccf-csp:202104-3 DHCP服务器
问题描述
| 试题编号： | 202104-3 |
| 试题名称： | DHCP服务器 |
| 时间限制： | 1.0s |
| 内存限制： | 512.0MB |
| 问题描述： | 试题背景动态主机配置协议（Dynamic Host Configuration Protocol, DHCP）是一种自动为网络客户端分配 IP 地址的网络协议。当支持该协议的计算机刚刚接入网络时，它可以启动一个 DHCP 客户端程序。后者可以通过一定的网络报文交互，从 DHCP 服务器上获得 IP 地址等网络配置参数，从而能够在用户不干预的情况下，自动完成对计算机的网络设置，方便用户连接网络。DHCP 协议的工作过程如下：
在本题目中，你需要理解 DHCP 协议的工作过程，并按照题目的要求实现一个简单的 DHCP 服务器。 问题描述报文格式为了便于实现，我们简化地规定 DHCP 数据报文的格式如下： None DHCP 数据报文的各个部分由空格分隔，其各个部分的定义如下：
例如下列都是合法的 DHCP 数据报文： a * DIS 0 0 服务器配置为了 DHCP 服务器能够正确分配 IP 地址，DHCP 需要接受如下配置：
分配策略当客户端请求 IP 地址时，首先检查此前是否给该客户端分配过 IP 地址，且该 IP 地址在此后没有被分配给其它客户端。如果是这样的情况，则直接将 IP 地址分配给它，否则， 实现细节在 DHCP 启动时，首先初始化 IP 地址池，将所有地址设置状态为未分配，占用者为空，并清零过期时刻。 对于收到的报文，设其收到的时刻为 t。处理细节如下：
对于 Discover 报文，按照下述方法处理：
对于 Request 报文，按照下述方法处理：
上述处理过程中，地址池中地址的状态的变化可以概括为如下图所示的状态转移图。为了简洁，该图中没有涵盖需要回复 Nak 报文的情况。 输入格式输入的第一行包含用空格分隔的四个正整数和一个字符串，分别是：N、Tdef、Tmax、Tmin 和 H，保证 Tmin≤Tdef≤Tmax。 输入的第二行是一个正整数 n，表示收到了 n 个报文。 输入接下来有 n 行，第 (i+2) 行有空格分隔的正整数 ti 和约定格式的报文 Pi。表示收到的第 i 个报文是在 ti 时刻收到的，报文内容是 Pi。保证 ti 输出有若干行，每行是一个约定格式的报文。依次输出 DHCP 服务器发送的报文。 输入第一行，分别设置了 DHCP 的相关参数，并收到了 16 个报文。 第 1 个报文和第 2 个报文是客户端 第 3 个报文不符合 Discover 报文的要求，不做任何处理。 第 4 个报文 第 5 个报文中，Request 报文不符合接收主机是 DHCP 服务器本机的要求，因此不做任何处理。 第 6 个报文是 第 7 个报文中，过期时刻 11 小于最短过期时间，因此返回的过期时刻是 12。虽然此时为 第 9、10 两个报文中，为 第 11 个报文中， 第 12 个报文中， 第 13、14 个报文中， 第 15 个报文中， 第 16 个报文中， 在本样例中，DHCP 服务器一共收到了 6 个报文，处理情况如下： 第 1 个报文不是 DHCP 服务器需要处理的报文，因此不回复任何报文。 第 2 个报文中， 第 3 个报文中， 第 4 个报文中， 第 5、6 个报文中， 对于 20% 的数据，有 N≤200，且 n≤N，且输入仅含 Discover 报文，且 t 对于 50% 的数据，有 N≤200，且 n≤N，且 t 对于 70% 的数据，有 N≤1000，且 n≤N，且报文的接收主机或为本机，或为 对于 100% 的数据，有 N≤10000，且 n≤10000，主机名的长度不超过 20，且 t,Tmin,Tdefault,Tmax≤109，输入的报文格式符合题目要求，且数字不超过 109。 |
#include
using namespace std;
int N,tmin,tdef,tmax,n;
string h;struct pd
{string owner;int zhuang;//表示当前状态,0:未分配,1:待分配,2:占用,3:过期 int t;//过期时刻
}p[10010];void add(int x)
{for(int i=1;i<=N;i++){if(p[i].t>0 && p[i].t<=x){if(p[i].zhuang==1){p[i].zhuang=0;p[i].owner="";p[i].t=0;}else{p[i].zhuang=3;p[i].t=0;}}}
}int get_owner(string x)
{for(int i=1;i<=N;i++){if(p[i].owner==x){return i;}}return 0;
}int get_zhuang(int x)
{for(int i=1;i<=N;i++){if(p[i].zhuang==x){return i;}}return 0;
}int main()
{cin>>N>>tdef>>tmax>>tmin>>h;cin>>n;for(int i=1;i<=n;i++){int tnow,ip,out;//当前时间,IP地址,过期时刻string fasong,jieshou,type;//发送主机,接收主机,报文类型cin >> tnow>>fasong>>jieshou>>type>>ip>>out;//对于收到的报文,设其收到的时刻为t,处理细节如下：if(jieshou!=h && jieshou!="*"){if(type!="REQ") continue;}if(type!="DIS" && type!="REQ") continue;if((jieshou=="*" && type!="DIS") || (jieshou==h && type=="DIS"))continue;add(tnow);//对于 Discover 报文:if(type=="DIS"){//1.检查是否有占用者为发送主机的ip地址int k=get_owner(fasong);if(k==0) k=get_zhuang(0);if(k==0) k=get_zhuang(3);if(k==0) continue;//2.将ip地址设置为待分配，占用者设置为发送主机p[k].zhuang=1;p[k].owner=fasong;//3.如果报文过期时刻为0，则设置过期时刻为t+Tdefif(out==0){p[k].t=tnow+tdef;}else{int kk=out-tnow;kk=max(kk,tmin);kk=min(kk,tmax);p[k].t=kk+tnow;}cout<< h <<" "<=1 && ip<=N && p[ip].owner==fasong)){cout<< h <<" "<