首页 > > 程序设计 > C/C++ >

Difficult Melody（映射）

2018-06-17 23:41:45来源：未知阅读 ()

题目链接

http://vjudge.net/contest/137242#problem/D

Description

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.

Input

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.

Output

For each test case, print the case number and the most difficult melody. If there is more than one solution, output the lexicographically smallest one. If there is no solution, output the string `No solution'.

Sample Input

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

Sample Output

Case 1: BFC 
Case 2: No solution


题意：输入n,m,k  接下来的n行，每行输入一个1~100的字符串（只包含大写字母`C', `D', `E', `F', `G', `A', `B'），然后输入"Yes" 或者"No"  求其中长为k的最难字符串，最难字符串定义如下：设这个子串在n个串中出现p次，在表示为"Yes"的串中出现q次，在同一个串中不重复计算只算一次，q/p比值越小难度越大，并且要保证p>=m 否则不考虑这个字符串，如果有多个字符串比值相同，输出p较大的支付串，如果有多个p也相同，输出字典序较小的字符串；

思路：用两个集合分别记录这些长为k的子串在n个串中出现的次数和在"Yes"表示的串中出现的次数；

代码如下：

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <map>
#include <bitset>
using namespace std;
typedef long long LL;
map<string,int>mp1;
map<string,int>mp2;///Yes;
map<string,int>mp3;
map<string,int>::iterator it;

int main()
{
    int n,m,k,Case=1;
    while(scanf("%d",&n)&&n)
    {
        scanf("%d%d",&m,&k);
        mp1.clear();
        mp2.clear();
        char s1[105],s2[10];
        for(int j=0; j<n; j++)
        {
            scanf("%s%s",s1,s2);
            int len=strlen(s1);
            mp3.clear();
            for(int i=len-k; i>=0; i--)
            {
                s1[i+k]='\0';
                string s=(string)(s1+i);
                if(mp3[s]==0){
                    mp3[s]++;
                    mp1[s]++;
                    if(s2[0]=='Y') mp2[s]++;
                }
            }
        }
        int t1=9999,t2=99;
        string str="";
        for(it=mp1.begin(); it!=mp1.end(); it++)
        {
            if(it->second>=m)
            {
                int w1=mp2[it->first];
                int w2=it->second;
                int f=w1*t2-w2*t1;
                if(f<0||f==0&&w2>t2||f==0&&w2==t2&&(str>(it->first)))
                {
                    str="";
                    str+=it->first;
                    t1=w1;
                    t2=w2;
                }
            }
        }
        printf("Case %d: ",Case++);
        if(t1==9999&&t2==99) puts("No solution");
        else cout<<str<<endl;
    }
    return 0;
}