韩爷的梦

Time Limit: 20 Sec Memory Limit: 256 MB

题目连接

http://acm.uestc.edu.cn/#/contest/show/61

Description

一天，韩爷去百度面试，面试官给了他这么一个问题。

给你2万个字符串，每个字符串长度都是100，然后把2万个字符串丢入一个 set< string >g 中，问最终set里含有多少个元素？

g 是一个用来存储字符串、具有去重功能的容器，即相同字符串在 g 中只能保留一个。

两个字符串相等，当且仅当，长度一样且对应位置的字符都一样。

韩爷前晚没睡好，随手写了一个程序交给面试官，然后就gg了。

#include
          
           #include
           
            #include
            
             using namespace std;string s;set
             
              g;int main(){    for(int k=1;k<=20000;k++){        cin>>s;        g.insert(s);    }    cout<
              
               <

韩爷醒来之后，发现这只是一个梦（还好只是个梦）。他回忆起梦中的面试官给他的内存限制和时间限制非常低，这么做肯定过不了，那么，现在你不在梦中，你能解决这个问题么？

Input

单case

每个case有且只有2万行，每一行包含一个字符串，每行字符串的长度都为100 （样例除外）

字符集：大写英文字母（A－Z），小写英文字母（a－z），数字（0－9）

Output

输出一个整数，表示最终set里含有多少个元素。

Sample Input

aaAa

bbbb

1234

bbbb

ee09

Sample Output

HINT

样例只是样例，不在test中

注意时间限制和内存限制非常低

题意

题解：

单hash一下就好

双hash也很稳

代码：

//qscqesze#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   typedef long long ll;using namespace std;//freopen("D.in","r",stdin);//freopen("D.out","w",stdout);#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)#define maxn 200001#define mod 812361263#define eps 1e-9int Num;char CH[20];//const int inf=0x7fffffff; //нчоч╢Сconst int inf=0x3f3f3f3f;/*inline void P(int x){ Num=0;if(!x){putchar('0');puts("");return;} while(x>0)CH[++Num]=x%10,x/=10; while(Num)putchar(CH[Num--]+48); puts("");}*/inline ll read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}inline void P(int x){ Num=0;if(!x){putchar('0');puts("");return;} while(x>0)CH[++Num]=x%10,x/=10; while(Num)putchar(CH[Num--]+48); puts("");}//**************************************************************************************char s[110];vector
                   
                     a;/*int ELFhash(char *key){ unsigned long h=0; unsigned long x=0; while(*key) { h=(h<<4)+(*key++); //h左移4位，当前字符ASCII存入h的低四位 if( (x=h & 0xF0000000L)!=0) { //如果最高位不为0，则说明字符多余7个，如果不处理，再加第九个字符时，第一个字符会被移出 //因此要有如下处理 h^=(x>>24); //清空28~31位 h&=~x; } } return h % mod;}*/int get_hash(char *key){ ll N=1998585857; long long h=0; while(*key) h=(h*127+(*key++)+N)%N; return h%N;}int main(){ for(int i=0;i<20000;i++) { scanf("%s",s); a.push_back(get_hash(s)); } sort(a.begin(),a.end()); a.erase(unique(a.begin(),a.end()),a.end()); printf("%d\n",a.size());}