O(n+m)算法,AC了,题目是不是得想办法加强?

P2249 【深基13.例1】查找

huaji_huaji @ 2023-08-29 18:16:37

(超级juruo,有错轻喷)

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
inline void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
int n,m;
int a[1000001];
unordered_map<int,int>mp;
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++){
        int x=read();
        if(!mp[x])mp[x]=i;
    }
    while(m--){
        int x=read();
        write(mp[x]?mp[x]:-1);
        putchar(' ');
    }

    return 0;
}

by Max6700 @ 2023-08-29 18:21:13

@huaji_huaji %%%


by Nicrobot @ 2023-08-29 18:22:37

二分还是 O(m \log n) 的 卡不了吧


by w9095 @ 2023-08-29 18:23:31

卡不了,二分跑得更慢(


by ZhongYuLin @ 2023-08-29 18:32:19

用unoedered_map的话可以照着模数的倍数卡到O(n^2)。请见https://oi-wiki.org/lang/csl/unordered-container/


by JRzyh @ 2023-08-29 18:42:46

这是hash,只能卡模数


by huaji_huaji @ 2023-08-29 18:47:28

@ZhongYuLin 可是要是特定卡的话还有改hash的办法,似乎没有一个完全卡掉unordered_map的方法。。。而且就算不行也可以用map,虽然复杂度跟二分差不多,但是代码不知简单了多少。本题的本意是二分,可是这道题似乎不能卡掉这些方法。


by ZhongYuLin @ 2023-08-29 19:08:34

@huaji_huaji 是的,但是我觉得可以贴出来那句名言了“Do not use STL,go and learn……"


by huaji_huaji @ 2023-08-29 19:13:34

@ZhongYuLin 6,这句话好像用在这里非常合适。


|