指纹锁--牛客 只能说不难 但是有意思

作者： 作者的头像   偶尔也会翻身的咸鱼 ,  2022-07-26 21:50:28 ,  所有人可见 ,  阅读 137

2


1

指纹锁–牛客

传送门–>https://ac.nowcoder.com/acm/contest/19850/L

set大法 之构造结构体

#include<iostream>
#include<algorithm>
#include<set> 
using namespace std;
int n,k;
struct cmp{
    bool operator()(const int & x, const int & y)
    {
        if(abs(x-y)<=k)
        {
            return false;
        }
        return x<y;
    }
};
    int main()
    {
        scanf("%d%d",&n,&k);
        set<int,cmp> q;  //定义一个结构体 增加q  inset  的条件
        while(n--)
        {
            char str[6];
            int a;
            scanf("%s%d",str,&a);
            if(str[0]=='a')  q.insert(a);
            else if(str[0]=='d') q.erase(a);
            else if(str[0]=='q')
            {
                if((q.find(a))!=q.end())     puts("Yes");//值得考虑 为什么返回的迭代器不能是q.end()
                else puts("No");
            }
        }
        return 0;
    }

set大法 二:

#include<iostream>
#include<algorithm>
#include<set>

using namespace std;

int m, k;

int main()
{
    set<int> s;
    scanf("%d%d",&m,&k);
    while (m--)
    {
        char op[6];
        int x;
        scanf("%s%d",op,&x);
        if(*op == 'a')  //整个区间没有这个[x-k,x+k] 就插入
        {
            if(s.lower_bound(x - k) == s.upper_bound(x + k)) s.insert(x);
        }
        else if(*op == 'd') //注意s.erase 函数的用法 这里是妙用
        {
            if(s.size()) s.erase(s.lower_bound(x - k), s.upper_bound(x + k));
        }
        else
        {
            if(s.lower_bound(x - k) == s.upper_bound(x + k)) puts("No");
            else puts("Yes");
        }
    }

    return 0;
}

set大法 三:

#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
int m,k;
int x;
char s[10];
set<int>G;


bool ask(int x)//是否能找到x元素， [x-k,x+k]内的元素都被视为值为x 
{
    set<int>::iterator it =G.lower_bound(x-k);//找第一个大于等于x-k的元素 
    return it!=G.end()&&*it<=x+k;//找到了并且该元素小于等于x+k 
}
int main()
{
    scanf("%d%d",&m,&k);
    for(int i=0;i<m;++i)
    {
        scanf("%s%d",s,&x);
        if(s[0]=='a')//[x-k,x+k]内的元素都被视为值为x 
        {
            if(!ask(x)) G.insert(x);//没有找到[x-k,x+k]中的任何元素 
        }
        else if(s[0]=='d')//删除操作 
        {
            set<int>::iterator it =G.lower_bound(x-k);
            while(*it<=x+k&&it!=G.end())//it不能指向end 
            {
                set<int>::iterator temp=it;//临时的迭代器变量 
                ++it;
                G.erase(temp);//删除这个迭代器  
             } 
        }
        else
        {
            if(ask(x)) puts("Yes");
            else puts("No");
         } 
    }
    return 0;
}

1 评论

用户头像
syadream   2025-02-18 15:57 · 福建         踩      回复

这个题目使用Python过不了，python的set不能像c++一样配合自定义比较器，有大佬知道应该怎么做吗?
python只能过50%的数据:

import sys
from bisect import bisect_left, bisect_right

def main():
    input = sys.stdin.readline
    m, k = map(int, input().split())
    arr = []

    for _ in range(m):
        op, x = input().split()
        x = int(x)

        if op == "add":
            # 使用二分查找找到可能的范围
            left = bisect_left(arr, x - k)
            right = bisect_right(arr, x + k)

            # 如果范围内没有数，则可以添加
            if left == right:
                arr.insert(left, x)

        elif op == "del":
            # 使用二分查找找到需要删除的范围
            left = bisect_left(arr, x - k)
            right = bisect_right(arr, x + k)
            if left < right:
                del arr[left:right]

        else:  # query
            # 使用二分查找检查是否存在近似相等的数
            left = bisect_left(arr, x - k)
            right = bisect_right(arr, x + k)
            print("Yes" if left < right else "No")

if __name__ == "__main__":
    main()
1024
x