POJ 3865 - Database 字符串hash-白红宇

POJ 3865 - Database 字符串hash

阅读量：4204 次

发布时间：2019-05-26

本文共 1449 字，大约阅读时间需要 4 分钟。

【题意】

给一个字符串组成的矩阵，规模为n*m（n<=10000，m<=10），如果某两列中存在两行完全相同，则输出NO和两行行号和两列列号，否则输出YES

【题解】

因为m很小，所以对每一行枚举其中两个字符串，检查之前行中对应的两列里是否重复即可。但是如何判重。

一开始想的把字符串做成pair然后用map映射为行号，但是TLE。

后来想到用hash判重，可能是因为哈希函数不够好，还是TLE。。。

总之这道题卡了三个小时，一直TLE。

枚举每一列，对枚举到的那一列从小到大排序，然后找到相邻两个相等的，接着在相同行，不同列中寻找相等的字符串，如果存在表示找到解。复杂度是m^2*n*logn，处于可以接受的范围。

最后的方法在POJ上使用C++通过，但是G++却超时了。

曾经记得POJ有一道题是使用G++通过，C++超时，总之以后在POJ上超时了就两个编译器都试试。

在看别人的代码时，发现有人用了字符串hash读入：

typedef unsigned long long ULL;ULL hash(char *s) {    ULL res = 0;    for(int i = 0; s[i]; ++i) {        res *= 9837;//质数        res += s[i];    }    return res;}

这样做比较速度相当快，程序用时不到1s。

因为没有处理冲突，所以可以用这个方法水过去(笑)

代码：(没有用字符串hash)

////  main.cpp//  160929////  Created by 刘哲 on 17/4/6.//  Copyright © 2016年 my_code. All rights reserved.////#include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #define lowbit(x) (x&-x)using namespace std;#define eps 1e-9#define ALL(x) x.begin(),x.end()#define INS(x) inserter(x,x.begin())#define FOR(i,j,k) for(int i=j;i<=k;i++)#define MAXN 1005#define MAXM 40005#define INF 0x3fffffffusing namespace std;typedef long long LL;int i,j,k,n,m,x,T,ans,big,cas,num,len,nodenum,l;bool flag;char s[105],t[105];int pre;string y[10005][15];string ex;struct node{ string st; int i;} G[10005];bool cmp(node a,node b){ return a.st

你可能感兴趣的文章