发一个C++版本的实现。里面注释的部分是输出调试信息。主要是判断IP是否属于代码段的时候设计到大端小端的问题要注意以下。 然后就是代码中对删除操作的处理偷懒了，没有完全匹配删除规则的一致性（比如IP/MASK匹配偷懒了，还有操作是A还是R也没去匹配了)但是测试用例里面不涉及到这种不一致的问题，所以还是能AC。

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

struct addr {
    union {
        uint8_t u[4];
        uint32_t fu;
    };
};

struct rule {
    addr ip;
    int mask;
    char action;
    string goto_rules;

    rule(){};
    rule(addr _ip, int _mask, char _act, string _rule="") {
        ip=_ip; mask = _mask; action = _act; goto_rules = _rule;
    }

    bool match(struct addr sip) {
        // printf("mask %d %x %x\n", mask, ip.fu & 0xffffffff << (32-mask), sip.fu & 0xffffffff << (32-mask));
        if((ip.fu & (0xffffffff << (32-mask))) == (sip.fu & (0xffffffff << (32-mask)))) {
            return true;
        }
        return false;
    };
};

struct addr string_to_ipmask(string str, int &mask) {
    int i, pre = 0;
    uint8_t tmp;
    struct addr ans;
    int b = 3;
    for(i=0; i<(int)str.length(); ++i) {
        if(str[i] == '.') {
            tmp = strtol(str.substr(pre, i-pre).c_str(), NULL, 10);
            ans.u[b--] = tmp;
            pre = i+1;
        } else if(str[i] == '/') {
            tmp = strtol(str.substr(pre, i-pre).c_str(), NULL, 10);
            ans.u[b--] = tmp;
            pre = i+1;
            break;
        }
    }
    if(i == (int)str.length()) {    // 没有mask
        tmp = strtol(str.substr(pre, i-pre).c_str(), NULL, 10);
        ans.u[b--] = tmp;
        mask = 32;
    } else {    // 有mask
        // printf("## %s", str.substr(pre, str.length()-pre).c_str());
        mask = strtol(str.substr(pre, str.length()-pre).c_str(), NULL, 10);
    }
    // printf("%d.%d.%d.%d\n", ans.u[0], ans.u[1], ans.u[2], ans.u[3]);
    // printf("%x mask: %d\n", ans.fu, mask);
    return ans;
}

unordered_map<string, list<rule>> iptables;

int main() {
    int n;
    cin >> n;
    string action, name, addv, cidr;
    int mask;
    struct addr ip;
    for(int i=0; i<n; ++i) {
        cin >> action;
        // printf("rule %s\n", action.c_str());
        if(action == "A") {
            cin >> name;
            cin >> cidr;
            ip = string_to_ipmask(cidr, mask);
            cin >> action;
            if(action == "G") {
                cin >> addv;
                iptables[name].emplace_back(ip, mask, action[0], addv);
            } else {
                iptables[name].emplace_back(ip, mask, action[0]);
            }
        } else if(action == "I") {
            cin >> name;
            cin >> cidr;
            ip = string_to_ipmask(cidr, mask);
            cin >> action;
            if(action == "G") {
                cin >> addv;
                iptables[name].emplace_front(ip, mask, action[0], addv);
            } else {
                iptables[name].emplace_front(ip, mask, action[0]);
            }
        } else if(action == "M") {
            cin >> cidr;
            ip = string_to_ipmask(cidr, mask);
            
            string chain = "c0";
            
            bool fmatch = false;
reentry:
            for(rule &r : iptables[chain]) {
                if(r.match(ip)) {
                    if(r.action == 'G') {
                        chain = r.goto_rules;
                        goto reentry;
                    } else if(r.action == 'A' || r.action == 'R') {
                        printf("%c", r.action);
                        fmatch = true;
                        break;
                    }
                }
            }
            if(fmatch == false) {
                printf("U");
            }
        } else if(action == "D") {
            cin >> name;
            cin >> cidr;
            ip = string_to_ipmask(cidr, mask);
            cin >> action;
            if(action == "G")
                cin >> addv;
            for(auto it = iptables[name].begin(); it != iptables[name].end(); ++it) {
                if(it->match(ip)) {
                    iptables[name].erase(it);
                    break;
                }
            }
        }
    }
    return 0;
}

题面描述

本题是实现一个简化版的 iptables，用于管理 Linux 系统的网络访问控制。通过一系列操作命令，管理员可以定义规则链，并根据这些规则链对IP或CIDR地址进行访问控制。题目要求处理插入、追加、删除规则的操作，并对IP查询进行匹配，输出查询结果。

给定输入包括规则操作和查询命令，要求我们从一个默认规则链 c0 开始匹配 IP 地址，返回匹配的规则结果（Accept 或 Reject），或输出 Unknown 表示没有匹配的规则。

思路

题目核心是处理网络访问规则链，模拟 iptables 的规则匹配机制。主要涉及三种操作：插入、追加和删除规则，以及查询某个IP是否被允许访问。使用链表存储规则链，并且每次根据输入动态更新。

具体分析

1.数据结构设计：

使用一个字典 chains，键为链的名字，值为该链上的规则列表，每条规则由一个三元组 (action, net, mask) 表示： action: 表示该规则是 Accept 或 Reject。 net: IP 地址段的整数表示。 mask: 子网掩码长度。 另一个关键部分是处理 CIDR 地址段和具体 IPv4 地址的匹配，通过比特操作来判断某个IP是否在某个网段内。

2.IP和CIDR处理：

IP地址用整数表示，方便后续与子网掩码进行位运算。 CIDR格式的网段如 192.168.1.0/24 可以通过IP地址的前24位和网段掩码进行匹配。 具体实现中，将IP地址和掩码转换为整数，并通过与操作和位移实现匹配。

3.规则的插入、追加、删除：

插入：将规则插入到规则链的开头。 追加：将规则追加到规则链末尾。 删除：从链中找到对应规则并删除。

4.查询操作的实现：

从默认链 c0 开始查询，根据输入的IP逐条匹配链中的规则。 如果遇到 Goto 操作，跳转到指定的规则链继续匹配。 如果找到第一个匹配的规则，立即返回其结果（Accept 或 Reject）。如果所有规则都不匹配，则返回 Unknown。

DFS函数详解

查询IP是否被允许访问时，使用深度优先搜索（DFS）遍历规则链：

每次匹配时，从链 c0 开始，根据规则依次检查IP是否在某个CIDR网段内。 如果匹配到跳转规则（Goto），则递归进入新的规则链。 如果匹配到 Accept 或 Reject，立即返回结果，结束递归。 若没有规则匹配到，返回 Unknown

代码如下

python

from collections import defaultdict

# 将IPv4地址转换为32位整数
# 例如 '192.168.1.1' 会被转换为一个32位整数，以便后续处理
def ip_to_int(ip):
    parts = list(map(int, ip.split('.')))  # 将IP地址拆分为四个部分
    # 通过位运算将这四部分拼接为一个32位整数
    return (parts[0] << 24) | (parts[1] << 16) | (parts[2] << 8) | parts[3]

# 解析CIDR格式的网络地址，返回(网络地址整数, 掩码长度)
# 例如 '192.168.1.0/24' 会被转换为对应的网络地址和子网掩码长度
def parse_cidr(cidr):
    ip, mask = cidr.split('/')  # 将CIDR分为IP部分和掩码部分
    mask = int(mask)  # 掩码长度转换为整数
    ip_int = ip_to_int(ip)  # 将IP部分转换为32位整数
    # 通过位运算计算网络地址
    net = ip_int & (~((1 << (32 - mask)) - 1))
    return (net, mask)  # 返回网络地址和掩码长度

def main():
    N = int(input())  # 读取总的命令数量
    chains = defaultdict(list)  # 使用字典保存每个规则链，链名作为键，链上的规则列表作为值
    outputs = []  # 保存查询结果的输出列表
    
    # 处理每条规则操作命令或查询命令
    for _ in range(N):
        line = input().strip()  # 读取并去掉命令行中的多余空格
        tokens = line.split()  # 将命令按空格分割成若干部分
        op = tokens[0].upper()  # 操作类型（I: 插入，A: 追加，D: 删除，M: 查询）

        if op in {'I', 'A'}:  # 插入或追加规则
            chain_name, ip_or_cidr, action = tokens[1:4]  # 规则链名称，IP或CIDR，操作（A或R）
            
            if action == 'G':  # 如果规则是Goto（跳转到其他规则链）
                target_chain = tokens[4]  # 跳转的目标规则链
                # 处理CIDR或单个IP
                net, mask = parse_cidr(ip_or_cidr) if '/' in ip_or_cidr else (ip_to_int(ip_or_cidr), 32)
                rule = ('G', net, mask, target_chain)  # 构造Goto规则
            else:  # 普通的Accept或Reject规则
                net, mask = parse_cidr(ip_or_cidr) if '/' in ip_or_cidr else (ip_to_int(ip_or_cidr), 32)
                rule = (action, net, mask)  # 构造Accept或Reject规则
            
            if op == 'I':  # 插入规则到链的开头
                chains[chain_name].insert(0, rule)
            else:  # 追加规则到链的末尾
                chains[chain_name].append(rule)
        
        elif op == 'D':  # 删除规则
            chain_name, ip_or_cidr, action = tokens[1:4]  # 获取链名，IP或CIDR，操作（A或R）
            net, mask = parse_cidr(ip_or_cidr) if '/' in ip_or_cidr else (ip_to_int(ip_or_cidr), 32)
            # 删除规则链中与指定规则匹配的规则
            rules = chains[chain_name]
            chains[chain_name] = [r for r in rules if not (r[0] == action and r[1] == net and r[2] == mask)]
        
        elif op == 'M':  # 查询命令
            ip_str = tokens[1]  # 获取要查询的IP
            ip = ip_to_int(ip_str)  # 将IP转换为32位整数
            stack = ['c0']  # 从默认链 'c0' 开始查询
            result = 'U'  # 如果未找到匹配规则，结果默认设为 'U'（Unknown）
            visited_chains = set()  # 记录已经访问过的规则链，避免循环跳转
            
            # 深度优先搜索规则链
            while stack:
                current_chain = stack.pop()  # 取出当前要查询的规则链
                if current_chain in visited_chains:  # 如果该链已经访问过，跳过
                    continue
                visited_chains.add(current_chain)  # 标记该链为已访问
                rules = chains[current_chain]  # 获取当前规则链上的所有规则
                
                # 遍历该规则链上的所有规则
                for rule in rules:
                    # 检查当前IP是否符合该规则的网络地址范围
                    if rule[1] <= ip <= (rule[1] + ((1 << (32 - rule[2])) - 1)):
                        if rule[0] in ('A', 'R'):  # 如果是Accept或Reject规则
                            result = rule[0]  # 记录匹配的结果
                            stack = []  # 清空堆栈，结束查询
                            break
                        elif rule[0] == 'G':  # 如果是Goto规则
                            stack.append(rule[3])  # 将目标链名加入堆栈，继续查询
                            break
            outputs.append(result)  # 将查询结果加入输出列表
    
    print(''.join(outputs))  # 最后输出所有查询结果

if __name__ == "__main__":
    main()

cpp

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

// 将IPv4地址转换为32位整数
unsigned int ip_to_int(const string& ip) {
    unsigned int parts[4];
    sscanf(ip.c_str(), "%u.%u.%u.%u", &parts[0], &parts[1], &parts[2], &parts[3]);
    return (parts[0] << 24) | (parts[1] << 16) | (parts[2] << 8) | parts[3];
}

// 解析CIDR格式的网络地址，返回网络地址和掩码长度
pair<unsigned int, int> parse_cidr(const string& cidr) {
    size_t pos = cidr.find('/');
    string ip = cidr.substr(0, pos);
    int mask = stoi(cidr.substr(pos + 1));
    unsigned int ip_int = ip_to_int(ip);
    unsigned int net = ip_int & (~((1u << (32 - mask)) - 1));
    return {net, mask};
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N;
    cin >> N;
    // 定义规则结构
    struct Rule {
        char type; // 'A', 'R', 'G'
        unsigned int net;
        int mask;
        string target; // 仅G类型有
    };
    
    unordered_map<string, vector<Rule>> chains;
    string line;
    getline(cin, line); // 读取剩余的换行符

    string outputs = "";
    
    for(int i = 0; i < N; ++i){
        getline(cin, line);
        if(line.empty()) { i--; continue; }
        stringstream ss(line);
        string op;
        ss >> op;
        char operation = toupper(op[0]);
        
        if(operation == 'I' || operation == 'A'){
            string chain_name, ip_or_cidr, action;
            ss >> chain_name >> ip_or_cidr >> action;
            Rule rule;
            rule.type = action[0];
            if(ip_or_cidr.find('/') != string::npos){
                auto parsed = parse_cidr(ip_or_cidr);
                rule.net = parsed.first;
                rule.mask = parsed.second;
            }
            else{
                rule.net = ip_to_int(ip_or_cidr);
                rule.mask = 32;
            }
            if(rule.type == 'G'){
                string target_chain;
                ss >> target_chain;
                rule.target = target_chain;
            }
            if(operation == 'I'){
                chains[chain_name].insert(chains[chain_name].begin(), rule);
            }
            else{
                chains[chain_name].push_back(rule);
            }
        }
        else if(operation == 'D'){
            string chain_name, ip_or_cidr, action;
            ss >> chain_name >> ip_or_cidr >> action;
            unsigned int net;
            int mask;
            if(ip_or_cidr.find('/') != string::npos){
                auto parsed = parse_cidr(ip_or_cidr);
                net = parsed.first;
                mask = parsed.second;
            }
            else{
                net = ip_to_int(ip_or_cidr);
                mask = 32;
            }
            char act = action[0];
            auto &rules = chains[chain_name];
            rules.erase(
                remove_if(rules.begin(), rules.end(), [&](const Rule& r) {
                    if(r.type != act) return false;
                    if(r.net != net) return false;
                    if(r.mask != mask) return false;
                    return true;
                }),
                rules.end()
            );
        }
        else if(operation == 'M'){
            string ip_str;
            ss >> ip_str;
            unsigned int ip = ip_to_int(ip_str);
            stack<string> stk;
            stk.push("c0");
            char result = 'U';
            unordered_set<string> visited;
            
            while(!stk.empty()){
                string current_chain = stk.top(); stk.pop();
                if(visited.find(current_chain) != visited.end()) continue;
                visited.insert(current_chain);
                if(chains.find(current_chain) == chains.end()) continue;
                for(auto &rule : chains[current_chain]){
                    unsigned int start = rule.net;
                    unsigned int end = rule.net + ((1u << (32 - rule.mask)) - 1);
                    if(ip >= start && ip <= end){
                        if(rule.type == 'A' || rule.type == 'R'){
                            result = rule.type;
                            stk = stack<string>(); // 清空堆栈，结束查询
                            break;
                        }
                        else if(rule.type == 'G'){
                            stk.push(rule.target);
                            break;
                        }
                    }
                }
            }
            outputs += result;
        }
    }
    cout << outputs;
}

java

import java.util.*;
import java.io.*;

public class Main {
    // 将IPv4地址转换为32位整数
    static long ipToInt(String ip) {
        String[] parts = ip.split("\\.");
        long res = 0;
        for(String part : parts){
            res = (res << 8) | Long.parseLong(part);
        }
        return res;
    }

    // 解析CIDR格式的网络地址，返回网络地址和掩码长度
    static Pair<Long, Integer> parseCidr(String cidr) {
        String[] parts = cidr.split("/");
        String ip = parts[0];
        int mask = Integer.parseInt(parts[1]);
        long ipInt = ipToInt(ip);
        long net = ipInt & (~((1L << (32 - mask)) - 1));
        return new Pair<>(net, mask);
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        // 定义规则结构
        class Rule {
            char type; // 'A', 'R', 'G'
            long net;
            int mask;
            String target; // 仅G类型有

            Rule(char type, long net, int mask, String target){
                this.type = type;
                this.net = net;
                this.mask = mask;
                this.target = target;
            }
        }

        Map<String, List<Rule>> chains = new HashMap<>();
        StringBuilder outputs = new StringBuilder();
        
        for(int i = 0; i < N; ++i){
            String line = br.readLine();
            if(line == null || line.isEmpty()){
                i--;
                continue;
            }
            String[] tokens = line.trim().split("\\s+");
            char op = Character.toUpperCase(tokens[0].charAt(0));
            
            if(op == 'I' || op == 'A'){
                String chainName = tokens[1];
                String ipOrCidr = tokens[2];
                String action = tokens[3];
                char actionType = action.charAt(0);
                long net;
                int mask;
                if(ipOrCidr.contains("/")){
                    Pair<Long, Integer> parsed = parseCidr(ipOrCidr);
                    net = parsed.first;
                    mask = parsed.second;
                }
                else{
                    net = ipToInt(ipOrCidr);
                    mask = 32;
                }
                Rule rule;
                if(actionType == 'G'){
                    String targetChain = tokens[4];
                    rule = new Rule(actionType, net, mask, targetChain);
                }
                else{
                    rule = new Rule(actionType, net, mask, null);
                }
                chains.putIfAbsent(chainName, new ArrayList<>());
                if(op == 'I'){
                    chains.get(chainName).add(0, rule);
                }
                else{
                    chains.get(chainName).add(rule);
                }
            }
            else if(op == 'D'){
                String chainName = tokens[1];
                String ipOrCidr = tokens[2];
                String action = tokens[3];
                char act = action.charAt(0);
                long net;
                int mask;
                if(ipOrCidr.contains("/")){
                    Pair<Long, Integer> parsed = parseCidr(ipOrCidr);
                    net = parsed.first;
                    mask = parsed.second;
                }
                else{
                    net = ipToInt(ipOrCidr);
                    mask = 32;
                }
                if(chains.containsKey(chainName)){
                    List<Rule> rules = chains.get(chainName);
                    rules.removeIf(r -> r.type == act && r.net == net && r.mask == mask);
                }
            }
            else if(op == 'M'){
                String ipStr = tokens[1];
                long ip = ipToInt(ipStr);
                Stack<String> stack = new Stack<>();
                stack.push("c0");
                char result = 'U';
                Set<String> visited = new HashSet<>();
                
                while(!stack.isEmpty()){
                    String currentChain = stack.pop();
                    if(visited.contains(currentChain)) continue;
                    visited.add(currentChain);
                    if(!chains.containsKey(currentChain)) continue;
                    List<Rule> rules = chains.get(currentChain);
                    for(Rule rule : rules){
                        long start = rule.net;
                        long end = rule.net + ((1L << (32 - rule.mask)) - 1);
                        if(ip >= start && ip <= end){
                            if(rule.type == 'A' || rule.type == 'R'){
                                result = rule.type;
                                stack.clear();
                                break;
                            }
                            else if(rule.type == 'G'){
                                stack.push(rule.target);
                                break;
                            }
                        }
                    }
                }
                outputs.append(result);
            }
        }
        System.out.println(outputs.toString());
    }

    // 简单的Pair类
    static class Pair<F, S>{
        F first;
        S second;
        Pair(F first, S second){
            this.first = first;
            this.second = second;
        }
    }
}