目錄
試題背景
問題描述
報文格式
服務器配置
分配策略
實作細節
輸入格式
輸出格式
樣例輸入
樣例輸出
樣例說明
樣例輸入
樣例輸出
樣例說明
評測用例規模與約定
我滴解題思路~
滿分代碼如下
???????
這個題目來自于ccf認證考試2021年四月的第三題
試題背景
動態主機配置協議（Dynamic Host Configuration Protocol, DHCP）是一種自動為網路客戶端分配 IP 地址的網路協議，當支持該協議的計算機剛剛接入網路時，它可以啟動一個 DHCP 客戶端程式，后者可以通過一定的網路報文互動，從 DHCP 服務器上獲得 IP 地址等網路配置引數，從而能夠在用戶不干預的情況下，自動完成對計算機的網路設定，方便用戶連接網路，DHCP 協議的作業程序如下：
- 當 DHCP 協議啟動的時候，DHCP 客戶端向網路中廣播發送 Discover 報文，請求 IP 地址配置；
- 當 DHCP 服務器收到 Discover 報文時，DHCP 服務器根據報文中的引數選擇一個尚未分配的 IP 地址，分配給該客戶端，DHCP 服務器用 Offer 報文將這個資訊傳達給客戶端；
- 客戶端收集收到的 Offer 報文，由于網路中可能存在多于一個 DHCP 服務器，因此客戶端可能收集到多個 Offer 報文，客戶端從這些報文中選擇一個，并向網路中廣播 Request 報文，表示選擇這個 DHCP 服務器發送的配置；
- DHCP 服務器收到 Request 報文后，首先判斷該客戶端是否選擇本服務器分配的地址：如果不是，則在本服務器上解除對那個 IP 地址的占用；否則則再次確認分配的地址有效，并向客戶端發送 Ack 報文，表示確認配置有效，Ack 報文中包括配置的有效時間，如果 DHCP 發現分配的地址無效，則回傳 Nak 報文；
- 客戶端收到 Ack 報文后，確認服務器分配的地址有效，即確認服務器分配的地址未被其它客戶端占用，則完成網路配置，同時記錄配置的有效時間，出于簡化的目的，我們不考慮被占用的情況，若客戶端收到 Nak 報文，則從步驟 1 重新開始；
- 客戶端在到達配置的有效時間前，再次向 DHCP 服務器發送 Request 報文，表示希望延長 IP 地址的有效期，DHCP 服務器按照步驟 4 確定是否延長，客戶端按照步驟 5 處理后續的配置；
在本題目中，你需要理解 DHCP 協議的作業程序，并按照題目的要求實作一個簡單的 DHCP 服務器，
問題描述
報文格式
為了便于實作，我們簡化地規定 DHCP 資料報文的格式如下：
<發送主機> <接收主機> <報文型別> <IP 地址> <過期時刻>None
DHCP 資料報文的各個部分由空格分隔，其各個部分的定義如下：
- 發送主機：是發送報文的主機名，主機名是由小寫字母、數字組成的字串，唯一地表示了一個主機；
- 接收主機：當有特定的接收主機時，是接收報文的主機名；當沒有特定的接收主機時，為一個星號（
*）； - 報文型別：是三個大寫字母，取值如下：
DIS：表示 Discover 報文；OFR：表示 Offer 報文；REQ：表示 Request 報文；ACK：表示 Ack 報文；NAK：表示 Nak 報文；
- IP 地址，是一個非負整數：
- 對于 Discover 報文，該部分在發送的時候為 0，在接收的時候忽略；
- 對于其它報文，為正整數，表示一個 IP 地址；
- 過期時刻，是一個非負整數：
- 對于 Offer、Ack 報文，是一個正整數，表示服務器授予客戶端的 IP 地址的過期時刻；
- 對于 Discover、Request 報文，若為正整數，表示客戶端期望服務器授予的過期時刻；
- 對于其它報文，該部分在發送的時候為 0，在接收的時候忽略，
例如下列都是合法的 DHCP 資料報文：
a * DIS 0 0
d a ACK 50 1000None
服務器配置
為了 DHCP 服務器能夠正確分配 IP 地址，DHCP 需要接受如下配置：
- 地址池大小 N：表示能夠分配給客戶端的 IP 地址的數目，且能分配的 IP 地址是 1,2,…,N；
- 默認過期時間 Tdef：表示分配給客戶端的 IP 地址的默認的過期時間長度；
- 過期時間的上限和下限 Tmax、Tmin：表示分配給客戶端的 IP 地址的最長過期時間長度和最短過期時間長度，客戶端不能請求比這個更長或更短的過期時間；
- 本機名稱 H：表示運行 DHCP 服務器的主機名，
分配策略
當客戶端請求 IP 地址時，首先檢查此前是否給該客戶端分配過 IP 地址，且該 IP 地址在此后沒有被分配給其它客戶端，如果是這樣的情況，則直接將 IP 地址分配給它，否則，
總是分配給它最小的尚未占用過的那個 IP 地址，如果這樣的地址不存在，則分配給它最小的此時未被占用的那個 IP 地址，如果這樣的地址也不存在，說明地址池已經分配完畢，因此拒絕分配地址，
實作細節
在 DHCP 啟動時，首先初始化 IP 地址池，將所有地址設定狀態為未分配，占用者為空，并清零過期時刻，
其中地址的狀態有未分配、待分配、占用、過期四種，
處于未分配狀態的 IP 地址沒有占用者，而其余三種狀態的 IP 地址均有一名占用者，
處于待分配和占用狀態的 IP 地址擁有一個大于零的過期時刻，在到達該過期時刻時，若該地址的狀態是待分配，則該地址的狀態會自動變為未分配，且占用者清空，過期時刻清零；否則該地址的狀態會由占用自動變為過期，且過期時刻清零，處于未分配和過期狀態的 IP 地址過期時刻為零，即沒有過期時刻，
對于收到的報文，設其收到的時刻為 t，處理細節如下：
- 判斷接收主機是否為本機，或者為
*，若不是，則判斷型別是否為 Request，若不是，則不處理； - 若型別不是 Discover、Request 之一，則不處理；
- 若接收主機為
*，但型別不是 Discover，或接收主機是本機，但型別是 Discover，則不處理，
對于 Discover 報文，按照下述方法處理：
- 檢查是否有占用者為發送主機的 IP 地址：
- 若有，則選取該 IP 地址；
- 若沒有，則選取最小的狀態為未分配的 IP 地址；
- 若沒有，則選取最小的狀態為過期的 IP 地址；
- 若沒有，則不處理該報文，處理結束；
- 將該 IP 地址狀態設定為待分配，占用者設定為發送主機；
- 若報文中過期時刻為 0 ，則設定過期時刻為 t+Tdef；否則根據報文中的過期時刻和收到報文的時刻計算過期時間，判斷是否超過上下限：若沒有超過，則設定過期時刻為報文中的過期時刻；否則則根據超限情況設定為允許的最早或最晚的過期時刻；
- 向發送主機發送 Offer 報文，其中，IP 地址為選定的 IP 地址，過期時刻為所設定的過期時刻，
對于 Request 報文，按照下述方法處理：
- 檢查接收主機是否為本機：
- 若不是，則找到占用者為發送主機的所有 IP 地址，對于其中狀態為待分配的，將其狀態設定為未分配，并清空其占用者，清零其過期時刻，處理結束；
- 檢查報文中的 IP 地址是否在地址池內，且其占用者為發送主機，若不是，則向發送主機發送 Nak 報文，處理結束；
- 無論該 IP 地址的狀態為何，將該 IP 地址的狀態設定為占用；
- 與 Discover 報文相同的方法，設定 IP 地址的過期時刻；
- 向發送主機發送 Ack 報文，
上述處理程序中，地址池中地址的狀態的變化可以概括為如下圖所示的狀態轉移圖，為了簡潔，該圖中沒有涵蓋需要回復 Nak 報文的情況，
輸入格式
輸入的第一行包含用空格分隔的四個正整數和一個字串，分別是：N、Tdef、Tmax、Tmin 和 H，保證 Tmin≤Tdef≤Tmax，
輸入的第二行是一個正整數 n，表示收到了 n 個報文，
輸入接下來有 n 行，第 (i+2) 行有空格分隔的正整數 ti 和約定格式的報文 Pi，表示收到的第 i 個報文是在 ti 時刻收到的，報文內容是 Pi，保證 ti<ti+1，
輸出格式
輸出有若干行，每行是一個約定格式的報文，依次輸出 DHCP 服務器發送的報文，
樣例輸入
4 5 10 5 dhcp
16
1 a * DIS 0 0
2 a dhcp REQ 1 0
3 b a DIS 0 0
4 b * DIS 3 0
5 b * REQ 2 12
6 b dhcp REQ 2 12
7 c * DIS 0 11
8 c dhcp REQ 3 11
9 d * DIS 0 0
10 d dhcp REQ 4 20
11 a dhcp REQ 1 20
12 c dhcp REQ 3 20
13 e * DIS 0 0
14 e dhcp REQ 2 0
15 b dhcp REQ 2 25
16 b * DIS 0 0Data
樣例輸出
dhcp a OFR 1 6
dhcp a ACK 1 7
dhcp b OFR 2 9
dhcp b ACK 2 12
dhcp c OFR 3 12
dhcp c ACK 3 13
dhcp d OFR 4 14
dhcp d ACK 4 20
dhcp a ACK 1 20
dhcp c ACK 3 20
dhcp e OFR 2 18
dhcp e ACK 2 19
dhcp b NAK 2 0Data
樣例說明
輸入第一行，分別設定了 DHCP 的相關引數，并收到了 16 個報文，
第 1 個報文和第 2 個報文是客戶端 a 正常請求地址，服務器為其分配了地址 1，相應地設定了過期時刻是 7（即當前時刻 2 加上默認過期時間 5），
第 3 個報文不符合 Discover 報文的要求，不做任何處理，
第 4 個報文 b 發送的 Discover 報文雖然有 IP 地址 3，但是按照處理規則，這個欄位被忽略，因此服務器回傳 Offer 報文，過期時刻是 9，
第 5 個報文中，Request 報文不符合接收主機是 DHCP 服務器本機的要求，因此不做任何處理，
第 6 個報文是 b 發送的 Request 報文，其中設定了過期時刻是 12，沒有超過最長過期時間，因此回傳的 Ack 報文中過期時刻也是 12，
第 7 個報文中，過期時刻 11 小于最短過期時間，因此回傳的過期時刻是 12，雖然此時為 a 分配的地址 1 過期，但是由于還有狀態為未分配的地址 3，因此為 c 分配地址 3，第 8 個報文同理，為 c 分配的地址過期時刻是 13，
第 9、10 兩個報文中，為 d 分配了地址 4，過期時刻是 20，
第 11 個報文中，a 請求重新獲取此前為其分配的地址 1，雖然為其分配的地址過期，但是由于尚未分配給其它客戶端，因此 DHCP 服務器可以直接為其重新分配該地址，并重新設定過期時刻為 20，
第 12 個報文中，c 請求延長其地址的過期時刻為 20，DHCP 正常向其回復 Ack 報文，
第 13、14 個報文中，e 試圖請求地址，此時地址池中已經沒有處于“未分配”狀態的地址了，但是有此前分配給 b 的地址 2 的狀態是“過期”，因此把該地址重新分配給 e，
第 15 個報文中，b 試圖重新獲取此前為其分配的地址 2，但是此時該地址已經被分配給 e，因此回傳 Nak 報文，
第 16 個報文中，b 試圖重新請求分配一個 IP 地址，但是此時地址池中已經沒有可用的地址了，因此忽略該請求，
樣例輸入
4 70 100 50 dhcp
6
5 a * OFR 2 100
10 b * DIS 0 70
15 b dhcp2 REQ 4 60
20 c * DIS 0 70
70 d * DIS 0 120
75 d dhcp REQ 1 125Data
樣例輸出
dhcp b OFR 1 70
dhcp c OFR 1 70
dhcp d OFR 1 120
dhcp d ACK 1 125Data
樣例說明
在本樣例中，DHCP 服務器一共收到了 6 個報文，處理情況如下：
第 1 個報文不是 DHCP 服務器需要處理的報文，因此不回復任何報文，
第 2 個報文中，b 請求分配 IP 地址，因此 DHCP 服務器將地址 1 分配給 b，此時，地址 1 進入待分配狀態，DHCP 服務器向 b 發送 Offer 報文，
第 3 個報文中，b 發送的 REQ 報文是發給非本服務器的，因此需要將地址池中所有擁有者是 b 的待分配狀態的地址修改為未分配，
第 4 個報文中，c 請求分配 IP 地址，由于地址 1 此時是未分配狀態，因此將該地址分配給它，向它發送 Offer 報文，地址 1 進入待分配狀態，
第 5、6 個報文中，d 請求分配 IP 地址，注意到在收到第 5 個報文時，已經是時刻 70，地址 1 的過期時刻已到，它的狀態已經被修改為了未分配，因此 DHCP 服務器仍然將地址 1 分配給 d，
評測用例規模與約定
對于 20% 的資料，有 N≤200，且 n≤N，且輸入僅含 Discover 報文，且 t<Tmin；
對于 50% 的資料，有 N≤200，且 n≤N，且 t<Tmin，且報文的接收主機或為本機，或為 *；
對于 70% 的資料，有 N≤1000，且 n≤N，且報文的接收主機或為本機，或為 *；
對于 100% 的資料，有 N≤10000，且 n≤10000，主機名的長度不超過 20，且 t,Tmin,Tdefault,Tmax≤109，輸入的報文格式符合題目要求，且數字不超過 109，
我滴解題思路~
這個題目乍得一看，簡直要自閉了，因為題目實在是太長了，所以這告訴我們一個問題：如果你對這個DHCP相關的知識有所了解，并且學習過它的作業框架，那么上面的都是廢話，因為我大部分的時間都花在理解它的運作邏輯上了，
如果，你并沒有看完這題的題目，并且也不想要看完，那么你不妨看看我的想法？
DHCP是一種服務器在不需要客戶參與進來，就能夠自動為客戶的設備分配IP地址的一種協議，這里簡化它，就講述本題的資訊，方便你來了解它，（事實上，它也沒有復雜多少），它是TCP/IP協議中的一種，
DHCP接受discover報文和request報文，能夠發送offer，ack，nak報文；
客戶端要獲得DHCP服務器自動分配的IP地址，首先要向所在的網段，發送discover報文的廣播（就是和自己處于同一個網之下的所有機子都能接收到你發的東西），但是這種情況下只有DHCP服務器才能對你發的discover報文進行回應，別的機子都會無視你，注意一定是廣播，對應本題就是discover型別的報文，且接受者為"*";
如果你發送的discover廣播有DHCP服務器接收到了，那么這些服務器就會進行地址分配作業，當然是每一臺服務器都會進行地址分配操作，本題只是其中一臺名字是H而已，
具體怎么分配地址呢？首先他會查找地址池中有沒有這樣的一個地址，它之前已經被這個請求者占用過，如果有，直接就把這個IP繼續給他用，如果沒有就去找一個沒有用過的未分配地址給它，找不到，再去找有沒有過期的地址給它就好，過期地址其實也是某種意義上沒人用了，可以給它，但是過期地址需要再找到新主人之前，一直等待它原來的主人，有沒可能回來找它，那么這樣一個IP又從新變成待分配，要等待它現在的主人的一聲令下就到主人身邊，
如果找不到，那就無法處理了，就不用管這條discover報文了，如果找到了，繼續往下~
找到這樣的IP，DHCP服務器就把找到的IP分裝成一個offer報文精準的回傳給請求客戶端（單播），即只發給客戶端一人，這個offer報文中發送者自然是本臺服務器的名字，接收者是請求客戶端，型別是offer，IP是分配到的待分配IP，然后規定一個過期時刻，沒錯這個過期時刻是根據之前discover報文中客戶希望的過期時刻計算來的一個合理的過期時刻，就是說這個offer報文發出去之后，這個IP就要等待客戶端的回復，在這個過期時間之內如果等到回復，那么就可以分配給客戶端，沒等到的話，又要變成待分配去等待新的discover發現，
你可能會疑惑為什么都已經分配到了IP，還要再讓客戶端確認一下干什么？直接給它不就好了，這是很天真的，事實上，為了加快給不同客戶分配IP的速度，不僅僅是有一臺DHCP服務器，所以別的DHCP服務器也有可能給同一個客戶端分配IP，所以就要比較不同的offer報文誰更快到達客戶端那里，先到先分配咯，
然后假設我們這臺機子發送的offer報文在過期時間內，接受到了客戶端的請求回應，那么就真正可以把地址分給他了，當然，這里面還有一些貓膩，原因是，發送的request必須是具體指明是哪一臺機子，如果是廣播的話，這樣的請求無效，只有指明是我們這一臺DHCP服務器才可以，不然有可能引發兩臺以上的服務器真正去分配不同的IP，那就不能達到，獲得唯一IP的目的了，
接收到針對我的request報文了，那就可以真正，發送同意的ack報文，那就分配成功了，至此就完成了IP分配，
但是，還要補充一個小點，request不一定要在接受到offer之后才能發起，如果你自己發起，針對某一服務器的request，也有可能獲得一個IP，但是前提是，你之前已經用過了，換言之就是這個IP你已經discover過了，這樣IP的占有者是你，你自然可以請求再一次獲得它，
我這樣講解還是很難理解的~但是，如果你把這個題目結合我說的搞懂，你基本就把這個作業的邏輯搞懂了，這個題目很有必要認真一做，沒有復雜的演算法，但是由計算機網路的知識，還是很不錯的，學會了一個協議，
滿分代碼如下
已經有詳細的注釋了！請認真理解，
#include <bits/stdc++.h>
using namespace std;
#define DEPTH 10001
enum StateCode {NaN, Wait, Have, Overtime}; //一種狀態碼，記錄IP的四種狀態
struct IP {
int InvalidTime=0; //該IP的過期時刻
int state=NaN; //IP狀態:4種狀態
string user=""; //占用者
};
int N, Tdef, Tmax, Tmin; string H; int n;
void UpdateIP(int t, IP* pool) { //更新IP池的狀態，實際對每一個IP現在t時刻狀態進行更新
for (int i=1; i<=N; i++) {
if (t>=pool[i].InvalidTime&&pool[i].state==Wait) //注意這里用大于等于，我第一次就在這里錯了，原因是有可能從超時時刻轉成等待狀態
{pool[i].user=""; pool[i].state=NaN; pool[i].InvalidTime=0; continue;}
if (t>=pool[i].InvalidTime&&pool[i].state==Have)
{pool[i].state=Overtime; pool[i].InvalidTime=0;}
}
}
void SendOFR(const string &sender, int ip, const IP* pool) { //服務器發送offer報文
cout<<H<<' '<<sender<<' '<<"OFR"<<' '<<ip<<' '<<pool[ip].InvalidTime<<endl;
}
void SendACK(const string &sender, int ip, const IP* pool) { //服務器發送ack報文
cout<<H<<' '<<sender<<' '<<"ACK"<<' '<<ip<<' '<<pool[ip].InvalidTime<<std::endl;
}
void SendNAK(const string &sender, int ip) { //服務器發送nak報文
cout<<H<<' '<<sender<<' '<<"NAK"<<' '<<ip<<' '<<0<<std::endl;
}
int AssignIP(const string &sender, const string &receiver,
const string &type, int Ip, int invalidtime, IP* pool) {
//注意到只有有效的discover報文請求才能引起服務器申請地址的操作
int ip=N;
pool[0].user=sender;
while (pool[ip].user!=sender) ip--;
if (ip!=0) return ip;
else {
for (ip=1; ip<=N; ip++)
if (pool[ip].state==NaN) return ip;
if (ip==N+1) {
for (ip=1; ip<=N; ip++)
if (pool[ip].state==Overtime) return ip;
}
return 0;
}
} //按照定義向地址池請求分配一個可能的地址，若不存在回傳0
//匯總整一個服務器運作的邏輯，將每一次接受報文作為引數傳入，進行一次DealFuc操作
void DealFuc(int t, const string &sender, const string &receiver,
const string &type, int Ip, int invalidtime, IP* pool)
{
if (type=="DIS") { //接收到dis報文
if (receiver=="*") { //僅為廣播下才算有效
int ip=AssignIP(sender, receiver, type, Ip, invalidtime, pool); //查找是否有地址可分配
if (ip!=0) { //存在可分配IP
//修改地址池中該地址的狀態資訊
pool[ip].state=Wait;
pool[ip].user=sender;
//修改該地址的過期時刻
int limtime=invalidtime;
if (limtime==0) pool[ip].InvalidTime=t+Tdef;
else {
if (Tmin+t<=limtime&&limtime<=t+Tmax)
pool[ip].InvalidTime=limtime;
else {
if (limtime<t+Tmin) pool[ip].InvalidTime=t+Tmin;
else pool[ip].InvalidTime=t+Tmax;
}
}
SendOFR(sender, ip, pool); //發送offer報文
} else return; //不存在可分配IP，不處理
} else return; //不是廣播型別的discover報文是不合理的報文
}
else if (type=="REQ") { //接收到request報文
if (receiver==H) { //如果該報文接收者正是本機
int ip=Ip;
if (1<=ip&&ip<=N) { //判斷IP是否在地址池的范圍內
if (pool[ip].user==sender) { //判斷請求的地址是否已經discover過或者租借過，只要有過就會在user留下名字
pool[ip].state=Have; //請求成功修改狀態為占有
//修改該IP的過期時刻
int limtime=invalidtime;
if (limtime==0) pool[ip].InvalidTime=t+Tdef;
else {
if (t+Tmin<=limtime&&limtime<=t+Tmax)
pool[ip].InvalidTime=limtime;
else {
if (limtime<t+Tmin) pool[ip].InvalidTime=t+Tmin;
else pool[ip].InvalidTime=t+Tmax;
}
}
SendACK(sender, ip, pool); //發送ack報文給客戶端，表示IP請求成功
}
else SendNAK(sender, ip); //否則表示該請求是針對本機的但是沒有discover過或租借過，是無效的，發送nak報文，表示請求失敗
}
else SendNAK(sender, ip); //請求不在地址池范圍，同樣是無效的請求
}
else {
if (receiver=="*") return; //如果是廣播的request是不明確的，不能果斷處理，要等待進一步觀察
//你請求的是別的服務器，不是我，那么之前為你準備的待占用IP全部下降到未分配狀態
for (int ip=1; ip<=N; ip++) {
if (pool[ip].user==sender&&pool[ip].state==Wait) {
pool[ip].user="";
pool[ip].state=NaN;
pool[ip].InvalidTime=0;
}
}
}
}
else return; //接收到的不是discover也不是request報文，那么不在處理業務范圍內，不處理
}
int main() {
cin>>N>>Tdef>>Tmax>>Tmin>>H>>n;
IP pool[N+1];
int ti; string sender, receiver, type; int address, invalidtime;
for (int i=0; i<n; i++) {
//接受報文資訊
cin>>ti>>sender>>receiver>>type>>address>>invalidtime;
//更新ti時刻的地址池
UpdateIP(ti, pool);
//處理報文
DealFuc(ti, sender, receiver, type, address, invalidtime, pool);
}
return 0;
}如果覺得寫的不錯可以關注一下~或者收藏我的這個專欄哦~
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/298334.html
標籤：其他
上一篇：HTTP 連接：三次握手、四次揮手！你真的了解嗎？全新講解，走出誤區！不再害怕面試官...
下一篇：K8S 基本概念和術語