首页 > 代码库 > POJ 2352 star level

POJ 2352 star level

2024-07-15 01:26:19   220人阅读

题目链接：

http://poj.org/problem?id=2352

题目大意：
对于每一颗星星来说，都有一个属于自己的level，这个值为其他星星x，y坐标均不大于本星星的个数。输入时按先y由小到大，再x由小到大排列，无相同位置的星星

 

仔细一想其实这道题目根本不需要用到y，我是反向来思考的，构建一个保存x坐标由0到maxn的线段树，因为最后一个星星肯定不可能x，y同时不大于其他星星，所

以从后面开始看，只计算比它x小或相等的星星的个数，用cnt[ans]++，来记录成为ans水平的个数，再删去这个点，继续找上一个点对应的level

 

在这里要注意的是数组的范围，我就因为这个改了半天错，第一次发现数组范围定的不够大也是WA

他这里星星个数为15000，但是我们保存的是x的坐标，所以要看x最大达32000，所以用4*32000的大小保存tree[]，我的代码里懒得修改了就写成了

#define N 15005
int cnt[N],num[2*N],tree[8*N],D,maxn;//开始我写成的是4*N所以报错T T

 1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 #define N 15005 5 int cnt[N],num[2*N],tree[8*N],D,maxn; 6  7 int max(int a,int b) 8 { 9     return a>b?a:b;10 }11 12 void update(int i)13 {14     for(;i^1;i>>=1)15         tree[i>>1]=tree[i]+tree[i^1];16 }17 18 int query(int a,int b)19 {20     int i=D+a-1,j=D+b+1,ans=0;21     for(;i^j^1;i>>=1,j>>=1)22     {23         if(~i&1) ans+=tree[i^1];24         if(j&1)  ans+=tree[j^1];25     }26     return ans;27 }28 29 int main()30 {31     int n,x[N],y;32     while(scanf("%d",&n)!=EOF){33         maxn=0;34         memset(num,0,sizeof(num));35         //memset(tree,0,sizeof(tree));36         for(int i=1;i<=n;i++){37             scanf("%d%d",&x[i],&y);38             maxn=max(maxn,x[i]);39             num[x[i]]++;40         }41         for(D=1;D<maxn+1+2;D<<=1);42         for(int i=1;i<=maxn+1;i++) tree[D+i]=num[i-1];43         for(int i=D-1;i>=1;i--) tree[i]=tree[i<<1]+tree[i<<1|1];44         for(int i=0;i<=n-1;i++) cnt[i]=0;45         //for(int i=1;i<=2*D-1;i++) printf("%d\n",tree[i]);46         for(int i=n;i>=1;i--){47            // printf("%d",query(1,x[i]+1));48             tree[D+x[i]+1]--;49             update(D+x[i]+1);50             cnt[query(1,x[i]+1)]++;51         }52         for(int i=0;i<n;i++) printf("%d\n",cnt[i]);53     }54     return 0;55 }

当然从前往后思考也是一样的，那样的话是不断将x添入线段树，这里有一份是学长的代码，果然比我反向思考的要简洁好多，而且从他的代码也得到了其实tree的底层在没有

得到顶点的必要时，也是可以不必强求定位1<<n这种2的几次方的大小的，而在这里正好适用，因为每次找个数和只求到i^j^1即可（这个代表左右子树）；

代码如下：

#include <cstdio>#include <cstring>const int maxn = 32010;int tree[maxn<<2],a[maxn];int N,D;void update(int i){    for(;i^1;i >>= 1){        tree[i>>1] = tree[i]+tree[i^1];    }}int query(int x,int y){    int i = D+x-1,j = D+y+1,ans = 0;    for(;i^j^1;i >>= 1,j >>= 1){        if(~i&1)    ans += tree[i^1];        if(j&1)     ans += tree[j^1];    }    return ans;}int main(){    while(scanf("%d",&N) != EOF){        memset(tree,0,sizeof(tree));        memset(a,0,sizeof(a));        D = 32010;        for(int i = 0;i < N;i++){            int x,y;            scanf("%d%d",&x,&y);            a[query(1,++x)]++;            tree[D+x]++;            update(D+x);        }        for(int i = 0;i < N;i++)    printf("%d\n",a[i]);    }    return 0;}
View Code

 

 


联系
我们