hdu 1823 二维线段树

2010年12月01日 03:08

题意很明确,貌似主要就是用来测模板的....写的这个二维线段树虽然很长很罗嗦,但还是geilivable的啊,只不过用c++才能过

#include <cstdio>

typedef struct { int l,r; double val; } node1;
double max(double a,double b){return a>b?a:b;};
void swap(double &a,double &b) { double t=a;a=b;b=t; }
struct tree1
{
    node1 node[3000];
    void build(int l,int r,int root)
    {
        node[root].l=l;node[root].r=r;
        node[root].val=-1;
        if(l==r) return;
        int m=(l+r)/2;
        build(l,m,2*root);
        build(m+1,r,2*root+1);
    }
    void update(int x,double val,int root)
    {
        if(node[root].val<val)
            node[root].val=val;
        if(node[root].l == node[root].r)
            return;
        int m=(node[root].l+node[root].r)/2;
        if(x<=m) update(x,val,2*root);
        else update(x,val,2*root+1);
    }
    double query(int l,int r,int root)
    {
        if(node[root].l==l && node[root].r==r)
            return node[root].val;
        int m=(node[root].l+node[root].r)/2;
        if(r<=m) return query(l,r,root*2);
        else if(l>m) return query(l,r,root*2+1);
        else
            return max(query(l,m,root*2),
                    query(m+1,r,root*2+1));
    }
};
typedef struct {int l,r;tree1 tree; } node2;
struct tree2
{
    node2 node[300];
    void build(int xmin,int xmax,int ymin,int ymax,int root)
    {
        node[root].l=xmin;node[root].r=xmax;
        node[root].tree.build(ymin,ymax,1);
        if(xmin==xmax) return;
        int m=(xmin+xmax)/2;
        build(xmin,m,ymin,ymax,2*root);
        build(m+1,xmax,ymin,ymax,2*root+1);
    }
    void update(int x,int y,double val,int root)
    {
        node[root].tree.update(y,val,1);
        if(node[root].l==node[root].r)
            return;
        int m=(node[root].l+node[root].r)/2;
        if(x<=m) update(x,y,val,root*2);
        else update(x,y,val,root*2+1);
    }
    double query(int x1,int x2,int y1,int y2,int root)
    {
        if(node[root].l==x1 && node[root].r==x2)
            return node[root].tree.query(y1,y2,1);

        int m=(node[root].l+node[root].r)/2;
        if(x2<=m) return query(x1,x2,y1,y2,2*root);
        else if(x1>m) return query(x1,x2,y1,y2,2*root+1);
        else
            return max(query(x1,m,y1,y2,root*2)
                    ,query(m+1,x2,y1,y2,root*2+1));
    }
};
tree2 tree;
int main()
{   
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int n,h,hh;char s[2];
    double a,aa,l,ans;
    while(scanf("%d",&n),n)
    {
        tree.build(100,200,0,1000,1);
        while(n--)
        {
            scanf("%s",s);
            if(s[0]=='I')
            {
                scanf("%d %lf %lf",&h,&a,&l);
                tree.update(h,int(a*10),l,1);
            }
            else
            {
                scanf("%d %d %lf %lf",&h,&hh,&a,&aa);
                if(h>hh) {h^=hh;hh^=h;h^=hh;}
                if(a>aa) swap(a,aa);
                ans=tree.query(h,hh,int(a*10),int(aa*10),1);
                if(ans<0) puts("-1");
                else printf("%.1f\n",ans);
            }
        }
    }
}

 

评论(0) 阅读(2852)

poj 2352 第一道树状数组和线段树

2010年11月28日 06:37

拿这个题研究了好几天的树状数组和线段树

题意是给一些星星的x,y坐标,星星的层数为不在其上和其右的星星的个数.

因为星星是先按y的升序再按x的升序给出的,所以之后的星星不会影响前面的星星的层次,用树状数组统计小于等于当前星星x坐标的星星个数即为level.

树状数组的做法是,每读入一组坐标,先算出其level,再更新数组.最后输出的是各level星星数.注意树状数组是从1开始的所以x要+1.数组也不要开小.

#include<cstdio>
#include<cstdlib>
#include<cstring>

#define maxX 32003
#define lowbit(i) ((i)&(-i))
int level[15001];
int tree[maxX];
int n;

void update(int i,int val)
{
    while(i<=maxX)
    {
        tree[i]+=val;
        i+=lowbit(i);
    }
}
int sum(int i)
{
    int s=0;
    while(i>0)
    {
        s+=tree[i];
        i-=lowbit(i);
    }
    return s;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        int x,y; scanf("%d%d",&x,&y);
        ++x;
        ++level[sum(x)];
        update(x,1);
    }
    for(int i=0;i<n;i++)
        printf("%d\n",level[i]);
}

线段树的做法是,每插入一颗星星(设其横坐标为x),将区间[x,32000]加1,即后面的星星的层数加1,这样后面的星星调用query(x`)便可返回层数.

#include <cstdio>
struct node
{
    int l,r,val;
} tree[32000*4];

void create(int l,int r,int root)
{
    tree[root].l=l;tree[root].r=r;
    tree[root].val=0;
    if(l==r) return;
    int m=(l+r)/2;
    create(l,m,root*2);
    create(m+1,r,root*2+1);
}

void update(int l,int r,int root,int val)
{
    if(tree[root].l==l && tree[root].r==r)
    {
        tree[root].val+=val;
        return;
    }
    int m=(tree[root].l+tree[root].r)/2;
    if(r<=m) update(l,r,root*2,val);
    else if(l>m) update(l,r,root*2+1,val);
    else
    {
        update(l,m,root*2,val);
        update(m+1,r,root*2+1,val);
    }
}
int query(int x,int root)
{
    if(tree[root].l==tree[root].r)
        return tree[root].val;
    int m=(tree[root].l+tree[root].r)/2;
    if(x<=m) return query(x,root*2)+tree[root].val;
    else return query(x,root*2+1)+tree[root].val;
}
int level[32001];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int i,n,x,y;
    scanf("%d",&n);
    create(0,32000,1);
    for(i=0;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        ++level[query(x,1)];
        update(x,32000,1,1);
    }
    for(i=0;i<n;i++)
        printf("%d\n",level[i]);
}

 

评论(1) 阅读(2833)

poj 2250 输出LCS

2010年11月22日 05:45

求LCS(longest common subsequence),并输出.

这个输出自己写的还是很geilivable的啊!

#include <cstdio>
#include <cstring>
char s1[100][31];
char s2[100][31];
int d[101][101];
int stack[100];

int inline max(int a,int b){if(a>b) return a;else return b;}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int i,j,t,n1,n2,maxd;
    while(scanf("%s",s1[0])!=EOF)
    {
        n1=1;
        while(scanf("%s",s1[n1]),s1[n1][0]!='#')
            n1++;
        n2=0;
        while(scanf("%s",s2[n2]),s2[n2][0]!='#')
            n2++;
        maxd=0;
        for(i=0;i<=n1;i++)
            for(j=0;j<=n2;j++)
            {
                if(i==0||j==0) 
                    d[i][j]=0;
                else if(!strcmp(s1[i-1],s2[j-1]))
                    d[i][j]=d[i-1][j-1]+1;
                else
                    d[i][j]=max(d[i-1][j],d[i][j-1]);
                maxd=max(maxd,d[i][j]);
            }
        i=n1;j=n2;
        t=0;
        while(d[i][j])
        {
            if(!strcmp(s1[i-1],s2[j-1]))
            {
                stack[t++]=i-1;
                i--;j--;
            }else if(d[i-1][j]>d[i][j-1])
                --i;
            else --j;
        }
        while(t>1)
            printf("%s ",s1[stack[--t]]);
        printf("%s\n",s1[stack[0]]);
    }
}

 

评论(0) 阅读(1460)

poj 1509 最小表示法

2010年11月20日 18:36

最小表示法即寻找使循环串最小字典序的起始位置.

详见周源的ppthttp://www.chhaya.me/?p=229.

基本上就是两个指针i=0,j=1.从s[i]和s[j]开始比较第k个字符是否相同,当k==len时,返回i,j中的最小值.当s[i+k]和s[j+k]不相同时,若s[i+k]>s[j+k]则可见从s[i+1]到s[i+k]都不会是最小字典序的起始位置,所以i=i+k+1.当s[i+k]<s[j+k]时同理.若移动后i==j则使正在移动的那个指针++.然后从新的s[i]和s[j]开始比较.

#include <cstdio>
#include <cstring>

int mins(const char *s)
{
    int len=strlen(s);
    if(len==0||len==1) return 0;
    int i=0,j=1,k;
    char ci,cj;
    do
    {
        for(k=0;k<len;k++)
        {
            ci=s[(i+k)%len];
            cj=s[(j+k)%len];
            if(ci!=cj) break;
        }
        if(k==len) break;
        else if(ci>cj) 
        {
            i=i+k+1;
            if(i==j) i++;
        }
        else 
        {
            j=j+k+1;
            if(j==i) j++;
        }
    }while(1);
    return i<j?i:j;
}

char s[10001];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int cas;scanf("%d",&cas);
    while(cas--)
    {
        scanf("%s",s);
        printf("%d\n",mins(s)+1);
    }
}

 

评论(0) 阅读(2846)

poj 3189 二分+多重匹配

2010年11月08日 03:42

http://www.cublog.cn/u3/113538/showart_2212681.html

http://hi.baidu.com/scaneelingg/blog/item/a639111e08b98ac2a7866992.html

总是想不到二分.学到了多重匹配,X中一个点可以匹配Y中多个点,但Y中的点只能匹配一个X中的点.做法貌似是匈牙利算法的变种.也可以用最大流来做多重匹配,每一个X中的点连S,容量为1,每一个牛棚连T,容量为牛棚容量,XY之间按二分上下限连,但效率貌似要低.

#include <cstdio>
#include <cstring>

#define maxn 1001
#define maxm 21
int n,m;
//bool map[maxn][maxm];
int map[maxn][maxm];
int match[maxm][maxn];
bool v[maxm];
int cap[maxm];

int c[maxm];
int l,r;

int dfs(int p)
{
    int i,j;
    for(i=1;i<=m;i++)
        //if(map[p][i] && !v[i])
        if(l<=map[p][i] && map[p][i]<=r && !v[i])
        {
            v[i]=1;
            if(cap[i])
            {
                --cap[i];
                match[i][ ++match[i][0] ]=p;
                return 1;
            }
            else
            {
                for(j=1;j<=match[i][0];j++)
                    if(dfs(match[i][j]))
                    {
                        match[i][j]=p;
                        return 1;
                    }
            }
        }
    return 0;
}

int maxmatch()
{
    int i,ans=0;
    for(i=1;i<=m;i++)
        match[i][0]=0;
    for(i=1;i<=n;i++)
    {
        memset(v,false,sizeof(v));
        ans+=dfs(i);
    }
    return ans;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int i,j,N,B,b;scanf("%d%d",&N,&B);
    for(i=1;i<=N;i++)
        for(j=1;j<=B;j++)
        {
            scanf("%d",&b);
            map[i][b]=j;
        }

    for(j=1;j<=B;j++)
        scanf("%d",&c[j]);

    l=r=1;
    int ans=B+1;
    while(l<=r && r<=B)
    {
        for(i=1;i<=B;i++) cap[i]=c[i];
        n=N;m=B;
        if(maxmatch()==N)
        {
            if(ans>r-l+1) ans=r-l+1;
            ++l;
        } else ++r;
    }
    printf("%d\n",ans);
}

话说从上次回来后就很久没做了,一直在忙落下的作业和实验,要坚持啊.

评论(0) 阅读(2009)