特工身份识别系统

题意

情报机构给每个特工分配了 48 位二进制身份代号，用 6 个十六进制字节表示，格式为 xx-xx-xx-xx-xx-xx。

有 条授权规则，每条格式为 xx-xx-xx-xx-xx-xx/M，其中 是需要匹配的二进制前缀长度（）。 表示所有人都匹配， 表示完全匹配。

给 个特工代号，判断每个是否至少匹配一条规则，输出 YES 或 NO。

思路

这题的核心就是前缀匹配，不过匹配的单位是二进制位，而输入是十六进制。

怎么处理呢？把十六进制转成二进制位串就行了。每个十六进制字符对应 4 个二进制位，6 个字节一共 12 个十六进制字符，刚好 48 位。

对每条规则，把地址部分转成 48 位二进制串，记下前缀长度 。对每个查询，也转成 48 位二进制串，然后逐条规则检查：前 位是否一致。只要有一条匹配就输出 YES。

和 都不超过 1000，暴力 完全够用。

实现细节：

  • 解析十六进制时跳过 - 分隔符
  • 的规则直接匹配所有人，特殊处理即可
  • 用位串（数组或字符串）比较前 位，写法最直观

时间复杂度 ，空间 。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    vector<string> ruleBits(n);
    vector<int> ruleM(n);
    for(int i = 0; i < n; i++){
        char buf[64];
        scanf("%s", buf);
        string s(buf);
        int pos = s.find('/');
        ruleM[i] = stoi(s.substr(pos+1));
        string bits = "";
        for(int j = 0; j < pos; j++){
            char c = s[j];
            if(c == '-') continue;
            int val = (c >= '0' && c <= '9') ? c - '0' :
                      (c >= 'a' && c <= 'f') ? c - 'a' + 10 : c - 'A' + 10;
            for(int k = 3; k >= 0; k--)
                bits += ((val >> k) & 1) ? '1' : '0';
        }
        ruleBits[i] = bits;
    }
    int q;
    scanf("%d", &q);
    while(q--){
        char buf[64];
        scanf("%s", buf);
        string s(buf);
        string bits = "";
        for(char c : s){
            if(c == '-') continue;
            int val = (c >= '0' && c <= '9') ? c - '0' :
                      (c >= 'a' && c <= 'f') ? c - 'a' + 10 : c - 'A' + 10;
            for(int k = 3; k >= 0; k--)
                bits += ((val >> k) & 1) ? '1' : '0';
        }
        bool ok = false;
        for(int i = 0; i < n; i++){
            int m = ruleM[i];
            if(m == 0 || bits.substr(0, m) == ruleBits[i].substr(0, m)){
                ok = true; break;
            }
        }
        puts(ok ? "YES" : "NO");
    }
    return 0;
}

import java.util.*;

public class Main {
    static String toBits(String hex) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < hex.length(); i++) {
            char c = hex.charAt(i);
            if (c == '-') continue;
            int val = Character.digit(c, 16);
            for (int k = 3; k >= 0; k--)
                sb.append((val >> k) & 1);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine().trim());
        String[] ruleBits = new String[n];
        int[] ruleM = new int[n];
        for (int i = 0; i < n; i++) {
            String line = sc.nextLine().trim();
            int pos = line.indexOf('/');
            ruleM[i] = Integer.parseInt(line.substring(pos + 1));
            ruleBits[i] = toBits(line.substring(0, pos));
        }
        int q = Integer.parseInt(sc.nextLine().trim());
        StringBuilder out = new StringBuilder();
        for (int i = 0; i < q; i++) {
            String bits = toBits(sc.nextLine().trim());
            boolean ok = false;
            for (int j = 0; j < n; j++) {
                int m = ruleM[j];
                if (m == 0 || bits.substring(0, m).equals(ruleBits[j].substring(0, m))) {
                    ok = true; break;
                }
            }
            out.append(ok ? "YES" : "NO").append('\n');
        }
        System.out.print(out);
    }
}

import sys
input = sys.stdin.readline

def to_bits(hex_str):
    bits = []
    for c in hex_str:
        if c == '-':
            continue
        val = int(c, 16)
        for k in range(3, -1, -1):
            bits.append((val >> k) & 1)
    return bits

def main():
    n = int(input())
    rules = []
    for _ in range(n):
        line = input().strip()
        pos = line.index('/')
        m = int(line[pos+1:])
        bits = to_bits(line[:pos])
        rules.append((bits, m))
    q = int(input())
    out = []
    for _ in range(q):
        line = input().strip()
        bits = to_bits(line)
        ok = False
        for rbits, m in rules:
            if m == 0 or bits[:m] == rbits[:m]:
                ok = True
                break
        out.append("YES" if ok else "NO")
    print('\n'.join(out))

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', l => lines.push(l.trim()));
rl.on('close', () => {
    let idx = 0;
    function toBits(hex) {
        const bits = [];
        for (const c of hex) {
            if (c === '-') continue;
            const val = parseInt(c, 16);
            for (let k = 3; k >= 0; k--)
                bits.push((val >> k) & 1);
        }
        return bits;
    }
    const n = parseInt(lines[idx++]);
    const rules = [];
    for (let i = 0; i < n; i++) {
        const line = lines[idx++];
        const pos = line.indexOf('/');
        const m = parseInt(line.substring(pos + 1));
        const bits = toBits(line.substring(0, pos));
        rules.push([bits, m]);
    }
    const q = parseInt(lines[idx++]);
    const out = [];
    for (let i = 0; i < q; i++) {
        const bits = toBits(lines[idx++]);
        let ok = false;
        for (const [rbits, m] of rules) {
            if (m === 0) { ok = true; break; }
            let match = true;
            for (let j = 0; j < m; j++) {
                if (bits[j] !== rbits[j]) { match = false; break; }
            }
            if (match) { ok = true; break; }
        }
        out.push(ok ? "YES" : "NO");
    }
    console.log(out.join('\n'));
});