计蒜客 (寻找重复项)

原题连接:https://nanti.jisuanke.com/t/43120

蓝桥杯省赛模拟赛中的一道题

题意很简单,就是找运算式中第一个重复的位置

一开始没看仔细,直接开了个数组保存,后来发现只过了两组样例,才发现数据高达1e9,这样的话数组开不了这么大,又该用map来存储,结果map超时了!最后一组样例时间超限。

没办法,应该是要用hash了,但我不会hash。。。于是搁置了几天

今天在csdn上偶然看到该题的题解,发现大佬是用unordered_map做的。。。。

这个unordered_map和map用起来差不多。。。

只不过map内部是个红黑树来实现的,红黑树能自动排序,插入删除的效率高一点吧,查找效率为O(logn)

unordered_map内部是实现了哈希表,查找效率很高,常数级别的时间复杂度

不知道为啥在codeblocks上用unordered_map需要加#include <tr1/unordered_map>  和 using namespace std::tr1;

而在OJ上不需要。。。

代码:

#include <bits/stdc++.h>
#include <tr1/unordered_map>
using namespace std;
using namespace std::tr1;
unordered_map<long long,long long>mp;
int main()
{
    long long a,b,c;
    cin>>a>>b>>c;
    long long ans=1;
    mp[1]=1;
    int flag=0;
    for(int i=1;i<=2000000;i++)
    {
        ans=(ans*a+ans%b)%c;
        if(mp[ans]==0)
        {mp[ans]=1;}
        else
        {flag=1;
        cout<<i<<endl;
        break;}
    }
    if(flag==0)
    {cout<<"-1"<<endl;}
    return 0;
}

123

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注