HDU5199 – Gunner(离散)

题目链接:HDU5199

【分析】离散化一下所有高度,统计每个高度有饥渴树,然后按查询输出并归零就好了。也是水题,看数据量有10^6就手写了一个hash,终测竟然只跑了405ms

【AC CODE】1045ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <map>
//#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 1000000+10, MOD = 1000007;
struct HASH{
    int head[MOD], next[MAXN], sum[MAXN], cnt, node[MAXN], num[MAXN];
    void clear(){
        cnt = 0;
        clc(head,-1);
        clc(sum,0);
    }
    int hash(int s){
        return s%MOD;
    }
    void insert(int s, int v){
        int id = hash(s);
        int u = head[id];
        while(~u){
            if(s == node[u])
            {
                sum[u]++;
                return;
            }
            u = next[u];
        }
        sum[cnt] = 1;
        num[cnt] = v;
        node[cnt] = s;
        next[cnt] = head[id];
        head[id] = cnt++;
    }
    int find(int s){
        int id = hash(s);
        int u = head[id];
        while(~u){
            if(node[u] == s) return num[u];
            u = next[u];
        }
        return -1;
    }
}vis;
int sum[MAXN], cnt;

int in()//快速读入
{
    int ch,ans;
    while((ch = getchar()) < '0' || '9' < ch);
    ans = ch-'0';
    while((ch = getchar()) >= '0' && '9' >= ch) ans = (ans<<3)+(ans<<1)+ch-'0';
    return ans;
}

int get_id(int x)
{
    int ans = vis.find(x);
    if(-1 == ans)
    {
        vis.insert(x,cnt++);
        return cnt-1;
    }
    return ans;
}
int main()
{
#ifdef SHY
    freopen("d:\\1.txt", "r", stdin);
#endif
    int n,m;
    while(~scanf("%d %d%*c", &n, &m))
    {
        clc(sum,0);
        vis.clear();
        cnt = 0;
        rep(i,0,n) sum[get_id(in())]++;
        rep(i,0,m)
        {
            int h = get_id(in());
            printf("%d\n", sum[h]);
            sum[h] = 0;
        }
    }
    return 0;
}

 

发表评论

邮箱地址不会被公开。 必填项已用*标注

请输入正确的验证码