MAP
Time Limit: 1000 MS Memory Limit: 65536 KB
64-bit integer IO format: %I64d , %I64u Java class name: Main
[Submit] [Status] [Discuss]
Description
Many people get information from Baidu、Google、Bing and so on. OK, now we will consider how to test the performance of a search system.
The testing is based on an annotation file，annotation file consist of some query，every query has a query word and many reference URL. For example，“MM xxoo.com ooxx.com xoxo.com”，“MM”is the query word and “xxoo.com ooxx.com xoxo.com”is the reference URL.
If we search the query word from search system, we can also get a result list, and then we can test the search performance by the result list and annotation file. You job is calculate the MAP of the search performance. The definition of MAP is：
Rank:
Position of a retrieved URL in the list of retrieved list.
Precision at a given cut-off rank r for a single query:
P(r) = (number of relevant URL of rank r or less) / r
Average precision: defined as follows
Where N is the number of retrieved URL, R is the number of relevant URL, and rel(r) = 1 if URL at rank r is relevant, 0 otherwise.
Mean average precision: average precision for a set of queries is defined as follows:
Where Q is the number of queries.
The testing is based on an annotation file，annotation file consist of some query，every query has a query word and many reference URL. For example，“MM xxoo.com ooxx.com xoxo.com”，“MM”is the query word and “xxoo.com ooxx.com xoxo.com”is the reference URL.
If we search the query word from search system, we can also get a result list, and then we can test the search performance by the result list and annotation file. You job is calculate the MAP of the search performance. The definition of MAP is：
Rank:
Position of a retrieved URL in the list of retrieved list.
Precision at a given cut-off rank r for a single query:
P(r) = (number of relevant URL of rank r or less) / r
Average precision: defined as follows
Where N is the number of retrieved URL, R is the number of relevant URL, and rel(r) = 1 if URL at rank r is relevant, 0 otherwise.
Mean average precision: average precision for a set of queries is defined as follows:
Where Q is the number of queries.
Input
The first line of input contains T, the number of test cases.
For each test case start with a number n, the query number of annotation file. Then follows 2n lines, the first n lines are the annotation, every line means a query that has a word in front and the reference URL followed. The next n lines are the search result of the queries in annotation, every line means the search result of a query that has the search word in front and the retrieved URL followed.
n <= 100.
The length of a line <= 10000.
The length of a URL and word <= 50.
For each test case start with a number n, the query number of annotation file. Then follows 2n lines, the first n lines are the annotation, every line means a query that has a word in front and the reference URL followed. The next n lines are the search result of the queries in annotation, every line means the search result of a query that has the search word in front and the retrieved URL followed.
n <= 100.
The length of a line <= 10000.
The length of a URL and word <= 50.
Output
Case number ant the MAP value with 6 digits after decimal point.
Sample Input
1 3 Banana banana.com Apple iphone.com ipad.com Software Microsoft.com IBM.com Google.com Banana asd.com banana.com Apple gdfgd.com iphone.com ipad.com Software gdf.com wer.com tre.com
Sample Output
Case #1: 0.361111
Source
2012 Multi-University Training Contest 3
题目大意：
一个网址：MM xxoo.com ooxx.com xoxo.com 包括一个疑问词：MM，若干个数的URL： xxoo.com ooxx.com xoxo.com （3个URL）。题目说测试搜索引擎的性能，先输入一个网址，会返回一个网址（后输入的网址），称先输入网址的URL为相关URL(relevant URL)，称后输入的URL为retrieved URL。
rank :Position of a retrieved URL in the list of retrieved list.：后输入的URL在它所在的URL列表中的位置。
P(r) = (number of relevant URL of rank r or less) / r = （后输入的在 rank r 以内的相关URL的个数，可能为0）/r
N：后输入的URL的个数
R：先输入的URL的个数
rel(r)：若后输入的URL与先输入的URL相同则为1，不同则为0
Q：疑问词MM的个数
解题分析：
按照题意输入，按公式模拟，用map数组标记先输入的URL，值得注意的是，从URL列表中提取每个URL时，用到了 istringstream类，它在一个长字符串中提取用空格隔开的字符的。
例：
1 #include<iostream> 2 #include<sstream> //istringstream 必须包含这个头文件 3 #include<string> 4 using namespace std; 5 int main() 6 { 7 string str="i am a boy"; 8 istringstream a (str); 9 string s; 10 while(a>>s) //提取一个单词s且s不为空 11 { 12 cout<<s<<endl; 13 } 14 return 0; 15 }
解题代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<map> 5 #include<sstream> 6 using namespace std; 7 #define N 110 8 #define M 10005 9 int R[N]; 10 char a[M]; 11 map<string,int>mp[N]; 12 void Init(int k) 13 { 14 istringstream str(a); ///istringstream是一个类，str为它的一个对象 15 ///这里使用构造函数接受一个字符串a 16 string tmp; 17 int tot = 0; 18 str >> tmp; ///提取一个单词，空格用于区分单词，不可能被提取到单词中 19 ///其实如果自己模拟出错，应该就是把空格提到了单词中 20 ///这个语句是把MM提取出来了 21 mp[k].clear(); 22 while(str >> tmp){ ///开始提取先输入的URL 23 tot++; 24 mp[k][tmp] = 1; 25 } 26 R[k] = tot; ///得到的是先输入的URL的个数 27 } 28 double Get_AveP(int k) 29 { 30 istringstream str(a); 31 string tmp; 32 int r = 0,u = 0; ///p(r)=u/r 33 double res = 0; 34 str >> tmp; ///提取后输入的MM 35 while(str >> tmp){ ///提取后输入的URL 36 ++r; 37 if(mp[k][tmp] == 1) 38 { 39 u++; 40 res += u*1.0/r; ///res就是rel为1的时候p（r）的累加和 41 } 42 } 43 return res/R[k]; 44 } 45 int main() 46 { 47 int t,n,ca=0; 48 scanf("%d",&t); 49 while(t--) 50 { 51 scanf("%d",&n); 52 getchar(); 53 for(int i = 1; i <= n; i++) 54 { 55 gets(a); 56 Init(i); 57 } 58 double MAP = 0.0; 59 for(int i = 1; i <= n; i++) 60 { 61 gets(a); 62 MAP += Get_AveP(i); 63 } 64 MAP /= n; 65 printf("Case #%d: %.6lf\n",++ca,MAP); 66 } 67 return 0; 68 }
转载于:https://www.cnblogs.com/yangxingzhe8102/p/5939264.html
今天的文章G — HDU 4329 MAP分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/57961.html
