题目关键点:
-
DHCP 数据报文的格式如下:
<发送主机> <接收主机> <报文类型> <IP 地址> <过期时刻>
DHCP 数据报文的各个部分由空格分隔,其各个部分的定义如下:发送主机:是发送报文的主机名,主机名是由小写字母、数字组成的字符串,唯一地表示了一个主机;
接收主机:当有特定的接收主机时,是接收报文的主机名;当没有特定的接收主机时,为一个星号(*);
报文类型:是三个大写字母,取值如下:
DIS:表示 Discover 报文;
OFR:表示 Offer 报文;
REQ:表示 Request 报文;
ACK:表示 Ack 报文;
NAK:表示 Nak 报文;
IP 地址,是一个非负整数:
1.对于 Discover 报文,该部分在发送的时候为 0,在接收的时候忽略;
2.对于其它报文,为正整数,表示一个 IP 地址;
3.过期时刻,是一个非负整数:
3.1对于 Offer、Ack 报文,是一个正整数,表示服务器授予客户端的 IP 地址的过期时刻;
3.2对于 Discover、Request 报文,若为正整数,表示客户端期望服务器授予的过期时刻;
3.3对于其它报文,该部分在发送的时候为 0,在接收的时候忽略。
2.处理细节如下:
//continue
判断接收主机是否为本机,或者为 *,若不是,则判断类型是否为 Request,若不是,则不处理;
若类型不是 Discover、Request 之一,则不处理;
若接收主机为 *,但类型不是 Discover,或接收主机是本机,但类型是 Discover,则不处理。
//DIS
对于 Discover 报文,按照下述方法处理:
1.检查是否有占用者为发送主机的 IP 地址:
若有,则选取该 IP 地址;
若没有,则选取最小的状态为未分配的 IP 地址;
若没有,则选取最小的状态为过期的 IP 地址;
若没有,则不处理该报文,处理结束;
2.将该 IP 地址状态设置为待分配,占用者设置为发送主机;
3.若报文中过期时刻为 0 ,则设置过期时刻为t+Tdef;否则根据报文中的过期时刻和收到报文的时刻计算过期时间,判断是否超过上下限:若没有超过,则设置过期时刻为报文中的过期时刻;否则则根据超限情况设置为允许的最早或最晚的过期时刻;
4.向发送主机发送 Offer 报文,其中,IP 地址为选定的 IP 地址,过期时刻为所设定的过期时刻。
//REQ
对于 Request 报文,按照下述方法处理:
1.检查接收主机是否为本机:
若不是,则找到占用者为发送主机的所有IP地址,对于其中状态为待分配的,将其状态设置为未分配,并清空其占用者,清零其过期时刻,处理结束;
2.检查报文中的 IP 地址是否在地址池内,且其占用者为发送主机,若不是,则向发送主机发送 Nak 报文,处理结束;
3.无论该 IP 地址的状态为何,将该 IP 地址的状态设置为占用;
4.与 Discover 报文相同的方法,设置 IP 地址的过期时刻;
5.向发送主机发送 Ack 报文。
题目分析:
根据上述题目关键点以及题目大意:
1.我们要维护N个ip地址,在这个ip地址中维护地址状态,到期时间,占用者,所以简单方法我们可以使用结构体存储:
struct IP
{
int state;//0:未分配,1:待分配,2 占用, 3:过期
int times;//过期时间
string ocupy;//占用者
}id[N];//ip地址编号从1开始
2.剩下就是处理输入的m条报文数据:
我们每读入一条数据就要进行一次状态更新,主要是将过期的ip占用者和过期时间更改一下;以及对新分配的ip地址进行赋值。
2.1:通过关键点主要是三部分:对于一些不满足条件直接continue;DIS;REQ。
这三个状态根据题目描述写出即可。
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e4 + 10;
struct IP
{
int state;//0:未分配,1:待分配,2 占用, 3:过期
int times;//过期时间
string ocupy;//占用者
}id[N];//ip地址编号从1开始
int n, m, t_def, t_max, t_min;//n : 地址池大小, m:处理报文数量,
string dhcp;//服务器名称
void update(int t)//更新
{
for (int i = 1; i <= n; i ++)
if (id[i].times && id[i].times <= t)//时刻到期
{
if (id[i].state == 1)
{
id[i].state = 0;
id[i].ocupy = "";
id[i].times = 0;
}
else
{
id[i].state = 3;
id[i].times = 0;
}
}
}
//将常用部分代码抽象为函数:get_id_ip(string);get_id_state(int)
int get_id_ip(string address)//通过地址获取ip地址
{
for (int i = 1; i <= n; i ++)
if (id[i].ocupy == address)return i;
return 0;
}
int get_id_state(int state)//通过状态获取ip地址
{
for (int i = 1; i <= n; i ++)
if (id[i].state == state)return i;
return 0;
}
int main()
{
cin >> n >> t_def >> t_max >> t_min >> dhcp;
int tc;
string server, client, type;//发送, 服务, 类型
int address, t;
cin >> m;
while(m --)
{
cin >> tc >> server >> client >> type >> address >> t;//这里的server 与 client和y总的相反
//非本机非*非request
//首先处理continue的部分
update(tc);//每次根据到达时刻更新状态,和下面两个位置都可以,只要记得更新即可
if (client != dhcp && client != "*")
{
if (type != "REQ")continue;
}
if (type != "REQ" && type != "DIS")continue;
if (client == "*" && type != "DIS" || client == dhcp && type == "DIS")continue;
//update(tc);//每次根据到达时刻更新状态
if (type == "DIS")//处理DIS
{
int k = get_id_ip(server);
if (!k) k = get_id_state(0);
if (!k) k = get_id_state(3);
if (!k) continue;
id[k].state = 1, id[k].ocupy = server;
if (t == 0)id[k].times = tc + t_def;
else
{
int tt = t - tc;
tt = min(tt, t_max);
tt = max(tt, t_min);
id[k].times = tt + tc;
}
cout << dhcp << " " << server << " OFR " << k << " " << id[k].times << endl;
}
else if (type == "REQ")//处理REQ
{
if (client != dhcp)
{
for (int i = 1; i <= n; i ++)
{
if (id[i].ocupy == server && id[i].state == 1)
{
id[i].state = 0;
id[i].ocupy = "";
id[i].times = 0;
}
}
continue;
}
if (!(address >= 1 && address <= n && id[address].ocupy == server))
{
cout << dhcp << " " << server << " NAK " << address << " " << 0 << endl;
continue;
}
id[address].state = 2;
if (t == 0)id[address].times = tc + t_def;
else
{
int tt = t - tc;
tt = min(tt, t_max);
tt = max(tt, t_min);
id[address].times = tt + tc;
}
cout << dhcp << " " << server << " ACK " << address << " " << id[address].times << endl;
}
}
return 0;
}