被Hash虐残了……深跪……
这题用一个next数组和一个head数组形成了一个类链表结构,确保组合形成的字符串不重复。
判断字符串是否相同用的是Hash算法,这是处理字符串的五大神器。。。屌炸天的感觉。。。
AC Memory : 0KB Time : 379MS
代码:
#include <cstdio> #include <cstring> #include <cstdlib> #define N 1000003 #define M 2250010 typedef unsigned long long ull; const ull B = 100000007ULL; int n , row , col,ff,m=0,sum; char str1[1510][12],str2[1510][12]; char str[M][22]; int head[N],next[N]; int gethash(char *p) { int c=strlen(p); int cnt=0; for(int i=0; i<c; i++) cnt = (cnt*26+p[i])%N; return cnt; } int main() { scanf("%d",&n); while(m<n) { sum=0; scanf("%d%d",&row,&col); getchar(); for(int i=0; i<row; i++) gets(str1[i]); for(int i=0; i<col; i++) gets(str2[i]); memset(head,-1,sizeof(head)); memset(next,-1,sizeof(next)); for(int i=0; i<row; i++) for(int j=0; j<col; j++) { strcpy(str[sum],str1[i]); strcat(str[sum],str2[j]); int cnt = gethash(str[sum]); int c=head[cnt]; ff=0; while(c!=-1) { if(strcmp(str[sum],str[c])==0) { ff=1; break; } c=next[c]; } if(!ff) { next[sum]=head[cnt]; head[cnt]=sum++; } } printf("Case %d: %d\n",m+1,sum); m++; } return 0; }