#P3297. 第3题-VIP用户优先转发
          
                        
                                    
                      
        
              - 
          
          
                      1000ms
            
          
                      Tried: 232
            Accepted: 54
            Difficulty: 7
            
          
          
          
                       所属公司 : 
                              华为
                                
            
                        
              时间 :2025年6月18日-暑期实习(留学生)
                              
                      
          
 
- 
                        算法标签>字符串          
 
第3题-VIP用户优先转发
题面描述
随着园区网络的高速发展,大带宽、大流量成了主旋律,但是当网络带宽超过设备的处理能力时,可能导致网络拥塞,挤占一些高优先级的业务(如VIP用户流量),影响用户体验,所以对网络的用户体验优化成了园区网络的核心技术之一。
现有需求:希望提升VIP用户的流量优先级,在网络拥时优先调度。用户的唯一身份标识是其MAC地址(例如:00-d8-01-ef-31-3e),因此需要在网络中配置所有VIP用户的MAC地址白名单,以便网络芯片转发引擎在执行流量转发时优先转发对应MAC地址的报文。
网络系统中VIP用户MAC地址配置格式为 xx-xx-xx-xx-xx-xx/M,其中标识MAC地址和掩码长度。MAC地址由48 bit,共6字节组成,通常表示为6个十六进制数,格式为 xx-xx-xx-xx-xx-xx。例如:00-d8-61-ef-31-3e 就是一个MAC地址。掩码长度表示在进行MAC地址匹配时关注的 bit 位数,如掩码长度 40 转换成MAC地址掩码为 ff-ff-ff-ff-f0-00(高40位关注,低8位不关注);配置 00-e0-fc-01-01-01/32,其对应的MAC地址掩码为 ff-ff-ff-ff-00-00(高32位关注,低16位不关注),能匹配的VIPMAC地址范围是 00-e0-fc-01-00-00 到 00-e0-fc-01-ff-ff。
思路
- 
问题本质
- 这道题的本质是“前缀匹配”:给定若干个48 位长度的地址前缀(带掩码长度M),然后对于每个查询地址,判断其前M位是否与某个前缀相同。
 - 这与 IP 前缀匹配类似,但这里是MAC地址,共48位,掩码长度范围0到48。当掩码长度为0时表示不关心任何位,即可以匹配任意地址;掩码长度为48时表示完全精确匹配。
 
 - 
数据表示
- 将每个MAC地址转换为一个48 位的整数(可以用64位整数类型存储)。例如:字符串 
"00-d8-61-ef-31-3e"→ 每个十六进制字节转换后依次左移拼成一个48 位整数。 - 对于一个带掩码长度M的前缀 
addr/M,构造其掩码:高M位为1,低48−M 位为 0。或者我们更方便的方式:我们只需要把地址右移(48−M) 位,保留高M 位,称为“前缀值”。匹配时也将查询地址右移相同的(48−M) 位,如果结果相等则匹配。 - 例如:掩码长度M=32,
00-e0-fc-01-01-01转整数后右移48−32=16 位,得到高 32 位前缀。查询地址同样右移16位再比较。 
 - 将每个MAC地址转换为一个48 位的整数(可以用64位整数类型存储)。例如:字符串 
 - 
多前缀匹配加速
- 
n最多可达100000,m可能也很大,暴力对每个查询遍历所有前缀显然不可行。
 - 
观察到掩码长度M的取值范围是0到48,最多49种可能。我们可以针对每个可能的掩码长度L,维护一个哈希集合(如 C++ 的
unordered_set<uint64_t>,Python 的set,Java 的HashSet<Long>),存储所有白名单前缀右移后的值。 - 
具体:
- 读到一个前缀 
addr/M,将addr_int右移(48−M) 位得到prefix_value,插入到对应掩码长度集合集合S[M]中。 - 查询时,对于当前查询地址 
q_int,对每个存在白名单的掩码长度L(即S[L] 非空),计算q_int >> (48 - L),然后检查该值是否在S[L] 中。如果存在,则该查询答案为YES,否则继续检查下一个掩码长度;若都不匹配,则为NO。 
 - 读到一个前缀 
 - 
因为掩码长度可能的值只有49种,查询时最多做49次哈希查找,时间是O(∣distinct masks∣),通常远小于n,满足性能需求。
 
 - 
 - 
边界情况
- 掩码长度M=0:任何地址右移48 位(即 
>>48)得到0,如果存在一个M=0的前缀,则所有查询地址都匹配,答案始终YES。 - 掩码长度M=48:需要精确匹配,右移(48−48)=0 位即不变,直接把完整48 位整数存入集合,在查询时直接检查完整整数是否在集合中。
 - 合法性:输入保证 MAC 字符串合法格式。注意要忽略大小写差异,可统一转换为小写或大写再解析。
 - 空白和分隔:输入中 MAC 字节用 
-分隔,掩码用/紧跟在地址后。读取时按字符串解析即可。 
 - 掩码长度M=0:任何地址右移48 位(即 
 - 
时间空间复杂度
- 空间:需要存储n个前缀值在对应集合中,总数不超过n,所以O(n) 空间。
 - 构造:逐条插入哈希表,平均O(1),总O(n).
 - 查询:每条查询最多对d个不同掩码长度做哈希查找,d≤49,所以每条O(49) 平均。总共O(m×49)。当m很大时也足够快。
 - 解析 MAC 为整数时间 O(1),常数开销。
 
 
C++
#include <bits/stdc++.h>
using namespace std;
// 将 MAC 地址字符串解析为 48 位整数
// 格式假定为 "xx-xx-xx-xx-xx-xx",xx 为十六进制表示的字节
uint64_t parse_mac_to_int(const string &mac_str) {
    uint64_t mac = 0;
    int len = mac_str.size();
    // 逐段解析,中间以 '-' 分隔
    // 简单方式:按 '-' 分割
    uint64_t byte = 0;
    int parts = 0;
    size_t start = 0;
    for (int i = 0; i <= len; ++i) {
        if (i == len || mac_str[i] == '-') {
            // mac_str[start..i-1] 是两位十六进制
            string part = mac_str.substr(start, i - start);
            // 转为整数
            byte = std::stoul(part, nullptr, 16);
            mac = (mac << 8) | (byte & 0xFF);
            parts++;
            start = i + 1;
            if (parts == 6) break;
        }
    }
    return mac;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    // 数组下标 0..48,每个位置存储该掩码长度对应的前缀集合
    vector<unordered_set<uint64_t>> prefix_sets(49);
    bool has_zero_mask = false;
    string line;
    for (int i = 0; i < n; ++i) {
        cin >> line;  // 例如 "00-d8-61-ef-31-3e/48"
        // 按 '/' 分割
        size_t pos = line.find('/');
        string mac_part = line.substr(0, pos);
        int mask_len = stoi(line.substr(pos + 1));
        // 解析 MAC 为整数
        uint64_t mac_int = parse_mac_to_int(mac_part);
        if (mask_len == 0) {
            // 掩码长度为 0,匹配任意地址
            has_zero_mask = true;
            // 仍可在 prefix_sets[0] 中插入任意值,如 0
            prefix_sets[0].insert(0ULL);
        } else {
            // 右移以保留高 mask_len 位
            int shift = 48 - mask_len;
            uint64_t prefix = (mac_int >> shift);
            prefix_sets[mask_len].insert(prefix);
        }
    }
    int m;
    cin >> m;
    string query_mac;
    for (int qi = 0; qi < m; ++qi) {
        cin >> query_mac;  // "xx-xx-xx-xx-xx-xx"
        uint64_t q_int = parse_mac_to_int(query_mac);
        bool matched = false;
        // 如果存在掩码长度 0,则总匹配
        if (has_zero_mask) {
            matched = true;
        } else {
            // 遍历所有可能的掩码长度
            for (int L = 1; L <= 48; ++L) {
                if (prefix_sets[L].empty()) continue;
                int shift = 48 - L;
                uint64_t q_prefix = (q_int >> shift);
                if (prefix_sets[L].count(q_prefix)) {
                    matched = true;
                    break;
                }
            }
        }
        if (matched) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}
Python
import sys
def parse_mac_to_int(mac_str: str) -> int:
    # mac_str 形如 "xx-xx-xx-xx-xx-xx"
    parts = mac_str.split('-')
    mac_int = 0
    for part in parts:
        mac_int = (mac_int << 8) | int(part, 16)
    return mac_int
def main():
    data = sys.stdin
    # 读取 n
    line = data.readline().strip()
    if not line:
        return
    n = int(line)
    # prefix_sets[L] 存储掩码长度为 L 的前缀集合
    prefix_sets = [set() for _ in range(49)]
    has_zero_mask = False
    for _ in range(n):
        line = data.readline().strip()
        # 可能有空行,要跳过
        if not line:
            continue
        mac_part, mask_part = line.split('/')
        mask_len = int(mask_part)
        mac_int = parse_mac_to_int(mac_part)
        if mask_len == 0:
            has_zero_mask = True
            prefix_sets[0].add(0)
        else:
            shift = 48 - mask_len
            prefix = mac_int >> shift
            prefix_sets[mask_len].add(prefix)
    # 读取 m
    line = data.readline().strip()
    m = int(line)
    for _ in range(m):
        qline = data.readline().strip()
        if not qline:
            continue
        q_int = parse_mac_to_int(qline)
        matched = False
        if has_zero_mask:
            matched = True
        else:
            # 遍历所有掩码长度
            for L in range(1, 49):
                if not prefix_sets[L]:
                    continue
                shift = 48 - L
                q_prefix = q_int >> shift
                if q_prefix in prefix_sets[L]:
                    matched = True
                    break
        print("YES" if matched else "NO")
if __name__ == "__main__":
    main()
Java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
public class VipMacMatcher {
    // 将 MAC 地址解析为 48 位整数,结果存储在 long 类型中
    // 格式假定 "xx-xx-xx-xx-xx-xx"
    private static long parseMacToLong(String macStr) {
        String[] parts = macStr.split("-");
        long mac = 0;
        for (String part : parts) {
            // Long.parseLong 可解析十六进制,需要指定基数 16
            long byteVal = Long.parseLong(part, 16);
            mac = (mac << 8) | (byteVal & 0xFF);
        }
        return mac;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String line = reader.readLine();
        if (line == null || line.isEmpty()) {
            return;
        }
        int n = Integer.parseInt(line.trim());
        // prefixSets[L] 存放掩码长度为 L 的前缀集合
        @SuppressWarnings("unchecked")
        Set<Long>[] prefixSets = new HashSet[49];
        for (int i = 0; i <= 48; i++) {
            prefixSets[i] = new HashSet<>();
        }
        boolean hasZeroMask = false;
        for (int i = 0; i < n; i++) {
            line = reader.readLine().trim();
            if (line.isEmpty()) {
                i--;
                continue;
            }
            String[] parts = line.split("/");
            String macPart = parts[0];
            int maskLen = Integer.parseInt(parts[1]);
            long macInt = parseMacToLong(macPart);
            if (maskLen == 0) {
                hasZeroMask = true;
                prefixSets[0].add(0L);
            } else {
                int shift = 48 - maskLen;
                long prefix = macInt >>> shift;
                prefixSets[maskLen].add(prefix);
            }
        }
        line = reader.readLine().trim();
        int m = Integer.parseInt(line);
        for (int i = 0; i < m; i++) {
            line = reader.readLine().trim();
            if (line.isEmpty()) {
                i--;
                continue;
            }
            long qInt = parseMacToLong(line);
            boolean matched = false;
            if (hasZeroMask) {
                matched = true;
            } else {
                for (int L = 1; L <= 48; L++) {
                    if (prefixSets[L].isEmpty()) {
                        continue;
                    }
                    int shift = 48 - L;
                    long qPrefix = qInt >>> shift;
                    if (prefixSets[L].contains(qPrefix)) {
                        matched = true;
                        break;
                    }
                }
            }
            System.out.println(matched ? "YES" : "NO");
        }
    }
}
        题目内容
随着园区网络的高速发展,大带宽、大流量成了主旋律,但是当网络带宽超过设备的处理能力时,可能导致网络拥塞,挤占一些高优先级的业务(如VIP用户流量),影响用户体验,所以对网络的用户体验优化成了园区网络的核心技术之一
在你接到一个用户需求,希望提升VIP用户的流量优先级,在网络拥时优先调度。其中用户的唯一身份标识是其MAC地址(如:00−d8−01−ef−31−3e),所以我们需要在网络中配置所有VIP用户的MAC地址白名单,以便网络芯片转发引擎在执行流量转发时优先转发对应MAC地址的报文。
网络系统中VIP用户MAC地址配置格式为xx−xx−xx−xx−xx−xx/M,其中标识MAC地址和掩码长度
MAC地址由MAC地址48bit,共6字节组成,通常表示为6个十六进制数,格式为xx−xx−xx−xx−xx−xx。
如:00−d8−61−ef−31−3e就是一个MAC地址掩码长度表示在进行MAC地址匹配时关注的BIT位数,如:掩码长度40转换成MAC地址掩码为ff−ff−ff−ff−f−00相当于MAC地址最后8bit不关注如:配置00−e0−fc−01−01−01/32,其对应的MAC地址掩码为ff−ff−f−ff−00−00,能匹配上的VIP MAC地址范围是00−e0−fc−01−00−00~00−e0−fc−01−ff−ff
输入描述
输入第一行为整数 n(1≤n≤100000),代表需要配置为VIP的MAC地址及其掩码个数。
接下来n行是对应VIP用户MAC地址及其掩码长度,格式为xx−xx−xx−xx−xx−xx/M,其中M(0≤M≤48),MAC地址由数字和小写英文字母组成
然后是转发引擎待处理的报文MAC地址数目m(1≤m≤100)
接下来m行是转发引擎待处理的报文MAC地址,格式为xx−xx−xx−xx−xx−xx
输出描述
输出m个转发引擎待处理的报文MAC地址是否可以优先调度,是输出YES,不是则输出NO
样例1
输入
2
00-d8-61-ef-31-3e/48
00-e0-fc-00-ed-50/40
2
00-e0-fc-00-ed-66
00-d8-61-ef-31-3f
输出
YES
NO 
说明
00−e0−fc−00−ed−66在VIP MAC地址列表中可以匹配,因为00−e0−fc−00−ed−50/48表示匹配范围为00−e0−fc−00−ed−xx,其中xx不关注。
00−d8−61−ef−31−3f在VIP MAC地址列表中无法匹配
样例2
输入
1
00-d8-61-ef-31-3e/0
1
02-12-13-14-15-16
输出
YES