2020

2. 一个ip地址分发程序。分为两个步骤，申请 Request 和 释放 Release。申请时按照唯一的mac地址进行申请。

ip地址有256个，范围是192.168.0.0 - 192.168.0.255

  分配策略分为以下三种：

如果该mac是第一次申请，如果有未分配的ip，按照升序分配。如果该mac已经进行过申请，则优先分配给它之前它使用过的。如果不存在未分配的ip，则按升序查找目前已经释放的ip，如果依然没找到，则返回NA.

输入：一个数字T，代表几组操作。

           T行，每行格式为 REQUEST/RELEASE = MAC地址，

输出，其中REQUEST时需要输出分配的ip，release不需要输出。

 

样例：

4 REQUEST=AABBCCDDEEF1 RELEASE=AABBCCDDEEF1 REQUEST=AABBCCDDEEF2 REQUEST=AABBCCDDEEF1

输出：

192.168.0.0

192.168.0.1

192.168.0.0

解法：没啥算法。

#include <iostream> #include <string> #include <vector> #include <unordered_map> using namespace std; class MiniDhcpServer { public: string ip_head = "192.168.0."; int addr[256] = {0}; int cur_new = 0; unordered_map<string, int> mp; bool zero_left = true; string Request(const string& mac) { string res; if(mp.find(mac) != mp.end()) { if(addr[mp[mac]] == 2) { res = ip_head + to_string(mp[mac]); } else if(addr[mp[mac]] == 1) { int i=0; for(;i<256;i++){ if(addr[i] == 2){ res += ip_head + to_string(i); } } if(i == 256) { res = "NA"; } } } else { if(cur_new < 256 && addr[cur_new] == 0){ res = ip_head + to_string(cur_new); if(cur_new < 254 && addr[cur_new + 1] == 0) { cur_new++; } else { cur_new = 256; } } else { int i=0; for(;i<256;i++){ if(addr[i] == 2){ res += ip_head + to_string(i); } } if(i == 256) { res = "NA"; } } } return res; } void Release(const string &mac) { addr[mp[mac]] = 2; } }; int main() { int line; cin >> line; MiniDhcpServer dhcp; for (int loop = 0; loop < line; loop++) { string str; cin >> str; string opration = str.substr(0, str.find_first_of("=")); string mac = str.substr(str.find_first_of("=") + 1); if (opration == "REQUEST") { cout << dhcp.Request(mac) << endl; } else if (opration == "RELEASE") { dhcp.Release(mac); } } return 0; }

3. 有很多设备，设备之间通过有向链路相连，每个链路有不同的长度。

现在要给定一个起点设备，一个终点设备，请找出可以到达的最小路径长度。如果不存在此连通链路，输出-1.

输入：第一行为两个数 m,n 。m代表有多少条链路关系，n代表要查询几组路径长度。

           下面m行，每行三个数，为每两个设备之间的链接以及路径长度，即，起点，终点，长度。

           下面m+1 - m+n+1行为n条查询。

输出，按查询顺序输出最小路径长度。

样例：

输入：

4 2 100 101 5 101 102 1 100 102 2 104 103 3 100 102 100 103

输出：

2

-1

解题思路，深搜，记忆化，同路径标记防止回环。

#include <vector> #include <unordered_map> #include <iostream> #include <map> #include <limits> using namespace std; class Solution { public: unordered_map<int, vector<int>> mp; unordered_map<string, int> value; string GetConnName(int start, int end) { string s1 = to_string(start); string s2 = to_string(end); for(int i=0;i < (3 - s1.size()); i++){ s1 = "0" + s1; } for(int i=0;i < (3 - s2.size()); i++){ s2 = "0" + s2; } return s1 + s2; } int dfs(int start, int end, const vector<vector<int>> &connection, vector<int>& used, vector<int>& dp) { if(start == end){ used[end] = 1; return 0; } if(used[start] == 1){ return 0; } if(dp[start] != 0){ return dp[start]; } if(mp.find(start) == mp.end()) { return 0; } used[start] = 1; int cur_min = INT_MAX; for(auto t : mp[start]) { int cur = value[GetConnName(start, t)] + dfs(t, end, connection, used, dp); cur_min = cur_min > cur ? cur : cur_min; } used[start] = 0; return cur_min; } vector<int> GetBestRoute(const vector<vector<int>> &connection, const vector<vector<int>> &routes) { if(connection.empty()){ return vector<int>(routes.size(), -1); } vector<int> res; for(auto conn : connection) { mp[conn[0]].push_back(conn[1]); value[GetConnName(conn[0], conn[1])] = conn[2]; } for(auto route : routes) { vector<int> used(500, 0); vector<int> dp(500,0); int value_res = dfs(route[0], route[1], connection, used, dp); if(used[route[1]] == 1){ res.push_back(value_res); } else{ res.push_back(-1); } // vector<int>tmp(500, 0); // dp.assign(tmp.begin(), tmp.end()); // used.assign(tmp.begin(), tmp.end()); } return res; } }; int main() { int n, m; cin >> n >> m; int board1, board2, weight; vector<vector<int>> connections(n, vector<int>(3, 0)); for (int loop = 0; loop < n; loop++) { cin >> board1 >> board2 >> weight; connections[loop][0] = board1; connections[loop][1] = board2; connections[loop][2] = weight; } vector<vector<int>> routes(m, vector<int>(2, 0)); for (int loop = 0; loop < m; loop++) { cin >> board1 >> board2; routes[loop][0] = board1; routes[loop][1] = board2; } Solution solu; vector<int> res = solu.GetBestRoute(connections, routes); for (auto r : res) { cout << r << endl; } return 0; }