测测你的路由器 排行榜


时间限制: 30 s
空间限制: 2048 MB

题目描述

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

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

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

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

接口

你需要包含头文件 router.h

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

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

在此结构体中,addrnexthop大端序(Big Endian)存储。

unsigned query(unsigned addr);

数据规模和约定

本题共有 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

查询数据为随机生成。

注意事项

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


关于标准输出的说明(最后更新:2018年10月23日)

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

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




Judge Duck Online | 评测鸭在线
Server Time: 2019-10-17 01:01:06 | Loaded in 0 ms | Server Status
个人娱乐项目,仅供学习交流使用