POJ 3865 - Database 字元串hash

【題意】

給一個字元串組成的矩陣，規模為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)

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<queue>
#include<string>
#include<sstream>
#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 0x3fffffff
using 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<b.st;
}

int main()
{
    scanf("%d%d",&n,&m);
    gets(s);
    for (i=1;i<=n;i++)//讀入
    {
        gets(s);
        len=strlen(s);
        s[len]=',';
        s[len+1]='\0';
        pre=0;
        num=0;
        for (j=0;j<=len;j++)
        {
            if (s[j]==',')
            {
                s[j]='\0';
                y[i][++num]=(s+pre);
                
                pre=j+1;
            }
        }
    } 
        
    for (i=1;i<=m;i++)//枚舉列
    {
        for (j=1;j<=n;j++)//把這一列複制一遍後排序
        {
            G[j].st=y[j][i];
            G[j].i=j;
        }
        sort(G+1,G+1+n,cmp);
        
        
        for (j=1;j<=n;j++)//枚舉行
        {
            for (k=j+1; k<=n && G[k].st==G[j].st ;k++)//向下找與第j行相同的行
            {
                for (l=i+1;l<=m;l++)//再枚舉其他列，檢查是否有重複
                {
                    if ( y[ G[j].i ][l]==y[ G[k].i ][l] )//存在重複
                    {
                        printf("NO\n");
                        printf("%d %d\n",G[j].i,G[k].i);
                        printf("%d %d\n",i,l);
                        return 0;
                    }
                }
            }
        }
    }
        
    printf("YES\n");
    return 0;
}      

轉載于:https://www.cnblogs.com/zhyfzy/p/4271664.html