链接:https://ac.nowcoder.com/acm/contest/58236/D 来源:牛客网 HA实验有一套非常严密的安全保障体系,在HA实验基地的大门,有一个指纹锁。该指纹锁的加密算法会把一个指纹转化为一个不超过1e7的数字,两个指纹数值之差越小,就说明两个指纹越相似,当两个指纹的数值差≤k时,这两个指纹的持有者会被系统判定为同一个人。现在有3种操作,共m个, 操作1:add x,表示为指纹锁录入一个指纹,该指纹对应的数字为x,如果系统内有一个与x相差≤k的指纹,则系统会忽略这次添加操作 操作2:del x,表示删除指纹锁中的指纹x,若指纹锁中多个与x相差≤k的指纹,则全部删除,若指纹锁中没有指纹x,则可以忽略该操作, 操作3:query x,表示有一个持有指纹x的人试图打开指纹锁,你需要设计一个判断程序,返回该人是否可以打开指纹锁(只要x与存入的任何一个指纹相差≤k即可打开锁)。初始状态,指纹锁中没有任何指纹。
时间: 2023-10-07 15:13:21 浏览: 53
这道题可以使用哈希表来实现。
对于每个指纹,我们将其哈希到一个桶中,桶中存储的是所有与该指纹相差不超过 k 的指纹。具体来说,对于一个指纹 x,我们将其哈希到桶 h(x) 中,并将其加入桶中。同时,我们枚举所有与 x 相差不超过 k 的指纹 y,将 y 也加入桶 h(x) 中。
对于操作 1,我们只需要判断是否存在与 x 相差不超过 k 的指纹即可。
对于操作 2,我们需要将所有与 x 相差不超过 k 的指纹从桶 h(x) 中删除。
对于操作 3,我们只需要在桶 h(x) 中查找是否存在与 x 相差不超过 k 的指纹即可。
具体实现时,我们可以使用 vector 存储每个桶中的指纹,然后使用双指针扫描 vector,将与 x 相差不超过 k 的指纹加入桶中,时间复杂度为 O(n),其中 n 为指纹总数。查询和删除操作的时间复杂度也为 O(n)。
相关问题
https://ac.nowcoder.com/acm/contest/67743/L
很抱歉,我无法访问互联网上的链接。但是,我可以为您提供一些关于Nowcoder的一般信息。
Nowcoder是一个面向程序员的在线学习和竞赛平台,提供各种编程题目和算法竞赛。链接中的https://ac.nowcoder.com/acm/contest/67743/L可能是一个Nowcoder的竞赛链接,其中的"/acm/contest/67743/L"可能是竞赛的具体页面或题目链接。
如果您对Nowcoder平台或者竞赛有任何具体问题,我会尽力回答。请提出您的问题。
https://ac.nowcoder.com/acm/contest/61657/L
根据提供的引用内容,我无法回答你的问题。引用内容中包含了一些代码和链接,但没有提供具体的问题描述。请提供更详细的问题描述,我将尽力帮助你解答。
#### 引用[.reference_title]
- *1* *3* [2022/7/17/题解2022河南萌新联赛第(二)场:河南理工大学https://ac.nowcoder.com/acm/contest/37344](https://blog.csdn.net/m0_66433418/article/details/125835437)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^insert_down1,239^v3^insert_chatgpt"}} ] [.reference_item]
- *2* [牛客·金币https://ac.nowcoder.com/acm/contest/19305/1021](https://blog.csdn.net/m0_66433418/article/details/125787020)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^insert_down1,239^v3^insert_chatgpt"}} ] [.reference_item]
[ .reference_list ]