题面描述

本题是实现一个简化版的 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;
        }
    }
}

题目内容

$iptables$是$Linux$系统的网络访问控制模块，管理员可通过$iptables$配置允许从哪些来源$IP$或$IP$段访问$6$个$tinux$主机。

$iptables$支持设置多个规则链，每个规则链中可以包含若干条访问控制规则。当系统收到一个网络报文时，会基于系统配置的访问控制规则来决定是接受还是拒绝这个报文。

请开发一个简化版$iptables$，现给定一系列规则操作命令和查询命令，

请依次输出其中查询命令的$IP$匹配结果。

规则操作命令有两种格式:

1. op chain_name ip_or_cidr action.op有三种:

$I$表示$Insert$，在对应的规则链开始处插入一条规则，

$A$表示$Append$，在对应的规则链结尾处追加一条规则,

$D$表示从chain_name对应的链中删除一条规则;

$action$字段$A$表示$Accept$，$R$表示$Reject$

2. op chain_name1 ip_or_cidr_G chain_name2.表示当匹配到此规则后跳转到chain_name2继续匹配，$G$表示$Goto$。

其中ip_or_cidr字段可以是单个$IPV4$地址，也可以是$CIDR$格式的$IPV4$地址段。

$CIDR$示例:10.1.0.0/24 表示10.1.0.0到10.1.0.25s这个IP段。

对于一个CDRa.b.c.d/a，如果一个IP地址的前n个bit与a.b.c.d的前n个bit相同，那么这个P属于a.b.c.d/这个IP段。

查询命令的格式: M ip 查询此$IP$是否被允许访问，$M$表示$Match$。输入用例保证一定有一条$c0$规则链，每一个$M$操作都从$c0$链开始依次对每一条规则进行匹配，

输出匹配到的第一条规则的$action$($A$或$R$)。如果没有匹配到任何规则，输出$U$(表示$Unknown$)。只支持通过$IP$查询，不支持$CIDR$格式。

输入描述

第一行:一个整数$N$($2<=N<=100000$)，表示总的规则操作命令和查询命令的总数。

接下来$N$行为规则操作命令或查询命令。

输出描述

对于每一个$M$操作，输出规则匹配后的$action$字段 ($A、R$或$U$)

样例1

输入

11
A c0 192.168.1.0/24 R
I c0 192.168.1.1 A
A c0 10.1.0.0/24 G c2
A c1 0.0.0.0/0 R
A c2 10.1.0.3 R
A c2 10.1.0.0/24 A
M 192.168.1.1
M 192.168.1.10
D c0 192.168.1.0/24 R
M 192.168.1.10
M 10.1.0.3

输出

ARUR

说明

一共11条配置或查询操作。 规则链$c0$中包含$3$条规则，$c1$中包含$1$条规则，$c2$中包含$2$条规则。 然后查询$192.168.1.1$，匹配到了$cO$链中的I c0192.168.1.1 A,输出$A$;

查询$192.168.1.10$，匹配到了$c0$中的$A\ c0\ 192.168.1.0/24\ R$，输出$R$;

接下来删除了$c0$中的$192.168.1.0/24\ R$规则，再查询$192.168.1.10$时已没有任何规则可匹配，输出$U$;

又查询$10.1.0.3$，先匹配到了$c0$中的第$3$条规则，发现要$goto\ c2$，于是匹配到了$c2$中的$10.1.0.3\ R$规则，输出$R$。

样例2

输入

2
A c0 192.168.1.0/24 R
M 192.168.1.20

输出

R

说明

一共$2$条配置或查询操作。

规则链$c0$中包含$1$条规则，拒绝来自$192.168.1.0/24$的IP。

$192.168.1.20$属于$192.168.1.0/24$ 这个$IP$段，因此输出$R$。