题面描述

随着园区网络的高速发展，大带宽、大流量成了主旋律，但是当网络带宽超过设备的处理能力时，可能导致网络拥塞，挤占一些高优先级的业务（如$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$位不关注），能匹配的$VIP MAC$地址范围是 00-e0-fc-01-00-00 到 00-e0-fc-01-ff-ff。

思路

1. 问题本质

   • 这道题的本质是“前缀匹配”：给定若干个$48$ 位长度的地址前缀（带掩码长度$M$），然后对于每个查询地址，判断其前$M$位是否与某个前缀相同。
   • 这与 IP 前缀匹配类似，但这里是$MAC$地址，共$48$位，掩码长度范围$0$到$48$。当掩码长度为$0$时表示不关心任何位，即可以匹配任意地址；掩码长度为$48$时表示完全精确匹配。

2. 数据表示

   • 将每个$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$位再比较。

3. 多前缀匹配加速

   • $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$，满足性能需求。

4. 边界情况

   • 掩码长度$M=0$：任何地址右移$48$ 位（即 >>48）得到$0$，如果存在一个$M=0$的前缀，则所有查询地址都匹配，答案始终 YES。
   • 掩码长度$M=48$：需要精确匹配，右移$(48-48)=0$ 位即不变，直接把完整$48$ 位整数存入集合，在查询时直接检查完整整数是否在集合中。
   • 合法性：输入保证 MAC 字符串合法格式。注意要忽略大小写差异，可统一转换为小写或大写再解析。
   • 空白和分隔：输入中 MAC 字节用 - 分隔，掩码用 / 紧跟在地址后。读取时按字符串解析即可。

5. 时间空间复杂度

   • 空间：需要存储$n$个前缀值在对应集合中，总数不超过$n$，所以$O(n)$ 空间。
   • 构造：逐条插入哈希表，平均$O(1)$，总$O(n)$.
   • 查询：每条查询最多对$d$个不同掩码长度做哈希查找，$d \le 49$，所以每条$O(49)$ 平均。总共$O(m \times 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