QOJ.ac

QOJ

Límite de tiempo: 1 s Límite de memoria: 256 MB Puntuación total: 100

#10555. 国际大学生路由竞赛

Estadísticas

你可能知道 Bluegao 大学(前身为 Bluefly 大学)以网络技术闻名。有一天,他们的校长 Yuege 收到了一台特殊的路由器,以及一项关于路由表的任务。

在本题中,路由表是一个(可能很大的)表格,包含若干条目,每个条目代表一个子网。该路由器的功能有限,它只能处理两个下一跳(next-hop)和一个主路由表。如果主路由表中存在包含数据包目的地址的子网,数据包将被发送到下一跳 A。否则,它们将被发送到下一跳 B。

你可能知道,IPv4 使用 32 位(四字节)地址,这限制了地址空间为 $4294967296$ ($2^{32}$) 个地址。IPv4 地址可以用任何表示 32 位整数值的记法书写。为了方便人类阅读,它们通常以点分十进制记法书写,即由四个八位组组成,每个八位组用十进制表示并用点分隔。但它们的二进制记法也非常有用。例如,IP 地址 $128.2.142.23$ 可以用点分二进制记法表示为 $10000000.00000010.10001110.00010111$。

子网是一块具有完全相同二进制前缀的相邻 IP 地址块,通常写为该地址空间中的第一个 IP 地址加上前缀的位长度,例如 “202.120.224.0/24”。如果一个 IP 地址在某个子网的范围内,我们就说该子网包含这个 IP 地址。

Yuege 的任务是反转他路由器的行为,使所有当前路由到下一跳 A 的数据包路由到下一跳 B,反之亦然。同时,为了性能考虑,他希望保持主路由表的大小尽可能小。

简而言之,对于给定的路由表(即一堆子网),我们需要得到它的“补集”,即计算出一组最小的子网,这些子网与给定的子网没有交集,且它们的并集必须是整个 IPv4 地址空间。

记住,Bluegao 大学以网络技术闻名,作为 Bluegao 大学的校长,Yuege 当然知道如何解决这个问题,但他太懒了,不想写代码,所以他向你寻求帮助。

输入格式

输入的第一行给出了测试用例的数量 $T$。接下来是 $T$ 个测试用例。

对于每个测试用例,第一行包含一个整数 $n$ ($0 \le n \le 30000$),表示子网的数量。接下来的 $n$ 行,每行包含一个格式为 $a.b.c.d/l$ 的子网,其中 $a, b, c, d, l$ 均为整数,$0 \le a, b, c, d < 256$,$0 \le l \le 32$。

注意,即使 $l = 32$,也不能省略 “/32” 部分。如果 $l = 0$,则 IP 地址部分必须为 “0.0.0.0”。

输出格式

对于每个测试用例,首先输出一行 “Case #x:”,其中 $x$ 是测试用例编号(从 1 开始)。然后在第二行打印一个整数 $n$,表示你答案中子网的数量。接下来的 $n$ 行,每行包含一个与输入格式相同的子网。你可以以任何顺序输出它们。

样例

样例输入 1

3
0
1
0.0.0.0/1
1
128.0.0.0/1

样例输出 1

Case #1:
1
0.0.0.0/0
Case #2:
1
128.0.0.0/1
Case #3:
1
0.0.0.0/1

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.