测测你的路由器 - 题目

测测你的路由器排行榜

时间限制： 30 s
空间限制： 1048576 KB

题目描述

路由器是计算机网络中的重要器件。在分组交换网络中，路由器不断接收经过它的数据包，并根据其中的路由表进行转发。

路由表由若干个表项组成，每个表项包含 addr, len, nexthop 这三个属性。其中 addr 为一个 32 位的 IPv4 地址，形如 192.168.1.0，len 为一个 0 到 32 之间的整数，而 nexthop 也是一个 IPv4 地址。

路由表支持查询操作。具体来说，给定一个 32 位的 IPv4 地址，路由器可按照最长前缀匹配原则，在路由表中找到其对应的路由表项，并返回该表项的 nexthop 值。

在本题中，你需要实现路由表的查询。数据保证路由表中不存在两个 addr 和 len 分别完全相同的表项。

接口

你需要包含头文件 router.h。

void init(int n, int q, const RoutingTableEntry *a);

初始化。在程序启动时 init 会被调用一次，接下来 query 会被调用 q 次，随后程序将结束。
n 表示路由表项的数量，q 表示询问的数量，a 为一个长度为 n 的数组，表示各路由表项。
输入数据保证，所有路由表项已按照 addr 为第一关键字，len 为第二关键字升序排序。

其中 RoutingTableEntry 为路由表项的结构体，其定义如下：

typedef struct {
    unsigned addr;
    unsigned char len;
    char pad[3];  // Padding for memory alignment
    unsigned nexthop;
} __attribute__((packed)) RoutingTableEntry;

在此结构体中，addr 和 nexthop 以大端序（Big Endian）存储。

unsigned query(unsigned addr);

查询 addr 地址。若在路由表中能找到满足条件的表项，则返回其 nexthop 值，否则返回 0。

数据规模和约定

本题共有 4 个测试点，每个测试点 25 分。

对于每个测试点，只有当所有询问都回答正确时，才能得到该测试点的所有分数，否则得 0 分。

测试点编号	$n = $	$q = $	备注
1	$1$	$1$	测试程序初始化的时间
2	$827088$	$1$	测试路由表建立的时间
3	$827088$	$1000000$	测试路由表的查询时间
4	$827088$	$2000000$	测试路由表的查询时间

数据来源

路由表数据来自 archive.routeviews.org。

下载地址：archive.routeviews.org/oix-route-views/2019.09/oix-full-snapshot-2019-09-17-0600.bz2

查询数据为随机生成。

注意事项

你只需实现上述接口，无需也不应访问标准输入和标准输出。

语言

编译选项（详见 FAQ 页面）

关于接口中的数组初值说明（最后更新：2023年2月6日）

若题目要求实现函数接口，且该函数中存在仅用于输出的数组（如 void solve(int n, const int *in, int *out) 中的 out），那么除非另外说明，否则该数组在程序启动时的初值为 0。

关于标准输出的说明（最后更新：2018年10月23日）

标准输出将被重定向到内存中，所以你的内存使用量也包括了你的标准输出的大小（向上取整到 4KB 的倍数）。

如果你的程序要进行大量输出，请考虑这一点。

关于提交的说明

你提交的代码将会被公开，所有人都可见。如果这不是你所期望的，或者如果想要删除已提交的代码，请联系管理员。

你的代码

提交

Judge Duck Online | 评测鸭在线
Server Time: 2024-12-04 16:36:26 | Loaded in 0 ms | Server Status
个人娱乐项目，仅供学习交流使用 | 捐赠

测测你的路由器 排行榜