Problem C: 余弦定理
Time Limit: 1 Sec Memory Limit:
128 MB
Submit: 338 Solved: 76
[Submit][Status][Web
Board]
Description
小Q在埃森哲工作有一段时间了，他觉得自己在一个岗位山做的时间有点长， 所以刚刚换了一个team，是一个搞数据挖掘文本处理的team。在文本挖掘领域，经常要将文本抽象为一个向量，而计算两个文本的相似度就是计算这两个向量的夹角。
现在我们具体的介绍如何将两段文本向量化后求取相似度：
1. 首先统计每个文本中所有词出现的频度，对于["I", "like", "nice", "girls"]，可以得到频度向量("I":1, "like":1, "nice":1, "girls":1)。类似的，对于["I", "like", "strong", "boys"]，则可以得到频度向量("I":1, "like":1, "strong":1, "boys":1)。
2. 可以发现两个向量的值完全相同，但是其中所代表的含义完全不相同，所以我们还需要对两个向量做对齐操作，即对各自向量添加一些空项。则两个新向量为("I":1, "like":1, "nice":1, "girls":1, "strong":0, "boys":0)和("I":1, "like":1, "nice":0, "girls":0, "strong":1, "boys":1)。
3. 使用余弦定理对两个向量(1, 1, 1, 1, 0, 0)和(1, 1, 0, 0, 1, 1)求夹角，近似表示两个文本的近似度。
Sim(A, B) = (A[0]*B[0]+A[1]*B[1]+...+A[n]*B[n])/(sqrt(A[0]*A[0]+A[1]*A[1]+...+A[n]*A[n])*sqrt(B[0]*B[0]+B[1]*B[1]+...+B[n]*B[n]))。
现在给你两段文本A和B，希望你用如上所述的方法计算Sim(A, B)。
Input
多组测试数据。每组数据两行。
第1行：输入一个文本A，文本由若干单词组成。
第2行: 输入一个文本B，文本由若干单词组成。
所有单词都只由英文大小写字母构成，相邻单词由一个空格隔开。
Output
对于每组数据。输出一行，包含一个保留小数点后两位的浮点数，代表Sim(A, B)。
Sample Input
I like strong boysI like nice girls
Sample Output
0.50
HINT
输入比较困难，可以先读入一行到临时空间，再用sprintf或strstream来格式化。其余就比较简单了。
格式化版本：
#include <cmath>
#include <cstdio>
#include <iostream>
#include <strstream>
#include <map>
using namespace std;
inline int getint()
{
int res=0;char tmp;bool sgn=1;
do tmp=getchar();
while (!isdigit(tmp)&&tmp!='-');
if (tmp=='-'){sgn=0;tmp=getchar();}
do res=(res<<3)+(res<<1)+tmp-'0';
while (isdigit(tmp=getchar()));
return sgn?res:-res;
}
map<string,int> h1;
map<string,int> h2;
char word[10000000];
bool work(map<string,int> &hash)
{
string line;
string word;
strstream ss1;
getline(cin,line);
if (cin.eof()) return false;
ss1 << line;
while (!ss1.eof())
{
ss1 >> word;
hash[word]++;
}
return true;
}
map<string,int>::iterator it1;
map<string,int>::iterator it2;
int main()
{
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
bool first = true;
for (;;)
{
h1.clear();
h2.clear();
if (!work(h1)) break;
work(h2);
if (!first)
printf("\n");
first = false;
int fenzi = 0;
int fenmu1 = 0;
int fenmu2 = 0;
string tmp;
for (it1=h1.begin();it1!=h1.end();it1++)
{
fenmu1 += it1->second*it1->second;
}
for (it1=h2.begin();it1!=h2.end();it1++)
{
fenmu2 += it1->second*it1->second;
}
for (it1=h1.begin();it1!=h1.end();)
{
tmp = it1->first;
it2 = h2.find(tmp);
if (it2!=h2.end())
{
fenzi += it1->second*it2->second;
h2.erase(it2);
}
it2 = it1;
it1 ++;
h1.erase(it2);
}
for (it2=h2.begin();it2!=h2.end();)
{
tmp = it2->first;
it1 = h1.find(tmp);
if (it1!=h1.end())
{
fenzi += it1->second*it2->second;
h1.erase(it1);
}
it1 = it2;
it2 ++;
h2.erase(it1);
}
//printf("%.2f\n",sqrt(double(fenmu1)));
printf("%.2f",double(fenzi)/(sqrt(double(fenmu1))*sqrt(double(fenmu2))));
}
return 0;
}
手动处理版本：
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <map>
using namespace std;
inline int getint()
{
int res=0;char tmp;bool sgn=1;
do tmp=getchar();
while (!isdigit(tmp)&&tmp!='-');
if (tmp=='-'){sgn=0;tmp=getchar();}
do res=(res<<3)+(res<<1)+tmp-'0';
while (isdigit(tmp=getchar()));
return sgn?res:-res;
}
map<string,int> h1;
map<string,int> h2;
char word[10000000];
bool work(map<string,int> &hash)
{
for(;;)
{
for (;;)
{
int tt = scanf("%[^\n ]",word);
if (tt == EOF)
return false;
if (tt == 0)
getchar();
else
break;
}
hash[string(word)] ++;
if (getchar() == '\n')
break;
}
return true;
}
map<string,int>::iterator it1;
map<string,int>::iterator it2;
int main()
{
bool first = true;
for (;;)
{
h1.clear();
h2.clear();
if (!work(h1)) break;
work(h2);
if (!first)
printf("\n");
first = false;
int fenzi = 0;
int fenmu1 = 0;
int fenmu2 = 0;
string tmp;
for (it1=h1.begin();it1!=h1.end();it1++)
{
fenmu1 += it1->second*it1->second;
}
for (it1=h2.begin();it1!=h2.end();it1++)
{
fenmu2 += it1->second*it1->second;
}
for (it1=h1.begin();it1!=h1.end();)
{
tmp = it1->first;
it2 = h2.find(tmp);
if (it2!=h2.end())
{
fenzi += it1->second*it2->second;
h2.erase(it2);
}
it2 = it1;
it1 ++;
h1.erase(it2);
}
for (it2=h2.begin();it2!=h2.end();)
{
tmp = it2->first;
it1 = h1.find(tmp);
if (it1!=h1.end())
{
fenzi += it1->second*it2->second;
h1.erase(it1);
}
it1 = it2;
it2 ++;
h2.erase(it1);
}
//printf("%.2f\n",sqrt(double(fenmu1)));
printf("%.2f",double(fenzi)/(sqrt(double(fenmu1))*sqrt(double(fenmu2))));
}
return 0;
}