首页 > 代码库 > UVA 10887 Concatenation of Languages 字符串hash

UVA 10887 Concatenation of Languages 字符串hash

题目链接:https://vjudge.net/problem/UVA-10887

题意:

  给你两个集合A,B,任意组合成新的集合C(去重)

  问你最后C集合大小

题解:

  暴力

  组成的新串hash起来

#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define pii pair<int,int>#define MP make_pairtypedef long long LL;typedef unsigned long long ULL;const long long INF = 1e18+1LL;const double pi = acos(-1.0);const int N = 2e3+10, M = 1e3+20,inf = 2e9;ULL mod = 10000019ULL;int n,m;char a[N][202],b[N][202];map<ULL , int > mp;int ans;int check(int i,int j) {    ULL now = 0;    ULL ps = 1;    for(int ii = 0; ii < strlen(a[i]); ++ii) {        now = now + ps * (a[i][ii]) ;        ps *= mod;    }    for(int ii = 0; ii < strlen(b[j]); ++ii) {        now = now + ps * (b[j][ii]) ;         ps *= mod;    }    if(mp[now]) return 1;    else {        ans++;        mp[now] = 1;        return 0;    }}int main() {    int T,cas = 1;    scanf("%d",&T);    while(T--) {       mp.clear();        char ch[30];        scanf("%d%d",&n,&m);        getchar();        for(int i = 1; i <= n; ++i)           gets(a[i]);        for(int i = 1; i <= m; ++i)           gets(b[i]);        ans = 0;        for(int i = 1; i <= n; ++i) {            for(int j = 1; j <= m; ++j) {                check(i,j);            }        }        printf("Case %d: %d\n",cas++,ans);    }    return 0;}

 

UVA 10887 Concatenation of Languages 字符串hash