首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。