首页 > 代码库 > 单词分类
单词分类
1.单词分类
【问题描述】
chffy为了学好英语决定苦背单词，但很快他发现要直接记住杂乱无章的单词非常困难，他决定对单词进行分类。
两个单词可以分为一类当且仅当组成这两个单词的各个字母的数量均相等。
例如“AABAC” ，它和“CBAAA”就可以归为一类，而和“AAABB”就不是一类。
现在chffy有N个单词，所有单词均由大写字母组成，每个单词的长度不超过100 。你要告诉chffy 这些单词会被分成几类。
【输入格式】
输入文件的第一行为单词个数N ，以下N 行每行为一个单词。
【输出格式】
输出文件仅包含一个数，表示这N 个单词分成的类数。
【样例输入】
3
AABAC
CBAAA
AAABB
【样例输出】
2
【数据范围】
对于70％的数据满足N ≤ 100 。
对于100％的数据满足N ≤ 10000 。
【题目分析】
一开始的想法是排序，每个字符串内部排序，再把每个字符串排序，这样所有一样的字符串都放在一起了，但是....怎么实现呢..于是就放弃....
另一种想法，把字符转化为数字，相乘，mod一个较大的质数，乘积相同的大概就一样了吧....然后加了个特判，如果字符串长度都不一样，直接输出个数，这样40
后来Justpenz233把第一种方法实现了....
再后来，cjx用了一种飞快的方法：双哈希
//40分#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<cmath>using namespace std;const int mod1=10000007;const int mod2=12300001;int a[110];int sum1[10010],sum2[10010];char s[110];int n,len[110];int ans=0;int main(){ freopen("word.in","r",stdin); freopen("word.out","w",stdout); memset(sum1,1,sizeof sum1); memset(sum2,1,sizeof sum2); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%s",&s); len[i]=strlen(s); for(int j=1;j<=len[i];j++) a[j]=s[j-1]-‘A‘+1, sum1[i]=sum1[i]*a[j]%mod1, sum2[i]=sum2[i]*a[j]%mod2; } sort(sum1+1,sum1+1+n); sort(sum2+1,sum2+1+n); bool flag=0; for(int i=1;i<=n;i++) if(len[i]==len[i+1]) flag=1; if(flag==0) ans=n; else { for(int i=1;i<=n;i++) if(sum1[i]!=sum1[i-1]&&sum2[i]!=sum2[i-1]) ans++; } printf("%d",ans); fclose(stdin);fclose(stdout);}
//AC//原来sort可以这么干#include <cstdio>#include <string>#include <cstring>#include <iostream>#include <algorithm>using namespace std;string s[20000];int ans = 1;int n = 0;int main(){ freopen("word.in", "r", stdin); freopen("word.out", "w", stdout); cin >> n; for (int i = 1; i <= n; i ++) { cin >> s[i]; sort(s[i].begin(), s[i].end()); cout<<s[i]; } sort(s + 1, s + n + 1); for (int i = 2; i <= n; i ++) if (s[i] != s[i - 1]) ans++; cout << ans;}
#include<cstdio>#include<cstring>#define INF1 1000007#define INF2 10003struct Node{ int T1,T2;}i[10001];int n,Num(0),Prime[26];void Euler() //欧拉筛法。{ int Num(0); bool f[102]={0}; for (int a=2;a<102;a++) { if (!f[a]) Prime[Num++]=a; for (int b=0;b<Num&&a*Prime[b]<102;b++) { f[a*Prime[b]]=true; if (!(a%Prime[b])) break; } }}int main() //一言不合双Hash。{ freopen("word.in","r",stdin); freopen("word.out","w",stdout); Euler(); scanf("%d",&n); getchar(); for (int a=0;a<n;a++) { char S[101]; bool T(0); gets(S); int Sum1=1,Sum2=1,Length=strlen(S); for (int a=0;a<Length;a++) Sum1=(Sum1*Prime[S[a]-‘A‘])%INF1; for (int a=0;a<Length;a++) //妈的最后一个点被卡了，那就双Hash，你不是很能吗。 Sum2=(Sum2*Prime[S[a]-‘A‘])%INF2; for (int a=1;a<=Num;a++) if (Sum1==i[a].T1&&Sum2==i[a].T2) { T=true; break; } if (!T) { i[++Num].T1=Sum1; i[Num].T2=Sum2; } } printf("%d",Num); fclose(stdin);fclose(stdout); return 0;}
单词分类
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。