UVA 10887 set或hash

题意：

给出n个A串和m个B串，将这A串与B串连接（B接在A后面）可以生成n*m个AB串，求不同的AB串的数量

分析：

set直接水过

#include <bits/stdc++.h>

using namespace std;

char str1[2000][15],str2[2000][15];

int main()

{

//    freopen("in.txt","r",stdin);

    int m,n,t,kase=0;

    scanf("%d",&t);

    set<string>M;

    while(t--)

    {

        scanf("%d%d",&n,&m);

        getchar();

        for(int i=0; i<n; i++)

            gets(str1[i]);

        for(int i=0; i<m; i++)

            gets(str2[i]);

        for(int i=0;i<n;i++)

        {

            for(int j=0;j<m;j++)

            {

                char tmps[30];

                strcpy(tmps,str1[i]);

                strcat(tmps,str2[j]);

                M.insert(tmps);

            }

        }

        printf("Case %d: %d\n",++kase,M.size());

        M.clear();

    }

    return 0;

}

hash可以节省时间

#include <bits/stdc++.h>

using namespace std;

const int maxn=2300000;

const int mod=2299963;

int a[maxn];

char vis[maxn][30];

char str1[2000][15],str2[2000][15];

int BKDRHash(char *str)

{

    int seed = 131; // 31 131 1313 13131 131313 etc..

    int res = 0;

    while (*str)

        res = res * seed + (*str++);

    return (res & 0x7FFFFFFF)%mod;

}

int APHash(char *str)

{

    int res = 0;

    int i;

    for (i=0; *str; i++)

    {

        if ((i & 1) == 0)

            res ^= ((res << 7) ^ (*str++) ^ (res >> 3));

        else

            res ^= (~((res << 11) ^ (*str++) ^ (res >> 5)));

    }

    return (res & 0x7FFFFFFF)%mod;

}

int Judge(char *str)    //两次hash

{

    int h1=BKDRHash(str);

    int h2=APHash(str);

    while(a[h1])

    {

        if(a[h1]==h2) return 0;

        h1++;

    }

    a[h1]=h2;

    return 1;

}

int Insert(char *str)

{

    int h=BKDRHash(str);

    while(a[h])

    {

        if(strcmp(vis[h],str)==0) return 0;

        h++;            //如果冲突往后移一位

    }

    a[h]=1;

    strcpy(vis[h],str);

    return 1;

}

int main()

{

//    freopen("in.txt","r",stdin);

    int m,n,t,kase=0;

    scanf("%d",&t);

    while(t--)

    {

        memset(a,0,sizeof(a));

        scanf("%d%d",&n,&m);

        getchar();

        for(int i=0; i<n; i++)

            gets(str1[i]);

        for(int i=0; i<m; i++)

            gets(str2[i]);

        int ans=0;

        for(int i=0;i<n;i++)

        {

            for(int j=0;j<m;j++)

            {

                char tmps[30];

                strcpy(tmps,str1[i]);

                strcat(tmps,str2[j]);

//                if(Judge(tmps)) ans++;

                if(Insert(tmps)) ans++;

            }

        }

        printf("Case %d: %d\n",++kase,ans);

    }

    return 0;

}

巴特西

UVA 10887 set或hash

最新文章

热门文章