CSP CCF： 202104-3 DHCP服务器 （C++）

• 题目来源
• 解题过程
• • 暴力解法 100分
  • 非暴力解法 （只有想法）

链接: DHCP服务器.

1. 通读了一遍题目后，可以看出来，我们主要是实现 对收到的报文进行格式检查、返回正确格式下的DIS、REQ报文内容对应的报文。格式检查可融入到对DIS、REQ报文的回复中。
2. 对 DIS 报文

if (messType == "DIS" && recvHost == "*") {
  // 找合适的IP地址
   long long int ip = choseIP(sendHost);
   if (ip == 0) {
       continue;
   }

   // 修改 IP 地址状态
   ips[ip].state = 1;  // 将该 IP 地址状态设置为待分配，
   ips[ip].host = sendHost;  // 占用者设置为发送主机；

   // 设置过期时刻
   long long int eT = setExpireTime(ti, expiTime);
   ips[ip].expiTime = eT;

   // 向发送主机发送 Offer 报文，其中，IP 地址为选定的 IP 地址，过期时刻为所设定的过期时刻
   cout< 
对 REQ 报文
 
else if (messType == "REQ" && recvHost != "*"){
	// 接收主机是本服务器
    if (recvHost == H) {
        // 检查报文中的 IP 地址是否在地址池内，且其占用者为发送主机，若不是，则向发送主机发送 Nak 报文，处理结束；
        bool flag = false;

        //if ( (ips[ipAddr].state == 1 || ips[ipAddr].state == 2 || ips[ipAddr].state == 3) && ips[ipAddr].host == sendHost) {
        if (ipAddr > 0 && ipAddr <= n && ips[ipAddr].state != 0 && ips[ipAddr].host == sendHost) {
            flag = true;
        }
        if ( !flag) {
            cout<
        cleanUseless(sendHost);
    }
}
 
完整代码
 
#include 
#include 
#include 

using namespace std;
// 定义 IP 结构体
struct IP {
    string host;  // 分配给的主机的名称
    int state;  // 0: 未分配； 1: 待分配； 2:: 占用中； 3:过期了;
    long long int expiTime;  // 过期时刻
};

const long long int ipNum = 10001;  // ip池大小
IP ips[ipNum];

long long int N, Tdef, Tmax, Tmin;
string H;
long long int n;

// 初始化 IP池
void initIPstate() {
    for (long long int i = 1; i <= N; ++i) {
        ips[i].state = 0;
        ips[i].host = "";
        ips[i].expiTime = 0;
    }
}


// 选择 合适的 IP
long long int choseIP(string &sendHost) {
    long long int ip = 0;

    // 是否有占有者为发送主机的IP地址
    for (long long int i = 1; i <= N; ++i) {
        if ((ips[i].state == 1 || ips[i].state == 2 || ips[i].state == 3) && ips[i].host == sendHost) {
            ip = i;
            break;
        }
    }
    if (ip != 0) return ip;
    // 没有，则选取最小的状态为未分配的 IP 地址
    for (long long int i = 1; i <= N; ++i) {
        if (ips[i].state == 0) {
            ip = i;
            break;
        }
    }
    if (ip != 0) return ip;
    // 若没有，则选取最小的状态为过期的 IP 地址；
    for (long long int i = 1; i <= N; ++i) {
        if (ips[i].state == 3) {
            ip = i;
            break;
        }
    }
    if (ip != 0) return ip;
    // 若没有，则不处理该报文，处理结束；
    return ip;
}


// 设置 过期时间
long long int setExpireTime(long long int &t, long long int &expiTime) {
    long long int eT;
    // 若报文中过期时刻为 0 ，则设置过期时刻为 t + Tdef
    if (expiTime == 0) {
        eT = t + Tdef;
    }
    // 否则根据报文中的过期时刻和收到报文的时刻计算过期时间，判断是否超过上下限
    // 若没有超过，则设置过期时刻为报文中的过期时刻
    else if ((expiTime - t) >= Tmin && (expiTime - t) <= Tmax) {
        eT = expiTime;
    }
    // 否则则根据超限情况设置为允许的最早或最晚的过期时刻
    else if ((expiTime - t) < Tmin) {
        eT = t + Tmin;
    }
    else if ((expiTime - t) > Tmax) {
        eT = t + Tmax;
    }

    return eT;
}


// 将待分配、占用ip中过期的给处理掉
void cleanIpAddress(long long int &ti, string &sendHost) {
    for (long long int i = 1; i <= N; ++i) {
        // 删掉 if， 从 90-100分。 
        // 主要原因是：当host == sendHost && expiTime == ti && messType == "REQ" && ipAddr ！= i 时 ip[i] 的状态需要改变， 而我之前的做法没有考虑到这一点。
       // 但我不懂， 如果还是上述的条件， 但ipAddr == i && ips[i].state == 1， 那转换了状态不就错了嘛？———————— 再看了一下题目，"在到达该过期时刻时，若该地址的状态是待分配，则该地址的状态会自动变为未分配，且占用者清空，过期时刻清零；"。所以 此时它已经过期了，不能再作为待分配状态了。
        
		 // 待分配的ip到期便转换成未分配状态；
        if (ips[i].state == 1 && ips[i].expiTime <= ti) {
            ips[i].state = 0;
            ips[i].host = "";
            ips[i].expiTime = 0;
        }
        // 占用中的ip到期便转换为过期状态；
        else if (ips[i].state == 2 && ips[i].expiTime <= ti) {
            ips[i].state = 3;
            ips[i].expiTime = 0;
        }
    }
}


// 当主机不是本机且报文类型为“REQ”时， 处理发送主机在本机的ip的状态
void cleanUseless(string &sendhost) {
    // 找到占用者为发送主机的所有 IP 地址，对于其中状态为待分配的，将其状态设置为未分配，并清空其占用者，清零其过期时刻，处理结束；
    for (long long int i = 1; i <= n; ++i) {
        if (ips[i].host == sendhost && ips[i].state == 1) {  // 不要忘记 ips[i].state == 1 ！！！ 没有的话只有 60 分， 有的话有90分。
            ips[i].state = 0;
            ips[i].expiTime = 0;
            ips[i].host = "";
        }
    }
}


int main() {
    //ifstream cin("in.txt");

    cin>>N>>Tdef>>Tmax>>Tmin>>H;
    cin>>n;

    initIPstate();

    for (long long int i = 0; i < n; ++i) {
        long long int ti, ipAddr, expiTime;
        string sendHost, recvHost, messType;
        cin>>ti>>sendHost>>recvHost>>messType>>ipAddr>>expiTime;

        cleanIpAddress(ti, sendHost);
        // DIS
        if (messType == "DIS" && recvHost == "*") {
            // 找合适的IP地址
            long long int ip = choseIP(sendHost);
            if (ip == 0) {
                continue;
            }

            // 修改 IP 地址状态
            ips[ip].state = 1;  // 将该 IP 地址状态设置为待分配，
            ips[ip].host = sendHost;  // 占用者设置为发送主机；

            // 设置过期时刻
            long long int eT = setExpireTime(ti, expiTime);
            ips[ip].expiTime = eT;

            // 向发送主机发送 Offer 报文，其中，IP 地址为选定的 IP 地址，过期时刻为所设定的过期时刻
            cout<
            if (recvHost == H) {
                // 检查报文中的 IP 地址是否在地址池内，且其占用者为发送主机，若不是，则向发送主机发送 Nak 报文，处理结束；
                bool flag = false;

                if (ipAddr > 0 && ipAddr <= n && ips[ipAddr].state != 0 && ips[ipAddr].host == sendHost) {
                    flag = true;
                }
                if ( !flag) {
                    cout<
                cleanUseless(sendHost);
            }
        }
        //  不用管
    }

    return 0;
}

 
非暴力解法 （只有想法） 
关键思路： 将发送者的名称 (sendHost) 与 ip(ips[i]) 连接 。 通过一个 map name2ip ({sendHost, i})实现。
代码 (略)