#2928. [GDKOI]交换机

[GDKOI]交换机

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

MoonMoon 正在准备计算机网络的开学考,复习到了有关交换机的知识。交换机具有令人惊奇的特性那就是 它的表是自动、动态和自治地建立的,即没有来自网络管理员或来自配置协议的任何干预。换句话说,交换 机是自学习的。这种能力大概是通过如下方式实现的:

1)1) 交换机表初始为空。

2)2) 对于在每个接口接收到的每个数据帧,该交换机在其表中存储数据帧的源 MACMAC 地址。

3)3) 如果在一段时间 (称为老化期) 后,交换机没有接收到含有某个源 MACMAC 地址的数据帧,就会在表中删 除这个源 MACMAC 地址。

现在给出了某天中一个交换机所有收到的数据帧(每一个数据帧包含一个源 MACMAC 地址,以及该数据帧 的到达时间),请你帮助 MoonMoon 算出在这一天中,这个交换机的表最少需要多少项,才可以使得这天所有数据 帧的信息可以存储下来。注意为了简单起见,每个时间点先进行删除操作再进行插入操作注意为了简单起见,每个时间点先进行删除操作再进行插入操作

简单来说,需要维护一个字符串集合 SS,有若干次插入操作,每次插入操作包含一个字符串以及一个有 效时间区间(区间长度为定值),需要求出所有时间内,字符串集合 SS 大小的最大值。

输入格式

第一行两个整数 nkn,k,分别表示数据帧的个数,以及老化期时间(单位:分钟)。

接下来 nn 行,每行两个字符串 s1,s2s_1, s_2,表示数据帧包含的源地址帧,以及到达时间,其中 s1s_1 是一个 MACMAC 地址,包含 12121616 进制数,s2s_2 的格式为 a:ba : b,其中 0a230 ≤ a ≤ 23,0b590 ≤ b ≤ 59,表示该数据帧在 aabb 分钟 00 秒到达交换机,并且 a,ba, b 不足 1010 的数字前面要补充一个零。

输出格式

一行,一个整数,代表答案

输入样例1

4 10
0123456789ABCDEF 00:10
0000000000ABCDEF 08:11
0123456789ABCDEF 00:15
0000000000ABCDEF 00:11

输出样例1

2

输入样例2

3 60
0123456789ABCDEF 13:00
0000000000000000 14:00
0123456789ABCDEF 12:30

输出样例2

1

输入样例3

详见文件

输出样例3

详见文件

样例解释

样例 11 中,时刻 00:1100:11 分表项中有 22 个源 MACMAC 地址 0123456789ABC0123456789ABC0000000000ABCDEF0000000000ABCDEF,所以至 少需要表项大小至少为 22,可以证明这是最少需要的表项大小。

数据范围

对于所有的数据,有 1n105,1k14401 ≤ n ≤ 10^5,1 ≤ k ≤ 1440;

对于 50%50\% 的数据,有 1n5001 ≤ n ≤ 500

GDKOI普及组重现

未参加
状态
已结束
规则
IOI
题目
8
开始于
2023-4-6 21:00
结束于
2023-4-16 21:00
持续时间
240 小时
主持人
参赛人数
36