首页 > 基础算法 > 递归和分治 > hdu 1604 Letter Sequence Analysis-分治-[解题报告]
2013
12-12

hdu 1604 Letter Sequence Analysis-分治-[解题报告]

Letter Sequence Analysis

问题描述 :

Cryptographic analysis makes extensive use of the frequency with which letters and letter sequences occur in a language. If an encrypted text is known to be in english, for example, a great deal can be learned from the fact that the letters E, L, N, R, S, and T are the most common ones used in written english. Even more can be learned if common letter pairs, triplets, etc. are known.
For this problem you are to write a program which accepts as input a text file of unspecified length and performs letter sequence analysis on the text. The program will report the five most frequent letter sequences for each set of sequences from one to five letters. That is it will report the individual characters which occur with the five highest frequencies, the pairs of characters which occur with the five highest frequencies, and so on up to the letter sequences of five characters which occur with the five highest frequencies.

The program should consider contiguous sequences of alphabetic characters only, and case should be ignored (e.g. an `a’ is the same as an `A’). A report should be produced using the format shown in the example at the end of this problem description. For each sequence length from one to five, the report should list the sequences in descending order of frequency. If there are several sequences with the same frequency then all sequences should be listed in alphabetical order as shown (list all sequences in upper case). Finally, if there are less than five distinct frequencies for a particular sequence length, simply report as many distinct frequency lists as possible.

Examples

When a text file containing simply the line “Peter Piper Picks Pickles!” is used as input, the output should appear as shown here:

Analysis for Letter Sequences of Length 1
—————————————–
Frequency = 5, Sequence(s) = (P)
Frequency = 4, Sequence(s) = (E)
Frequency = 3, Sequence(s) = (I)
Frequency = 2, Sequence(s) = (C,K,R,S)
Frequency = 1, Sequence(s) = (L,T)

Analysis for Letter Sequences of Length 2
—————————————–
Frequency = 3, Sequence(s) = (PI)
Frequency = 2, Sequence(s) = (CK,ER,IC,PE)
Frequency = 1, Sequence(s) = (ES,ET,IP,KL,KS,LE,TE)

Analysis for Letter Sequences of Length 3
—————————————–
Frequency = 2, Sequence(s) = (ICK,PIC)
Frequency = 1, Sequence(s) = (CKL,CKS,ETE,IPE,KLE,LES,PER,PET,PIP,TER)

Analysis for Letter Sequences of Length 4
—————————————–
Frequency = 2, Sequence(s) = (PICK)
Frequency = 1, Sequence(s) = (CKLE,ETER,ICKL,ICKS,IPER,KLES,PETE,PIPE)

Analysis for Letter Sequences of Length 5
—————————————–
Frequency = 1, Sequence(s) = (CKLES,ICKLE,PETER,PICKL,PICKS,PIPER)

When the first three paragraphs of this problem description are used as input, the output should appear as shown here:

Analysis for Letter Sequences of Length 1
—————————————–
Frequency = 201, Sequence(s) = (E)
Frequency = 112, Sequence(s) = (T)
Frequency = 96, Sequence(s) = (S)
Frequency = 90, Sequence(s) = (R)
Frequency = 84, Sequence(s) = (N)

Analysis for Letter Sequences of Length 2
—————————————–
Frequency = 37, Sequence(s) = (TH)
Frequency = 33, Sequence(s) = (EN)
Frequency = 27, Sequence(s) = (HE)
Frequency = 24, Sequence(s) = (RE)
Frequency = 23, Sequence(s) = (NC)

Analysis for Letter Sequences of Length 3
—————————————–
Frequency = 24, Sequence(s) = (THE)
Frequency = 21, Sequence(s) = (ENC,EQU,QUE,UEN)
Frequency = 12, Sequence(s) = (NCE,SEQ,TER)
Frequency = 9, Sequence(s) = (CES,FRE,IVE,LET,REQ,TTE)
Frequency = 8, Sequence(s) = (ETT,FIV)

Analysis for Letter Sequences of Length 4
—————————————–
Frequency = 21, Sequence(s) = (EQUE,QUEN)
Frequency = 20, Sequence(s) = (UENC)
Frequency = 12, Sequence(s) = (ENCE,SEQU)
Frequency = 9, Sequence(s) = (FREQ,NCES,REQU)
Frequency = 8, Sequence(s) = (ETTE,FIVE,LETT,TTER)

Analysis for Letter Sequences of Length 5
—————————————–
Frequency = 21, Sequence(s) = (EQUEN)
Frequency = 20, Sequence(s) = (QUENC)
Frequency = 12, Sequence(s) = (SEQUE,UENCE)
Frequency = 9, Sequence(s) = (ENCES,FREQU,REQUE)
Frequency = 8, Sequence(s) = (ETTER,LETTE)

题目链接:http://acm.hit.edu.cn/hoj/problem/view?id=1604

本题继续练习二分。

这题太恶心了,精度卡的,足够把人烦死,WA了N次。

注意一个重要的地方就行了使用%.nlf的时候,其实是会四舍五入的。这时倒不如手工来算。

注意标注的两个要点:

上代码:

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;

long long array[10003];

int s = 10000;
int n,k;

bool cmp(long long a,long long b)
{
    return a>b;
}
int calc(long long m)
{
    int p = 0;
    for(int i=0;i<n;i++)
    {
        p += array[i]/m;
    }

    return p>=k;
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif


    int l,r;
    int ans;
    double a;
    while(scanf("%d %d",&n,&k) == 2)
    {
        ans = 0;
        for(int i=0;i<n;i++)
        {
            scanf("%lf",&a);
            array[i]  = (a+1e-8) * s;//要点一
        }
        sort(array,array+n,cmp);
        l = s/100;
        r = array[0];
        while(l<=r)
        {
            long long m = (l + r)/2;
            if(calc(m)>0)
            {
                l = m+1;
                ans = m;
            }
            else
            {
                r = m-1;
            }
        }
        //要点二
        int th = ans/10000;
        int hu = (ans - th * 10000)/1000;
        int te = (ans - th * 10000 - hu * 1000)/100;
        printf("%d.%d%d\n",th,hu,te);
    }
    return 0;
}

解题转自:http://blog.csdn.net/niuox/article/details/8536029


  1. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。