首页 > ACM题库 > HDU-杭电 > HDU 4329-MAP-模拟-[解题报告]HOJ
2015
05-23

HDU 4329-MAP-模拟-[解题报告]HOJ

MAP

问题描述 :

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
Cut the cake

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:
Cut the cake

Where Q is the number of queries.

输入:

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.

输出:

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.

样例输入:

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

样例输出:

Case #1: 0.361111

很恶心的题意,暂时就不说了。 就是题目怎么说,你就怎么写。

http://acm.hdu.edu.cn/showproblem.php?pid=4329

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cctype>
using namespace std;

typedef pair<int,int> pii;
typedef vector<int> vi ;
typedef vector<string> vs;
#define Rep(i,n) for(int i = 0; i < (n); ++i)
#define pb push_back
 
char buf[11111] ;
string tmp ;
struct Query{
    string word ;
    vs url ;
    int len ;
    void get(){
        scanf("%s",buf);
        word = buf ;
        gets(buf);
        istringstream sin( buf ) ;
        for(len = 0 ; sin >> tmp; len++) url.pb(tmp);
    }
}Q[111] ,F[111];

double getQF(int t){
    int n = Q[t].len ;
    int m = F[t].len ;
    int num = 0;

    double ans = 0;
    Rep(j,m)
        Rep(i,n)
            if(Q[t].url[i]==F[t].url[j]){
                num ++ ;
                ans += num*1.0/(j+1);
                break;
            }
    ans /= n ;
    return ans ;
}

int main()
{
    int T , cas = 1;
    scanf("%d",&T);
    while(T--){
        int n ;
        scanf("%d",&n);
        Rep(i,n) Q[i].get();
        Rep(i,n) F[i].get();

        double ans = 0;
        Rep(i,n)ans += getQF(i);
        ans /= n ;
        printf("Case #%d: %.6f\n",cas++,ans);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/julyana_lin/article/details/8101161