hdu 5199 map或二分或哈希

題目描述：給出n棵樹的高度，每棵樹上都站著一只鳥，槍手Jack站在最左邊那棵樹的左邊對鳥進行射擊，當Jack在高度為H的地方向右發射一顆子彈的時候，高度為H的樹上的鳥兒就會掉落（注：其他樹上的鳥兒不會飛走或掉落，這不是腦經急轉彎！）。Jack會射擊多次，他想知道每次射擊會有多少鳥兒掉落下來。

思路：題意十分清晰，思路也很簡單，只要實現這種映射關系就行了，數據量比較大。

方法1：map+IO外掛水之

#include <cstdio>
#include <cctype>
#include <map>
using namespace std;

map<int, int> mp;
int n, m, tmp;
char buffer[10];

void print_d( int x )
{
    if ( x == 0 )
    {
        putchar('0');
    }
    else
    {
        int p = 0;
        while ( x )
        {
            buffer[p++] = x % 10 + '0';            
            x = x / 10;
        }
        for ( int i = p - 1; i >= 0; i-- )
        {
            putchar(buffer[i]);
        }
    }
    putchar('\n');
}

void scan_d( int & x )
{
    char ch = getchar();
    while ( !isdigit(ch) ) ch = getchar();
    x = 0;
    do
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    } while ( isdigit(ch) );
}

int main ()
{
    while ( scanf("%d%d", &n, &m) != EOF )
    {
        mp.clear();
        while ( n-- )
        {
            scan_d(tmp);
            mp[tmp]++;
        }
        while ( m-- )
        {
            scan_d(tmp);
            print_d(mp[tmp]);
            mp[tmp] = 0;            
        }
    }
    return 0;
}

這樣寫完全是對的，不過比csc的代碼要慢一點，原因如下：

當調用mp[tmp]的時候，如果tmp在map中不存在，則默認會插入一個tmp到0的映射然后返回，所以這樣寫會讓節點數增多，查詢效率變低。

證明代碼如下：

#include <iostream>
#include <cstdlib>
#include <map>
using namespace std;

int main ()
{
    map<int, int> mp;
    cout << "mp is empty: " << mp.size() << endl;
    cout << mp[111] << endl;
    cout << "The size is: " << mp.size() << endl;
    cout << mp[222] << endl;
    cout << "The size is: " << mp.size() << endl;
    for ( map<int, int>::iterator it = mp.begin(); it != mp.end(); it++ )
    {
        cout << it->first << " maps into " << it->second << endl;
    }
    system("pause");
    return 0;
}

運行結果如下：

可見確實是這樣，因此可以這樣寫來加快效率：

#include <cstdio>
#include <map>
using namespace std;

map<int, int> mp;
int n, m, tmp;

int main ()
{
    while ( scanf("%d%d", &n, &m) != EOF )
    {
        mp.clear();
        while ( n-- )
        {
            scanf("%d", &tmp);
            mp[tmp]++;
        }
        while ( m-- )
        {
            scanf("%d", &tmp);
            if ( mp.count(tmp) )
            {
                printf("%d\n", mp[tmp]);
                mp.erase(tmp);
            }
            else
            {
                printf("0\n");
            }
        }
    }
    return 0;
}

不過實測差不多，關鍵可能還是hdu服務器不穩定吧，不過mp[tmp] = 0; 還是沒有 mp.erase(tmp); 好，前者刪除節點，后者只是修改映射的值，前者配合mp.count(tmp)理論上更勝一籌。

方法2：二分?略...

方法3：hash

#include <cstdio>
#include <cstring>
using namespace std;

const int N = 5000007;
int hash_table[N];
int cnt[N];
int n, m, tmp;

int hash_key( int key )
{
    return key % N;
}

int kth( int k )
{
    int r = ( k + 1 ) >> 1;
    if ( k & 1 ) return r * r;
    return -r * r;    
}

void insert( int key )
{
    int t = hash_key(key);
    for ( int i = 0; ; i++ )
    {
        int pos = t + kth(i);
        if ( pos < 0 ) pos += N;
        if ( pos >= N ) pos -= N;
        if ( hash_table[pos] == -1 )
        {
            hash_table[pos] = key;
            cnt[pos]++;
            return ;
        }
        else if ( hash_table[pos] == key )
        {
            cnt[pos]++;
            return ;
        }
    }
}

int find( int key )
{
    int t = hash_key(key);
    for ( int i = 0; ; i++ )
    {
        int pos = t + kth(i);
        if ( pos < 0 ) pos += N;
        if ( pos >= N ) pos -= N;
        if ( hash_table[pos] == key )
        {
            int r = cnt[pos];
            cnt[pos] = 0;
            return r;
        }
        else if ( hash_table[pos] == -1 )
        {
            return 0;
        }
    }
}

int main ()
{
    while ( scanf("%d%d", &n, &m) != EOF )
    {
        memset( hash_table, -1, sizeof(hash_table) );
        memset( cnt, 0, sizeof(cnt) );        
        while ( n-- )
        {
            scanf("%d", &tmp);
            insert(tmp);
        }
        while ( m-- )
        {
            scanf("%d", &tmp);
            printf("%d\n", find(tmp));
        }
    }
    return 0;
}

?