题解 | #特工身份识别系统#

题目链接

题目描述

在一个情报机构中，特工的身份由一个 48 位的二进制代号表示，通常写作 6 个十六进制字节的形式（如 00-d8-61-ef-31-3e）。

授权体系基于前缀匹配规则，规则格式为 xx-xx-xx-xx-xx-xx/M，其中 $M$ 是一个介于 0 到 48 之间的安全等级。一条规则意味着，任何特工的身份代号，如果其前 $M$ 位与规则的基础代号的前 $M$ 位相同，则获得授权。

$M=48$ 表示完全匹配。
$M=0$ 表示匹配所有代号。

任务是开发一个系统，给定一组授权规则和一批待验证的特工身份代號，判断每个特工是否至少匹配一条授权规则。

解题思路

这道题的核心是实现对 48 位二进制数的前缀匹配。直接操作十六进制字符串进行比较会非常繁琐，因此，首要步骤是将字符串形式的代号转换为数值类型，以便利用高效的位运算进行比较。

数据转换：
- 一个 48 位的二进制数可以被一个 64 位的无符号长整型 (unsigned long long in C++, long in Java with care, int in Python)完美存储。
- 我们需要编写一个解析函数，将形如 xx-xx-xx-xx-xx-xx 的字符串转换为一个 64 位整数。这可以通过逐个解析由连字符 - 分隔的 6 个两位十六进制数，并通过位移运算将它们组合起来实现。例如，第一个字节左移 40 位，第二个字节左移 32 位，以此类推，最后一个字节不移位，然后将所有结果进行按位或运算。
前缀匹配逻辑：
- 假设我们有两个 48 位的数， $A$ （特工代号）和 $B$ （规则基础代号），以及一个前缀长度 $M$ 。要判断它们的前 $M$ 位是否相等，最简单的方法是同时将这两个数右移 $48 - M$ 位。
- 右移后，原来的前 $M$ 位被保留下来，成为了新的数的低 $M$ 位，而原始的后 $48-M$ 位则被移出。此时，只需比较 $A >> (48 - M)$ 和 $B >> (48 - M)$ 是否相等即可。
- 这个逻辑对边界情况也有效：
  - 当 $M=48$ 时，右移 0 位，相当于直接比较 $A$ 和 $B$ 的完整值。
  - 当 $M=0$ 时，右移 48 位，任何 48 位的数右移 48 位后都变为 0，因此比较结果总是 0 == 0，即为真，这符合“匹配所有”的规则。
整体算法：
- 读取所有 $N$ 条规则，将每条规则的十六进制部分解析为 64 位整数，与安全等级 $M$ 一起存储起来。
- 对于每个待验证的特工，同样将其代号解析为 64 位整数。
- 遍历所有存储的规则，使用上述位运算逻辑进行前缀匹配。
- 一旦找到任何一条匹配的规则，立即停止对当前特工的检查，输出 YES，然后处理下一个特工。
- 如果遍历完所有规则都未找到匹配项，则输出 NO。

鉴于 $N$ 和 $Q$ 的数据范围（最大为 1000），这种 $O(N \cdot Q)$ 的暴力匹配算法是完全可行的。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <string>
#include <utility>

using namespace std;

// 使用 unsigned long long 来存储 48 位代号
using ull = unsigned long long;

// 解析十六进制字符串到 ull
ull parse_id(const string& s) {
    ull res = 0;
    string current_hex;
    for (char c : s) {
        if (c == '-') continue;
        current_hex += c;
        if (current_hex.length() == 2) {
            res = (res << 8) + stoull(current_hex, nullptr, 16);
            current_hex = "";
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<pair<ull, int>> rules(n);
    for (int i = 0; i < n; ++i) {
        string rule_str;
        cin >> rule_str;
        size_t slash_pos = rule_str.find('/');
        string id_str = rule_str.substr(0, slash_pos);
        int m = stoi(rule_str.substr(slash_pos + 1));
        rules[i] = {parse_id(id_str), m};
    }

    int q;
    cin >> q;
    while (q--) {
        string agent_id_str;
        cin >> agent_id_str;
        ull agent_id = parse_id(agent_id_str);
        
        bool found = false;
        for (const auto& rule : rules) {
            ull rule_id = rule.first;
            int m = rule.second;
            
            if (m == 0) {
                found = true;
                break;
            }
            if ((agent_id >> (48 - m)) == (rule_id >> (48 - m))) {
                found = true;
                break;
            }
        }
        if (found) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }

    return 0;
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    private static long parseId(String s) {
        String clean_s = s.replace("-", "");
        return Long.parseUnsignedLong(clean_s, 16);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine(); 
        
        List<long[]> rules = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            String line = sc.nextLine();
            String[] parts = line.split("/");
            long id = parseId(parts[0]);
            int m = Integer.parseInt(parts[1]);
            rules.add(new long[]{id, m});
        }

        int q = sc.nextInt();
        sc.nextLine(); 
        
        for (int i = 0; i < q; i++) {
            String agentIdStr = sc.nextLine();
            long agentId = parseId(agentIdStr);
            
            boolean found = false;
            for (long[] rule : rules) {
                long ruleId = rule[0];
                long m = rule[1];
                
                if (m == 0) {
                    found = true;
                    break;
                }
                // 使用无符号右移 >>>
                if ((agentId >>> (48 - m)) == (ruleId >>> (48 - m))) {
                    found = true;
                    break;
                }
            }
            if (found) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }
}

def parse_id(s):
    return int(s.replace('-', ''), 16)

def main():
    n = int(input())
    rules = []
    for _ in range(n):
        rule_str = input()
        id_str, m_str = rule_str.split('/')
        rules.append((parse_id(id_str), int(m_str)))

    q = int(input())
    for _ in range(q):
        agent_id_str = input()
        agent_id = parse_id(agent_id_str)
        
        found = False
        for rule_id, m in rules:
            if m == 0:
                found = True
                break
            if (agent_id >> (48 - m)) == (rule_id >> (48 - m)):
                found = True
                break
        
        if found:
            print("YES")
        else:
            print("NO")

if __name__ == "__main__":
    main()

算法及复杂度

算法：暴力枚举 + 位运算
时间复杂度： $\mathcal{O}(N \cdot Q)$ - 对于 $Q$ 个查询，每个查询都需要遍历 $N$ 条规则。字符串解析和位运算的时间视为常数。
空间复杂度： $\mathcal{O}(N)$ - 主要用于存储 $N$ 条解析后的规则。