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) 阅读(2711)

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) 阅读(2677)

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) 阅读(1342)

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) 阅读(2700)

linux下使用xlib模拟鼠标移动和点击

2010年11月11日 20:36

/* ref: http://www.ishiboo.com/~danny/Projects/xwarppointer/ */
#include <stdio.h>
#include <string.h>
//头文件
#include <unistd.h>
#include <X11/X.h>
#include <X11/Xlib.h>
#include <X11/Xutil.h>
//全局变量
Display *display;
Window root;
//初始化
void init()
{
    if ((display = XOpenDisplay(NULL)) == NULL) {
        fprintf(stderr, "Cannot open local X-display.\n");
        return;
    }
    root = DefaultRootWindow(display);
}
//得到坐标
void GetCursorPos(int &x,int &y)
{
    int tmp;unsigned int tmp2;
    Window fromroot, tmpwin;
    XQueryPointer(display, root, &fromroot, &tmpwin, &x, &y, &tmp, &tmp, &tmp2);
}
//设置坐标
void SetCursorPos(int x,int y)
{
    int tmp;
    XWarpPointer(display, None, root, 0, 0, 0, 0, x, y);
    XFlush(display);
}

//模拟点击
/* http://www.linuxquestions.org/questions/programming-9/simulating-a-mouse-click-594576/ */
void mouseClick(int button)
{
    Display *display = XOpenDisplay(NULL);

    XEvent event;

    if(display == NULL)
    {
        printf("Errore nell'apertura del Display !!!\n");
        return;
    }

    memset(&event, 0x00, sizeof(event));

    event.type = ButtonPress;
    event.xbutton.button = button;
    event.xbutton.same_screen = True;

    XQueryPointer(display, RootWindow(display, DefaultScreen(display)), &event.xbutton.root, &event.xbutton.window, &event.xbutton.x_root, &event.xbutton.y_root, &event.xbutton.x, &event.xbutton.y, &event.xbutton.state);

    event.xbutton.subwindow = event.xbutton.window;

    while(event.xbutton.subwindow)
    {
        event.xbutton.window = event.xbutton.subwindow;

        XQueryPointer(display, event.xbutton.window, &event.xbutton.root, &event.xbutton.subwindow, &event.xbutton.x_root, &event.xbutton.y_root, &event.xbutton.x, &event.xbutton.y, &event.xbutton.state);
    }

    if(XSendEvent(display, PointerWindow, True, 0xfff, &event) == 0) printf("Errore nell'invio dell'evento !!!\n");

    XFlush(display);

    usleep(100000);

    event.type = ButtonRelease;
    event.xbutton.state = 0x100;

    if(XSendEvent(display, PointerWindow, True, 0xfff, &event) == 0) printf("Errore nell'invio dell'evento !!!\n");

    XFlush(display);

    XCloseDisplay(display);
}
int main()
{
    init();
    int x,y;
    GetCursorPos(x,y);
    printf("%d %d\n",x,y);
    SetCursorPos(0,0);
    XCloseDisplay(display);
    mouseClick(Button1);
    return 0;
}

 

评论(0) 阅读(5220)