首页 > 代码库 > HDU2836 Traversal

HDU2836 Traversal

2024-08-14 08:47:44   220人阅读

题解:

dp+树状数组优化

跟hdu2227差不多，只不过改变了一下范围。更改一下sum的方式即可

但是这题的a[i]范围比较大。

在用树状数组时，一种是直接使用map，另一种是使用hash+二分

代码:

map优化 1060ms

#include<bits/stdc++.h>using namespace std;#define LL long long const int N=100010;const int M=100000100;const int mod=9901;int n,h,Min,Max;int a[N],dp[N];map<int,int> c;int lowbit(int x){return x&-x;}void add(int x,int v){    while(x<M){        c[x]+=v;        c[x]%=mod;        x+=lowbit(x);    }}int sum(int x){    int cnt=0;    while(x){        cnt+=c[x];        cnt%=mod;        x-=lowbit(x);    }    return cnt;}int main(){    while(~scanf("%d%d",&n,&h)){        c.clear();        for(int i=1;i<=n;i++){             scanf("%d",&a[i]);             Min=max(a[i]-h,1);             Max=min(a[i]+h,M-5);             dp[i]=sum(Max)-sum(Min-1);             add(a[i],dp[i]+1);        }        printf("%d\n",((sum(M)-n)%mod+mod)%mod);    }    return 0;}

 

hash+二分 156ms

#include<bits/stdc++.h>using namespace std;#define LL long long const int N=100010;const int M=100000100;const int mod=9901;int a[N],t[N],c[N];int n,h,tot;int lowbit(int x){return x&-x;}void add(int x,int v){    while(x<=tot){        c[x]+=v;        c[x]%=mod;        x+=lowbit(x);    }}int sum(int x){    int cnt=0;    while(x){        cnt+=c[x];        cnt%=mod;        x-=lowbit(x);    }    return cnt;}int Bin(int v){    int l=1,r=tot;    while(l<=r){        int m=(l+r)>>1;        if(v==t[m]) return m;        if(v>t[m]) l=m+1;        else       r=m-1;    }}int lBin(int v){    int l=1,r=tot,ans=1;    while(l<=r){        int m=(l+r)>>1;        if(t[m]>=v){            r=m-1;            ans=m;        }        else l=m+1;    }    return ans;}int rBin(int v){    int l=1,r=tot,ans=tot;    while(l<=r){        int m=(l+r)>>1;        if(t[m]<=v){            l=m+1;            ans=m;        }        else r=m-1;    }    return ans;}int main(){    while(~scanf("%d%d",&n,&h)){        for(int i=1;i<=n;i++){            scanf("%d",&a[i]);            t[i]=a[i];        }        sort(t+1,t+n+1);        tot=0;        for(int i=1;i<=n;i++){            if(i==1||t[i]!=t[i-1]){                t[++tot]=t[i];//去掉重复元素                 c[tot]=0;            }        }        int ans=0;        for(int i=1;i<=n;i++){            int nidx=Bin(a[i]);            int l=lBin(a[i]-h);//大于等于a[i]-h的最小值位置             int r=rBin(a[i]+h);//小于等于a[i]+h的最大值位置             int val=(sum(r)-sum(l-1)+mod)%mod;            ans=(ans+val+1)%mod;            add(nidx,val+1);        }        printf("%d\n",((ans-n)%mod+mod)%mod);    }    return 0;}

 

HDU2836 Traversal


联系
我们