程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> NYOJ 285 尋找克隆人(map+計數)

NYOJ 285 尋找克隆人(map+計數)

編輯：C++入門知識

NYOJ 285 尋找克隆人(map+計數)

題目描述

美國的一個小鎮近日被外星人襲擊，一部分居民被其帶走並克隆，現在，科學家提取了鎮上一些人的DNA,請找出其中具有相同被克隆個數的DNA個數，例如下面的9個序列

AAAAAA
ACACAC
GTTTTG
ACACAC
GTTTTG
ACACAC
ACACAC
TCCCCC
TCCCCC
其中TCCCCC,GTTTTG分別具有兩個相同個體，ACACAC有四個，AAAAAA為一個，則按照行數對應輸出其個數

第一行1，第二行2，第四行1，其他行輸出0，共9行

輸入序列數不超過20000，每序列不超過20個字符
輸入以0 0結束輸出

如題中描述輸出即可樣例輸入

9 6
AAAAAA
ACACAC
GTTTTG
ACACAC
GTTTTG
ACACAC
ACACAC
TCCCCC
TCCCCC
0 0

樣例輸出

題目分析：

題目的意思是，求出出現i次的字符串的個數並輸出，就是一道map+計數的問題。用一個數組a[]記錄出現的次數，例如a[i]=4;表示出現i次的字符串為4.

AC代碼：

 
/**
 *哈希+計數
 */
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int a[20005];
int main()
{
    int n,m;
    while(cin>>n>>m&&n+m){
        string str;
        map hp;
        memset(a,0,sizeof(a));
        for(int i=0;i>str;
            hp[str]++;
        }
        map::iterator it;
        for(it=hp.begin();it!=hp.end();++it){
            ++a[it->second];//計數
        }
        for(int i=1;i<=n;i++){
            cout<