首页 > 代码库 > POJ 2159（判断可重集合相等&hash）
POJ 2159（判断可重集合相等&hash）
POJ 2159
题目归结为判断两个自然数多集（允许有重复元素的集合）a, b是否相等。用快排比较的效率是O(nlgn).
此题中a.b则分别是每个字母个数集。
下面提出一种O(n)的方法供大家参考。
猜想：若 sum(a^i) = sum(b^i)，i = 0, 1, 2, 则 a = b。
证明：？
注意
sum(s^0) 是多集s中元素的数目
sum(s^1) 是多集s中元素的和
sum(s^2) 是多集s中元素的平方和
即比较多集的三个统计值即可。以上算法是AC的。但是我还没有一个满意的证明。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#define MAXN 200001
#define MOD 1000000007
#define INF 0x7fffffff
#define EPS 1e-8
#define PI acos(-1.0)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define bug(a) cout<<"bug---->"<<a<<endl;
#define FIN freopen("datain.txt","r",stdin);
#define FOUT freopen("dataout.txt","w",stdout);
#define mem(a,b) memset(a,b,sizeof(a))
//#pragma comment (linker,"/STACK:102400000,102400000")
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
int main()
{
string s1,s2;
while(cin>>s1>>s2)
{
int n=s1.length();
int hash_1=0,hash_11=0;
int hash_2=0,hash_22=0;
int num1[30]={0};
int num2[30]={0};
for(int i=0;i<n;i++)
{
num1[s1[i]-'A']++;
num2[s2[i]-'A']++;
}
//bug(hash_1)
//bug(hash_2)
for(int i=0;i<26;i++)
{
hash_1+=num1[i];
hash_11+=num1[i]*num1[i];
hash_2+=num2[i];
hash_22+=num2[i]*num2[i];
}
if(hash_1==hash_2&&hash_11==hash_22)
cout<<"YES\n";
else
cout<<"NO\n";
}
return 0;
}
POJ 2159（判断可重集合相等&hash）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。