首页 > ACM题库 > HDU-杭电 > HDU 2978-Difficult Melody[解题报告]HOJ
2014
02-24

HDU 2978-Difficult Melody[解题报告]HOJ

Difficult Melody

问题描述 :

You’re addicted to a little game called `remember the melody’: you hear some notes, and then you repeat it. In most cases, the longer the melody, the harder to repeat, but it isn’t always true. Also, melodies of the same length are usually not equally easy to remember. To find a way to define the remember difficulty of a melody, you invented a statistics-based model:

Suppose you’re investigating melodies of a particular length. If a melody appeared in p games, among which you successfully repeated q games, the smaller q/p , the more difficult the melody. If there is more than one melody having the minimal ratio, the one with larger p is considered more difficult. But there is an exception: if p is smaller than a threshold m , you simply ignore it (you can’t call it difficult if you haven’t tried it a lot of times, can you?). The melody appears in a game if its string representation is a consecutive substring occurring at least once in that game.

Write a program to find the most difficult melody of length k , given n games you’ve played.

输入:

The input contains several test cases. Each case consists of three integers n, m, k (1<=m<=n<=100, 1<=k<=20 ) , the next n lines each contain two strings separated by exactly one space: the game, and whether you successfully repeated it. The first string will contain at least one at most 100 upper case letters `C’, `D’, `E’, `F’, `G’, `A’, `B’. The second string will be either `Yes’ or `No’ (case sensitive). The last test case is followed by a single zero, which should not be processed.

输出:

The input contains several test cases. Each case consists of three integers n, m, k (1<=m<=n<=100, 1<=k<=20 ) , the next n lines each contain two strings separated by exactly one space: the game, and whether you successfully repeated it. The first string will contain at least one at most 100 upper case letters `C’, `D’, `E’, `F’, `G’, `A’, `B’. The second string will be either `Yes’ or `No’ (case sensitive). The last test case is followed by a single zero, which should not be processed.

样例输入:

3 2 3 
EEECEG Yes 
BFCEG No 
DEBFCEGEEC No 
3 2 2 
AAA No 
BBB No 
CCC Yes 
0

样例输出:

Case 1: BFC 
Case 2: No solution

#include <cstdio>
#include <iostream>
#include <fstream>
#include <cstring>
#include <string>
#include <map>
#define OP(s) cout<<#s<<"="<<s<<" ";
#define PP(s) cout<<#s<<"="<<s<<endl;
#define SET(s,x) memset(s,x,sizeof(s));
using namespace std;
typedef long long LL;

struct Node
{
    int yes,count;
    string str;
}a[10010];
int tota = 0;

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("test.txt","r",stdin);
    #endif

    int n,m,k;
    while (~scanf("%d",&n),n)
    {
        static int cas = 0;
        printf("Case %d: ",++cas);
        tota = 0;

        int m,k;
        cin>>m>>k;

        string s1,s2;
        map<string,int> mp;
        while (n--)
        {
            map<string,bool> vd;
            cin>>s1>>s2;
//OP(s1)PP(s2)
            int len = s1.length();
            for (int i = 0;i <= len-k;i++)
            {
                string tmp = "";
                for (int j =0;j < k;j++) tmp += s1[i+j];
//PP(tmp)
                if (!vd[tmp])
                {
                    vd[tmp] = 1;
                    int id;
                    if (mp[tmp] == 0)
                    {
                        mp[tmp] = ++tota;
                        id = tota;
                        a[id].count = 0;
                        a[id].yes = 0;
                        a[id].str = tmp;
                    }
                    else id = mp[tmp];
                    a[id].count++;
                    if (s2 == "Yes") a[id].yes++;
//                    OP(id)OP(a[id].str)OP(a[id].yes)PP(a[id].count)
                }
            }
        }

        int ans = -1,ansc = 1,ansy = 2;
        for (int i = 1;i <= tota;i++)
        {
            if (a[i].count < m) continue;
            int y1 = a[i].yes,c1 = a[i].count;
            if (y1 * ansc < ansy*c1
                || y1*ansc == ansy*c1 && c1 > ansc
                || y1*ansc == ansy*c1 && c1 == ansc && a[i].str < a[ans].str
            )
            {
                ans = i,ansy = y1,ansc = c1;
            }
        }
        if (ans == -1) cout<<"No solution\n";
        else cout<<a[ans].str<<endl;
    }


    return 0;
}