二分查找第一次出现的位置

2011年3月17日 15:58

这个简单的问题以前居然没有想过,今天看书才发现二分也是可以做的,顺便用刚学的random库验证一下

# coding: utf-8
from random import *

def first(a,x):
    try:
        return a.index(x)
    except ValueError:
        return -1

def firstbin(a,x):
    l=0; u=len(a)-1
    while True:
        if l>u:
            return -1
        m=(l+u)/2
        if a[l]==x:
            return l
        elif a[m]<x:
            l=m+1
        elif a[m]==x:
            u=m
        elif a[m]>x:
            u=m-1

if __name__ == '__main__':
    cishu=1
    while True:
        a=[]
        for i in range(randint(1,10)):
            a.extend(range(100))
        a=sample(a,randint(0,len(a)))
        a.sort()
        x=randint(0,99)
        print cishu,
        cishu+=1
        if first(a,x)==firstbin(a,x):
            print 'OK'
            #print x,a
        else:
            print 'OOH!'
            print a,x
            break

update:

编程珠玑(中文第2版)88-90页上给出的另两种:

def binsearch(a,x):
    l=-1;u=len(a)
    while l+1!=u:
        # invariant: x[l]<t && x[u]>=t && l<u
        m=(l+u)/2
        if a[m]<x:
            l=m
        else:
            u=m
    # assert: l+1=u && x[l]<t && x[u]>=t
    p=u
    if p>=len(a) or a[p]!=x:
        p=-1
    return p

def binsearch(a,x):
    if len(a)==0:
        return -1
    i=max1(len(a))
    print len(a),i
    l=-1
    if a[i-1]<x:
        l=len(a)-i
    while i!=1:
        # invariant: x[l]<t && x[l+i]>=t && i=2^j
        i=i/2
        if a[l+i]<x:
            l=l+i
    # assert: i==1 && x[l]<t && x[l+i]>=t
    p=l+1
    print p
    if p>=len(a) or a[p]!=x:
        p=-1
    return p

循环不变式 断言 和 脚手架是好东西

书上说第二个的循环展开非常经典高效

评论(0) 阅读(1990)

A*算法寻路演示

2011年2月25日 10:14

环境为win下的 python 2.7 + pygame 1.9.2 pre

网上看到牛人做的,也自己学了学pygame做了个,现学的最简单的A*算法,未考虑神马穿越拐角规则,总之就是渣代码,打开后点一下确定起点,再点一下确定终点,然后拖动确定墙的位置,最后按一下空格看到结果

至少效果还可以 :)

code

评论(0) 阅读(2687)

poj 1436

2010年12月25日 17:14

每三条在水平上可以互相望见的竖线段可以组成一个三角形,求三角形总数.

开始看完题目后觉得不难写,扫描线,更改前查询.写完对照例子发现无论是把节点作为点还是线段,总是会有疏忽的情况,样例果然强大阿.才终于领悟大牛博客上说的纵坐标*2会简单,看来是奇数点可以保存线段的颜色信息,这样节点作为点就没问题了.

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define maxn 8000
#define lcd root<<1
#define rcd root<<1|1
vector<int> con[maxn];
int last[maxn];
struct seg 
{
    int x,y1,y2;
    bool operator < (const seg &s) const
    {return x<s.x;}
} s[maxn];
struct node
{
    int l,r,id;
    int mid(){return (l+r)>>1;}
}tree[16000*3];
void build(int l,int r,int root)
{
    tree[root].l=l;
    tree[root].r=r;
    tree[root].id=-1;//-1:none -2:mix
    if(l==r) return;
    int m=(l+r)>>1;
    build(l,m,lcd);
    build(m+1,r,rcd);
}
void down(int root)
{
    if(tree[root].id!=-2)
    {
        tree[lcd].id=tree[rcd].id=tree[root].id;
        tree[root].id=-2;
    }
}
void update(int l,int r,int id,int root)
{
    if(tree[root].l==l && tree[root].r==r)
    {
        tree[root].id=id;
        return;
    }
    if(tree[root].l==tree[root].r) return;
    down(root);
    int m=tree[root].mid();
    if(r<=m) update(l,r,id,lcd);
    else if(l>m) update(l,r,id,rcd);
    else
        update(l,m,id,lcd),update(m+1,r,id,rcd);
}
void query(int l,int r,int id,int root)
{
    if(tree[root].id!=-2)
    {
        int id2=tree[root].id;
        if(id2!=-1) if(last[id2]!=id)
        {
            con[id].push_back(id2);
            last[id2]=id;
        }
        return;
    }
    if(tree[root].l==tree[root].r) return;
    down(root);
    int m=tree[root].mid();
    if(r<=m) query(l,r,id,lcd);
    else if(l>m) query(l,r,id,rcd);
    else
        query(l,m,id,lcd),query(m+1,r,id,rcd);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int n,cas;scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d%d%d",&s[i].y1,&s[i].y2,&s[i].x);
            s[i].y1<<=1; s[i].y2<<=1;
        }
        sort(s,s+n);
        build(0,16000,1);
        for(int i=0;i<n;i++) con[i].clear();
        memset(last,-1,sizeof(last));
        for(int i=0;i<n;i++)
        {
            if(i) query(s[i].y1,s[i].y2,i,1);
            update(s[i].y1,s[i].y2,i,1);
        }
        int ans=0;
        for(int i=0;i<n;i++)
            for(int l=0;l<con[i].size();l++)
            {
                int j=con[i][l];
                for(int l2=0;l2<con[i].size();l2++)
                {
                    int k=con[i][l2];
                    if(k>j) for(int l3=0;l3<con[k].size();l3++)
                        if(con[k][l3]==j) 
                            ++ans;
                }
            }
        printf("%d\n",ans);
    }
}

 

评论(0) 阅读(2915)

poj 3667 Hotel 经典线段树

2010年12月19日 06:00

经典的线段树应用,寻找最左的k个连续的空房间, 批量入住, 批量退房.

需要保存每个节点的lv(最大左连续数), rv(最大右连续数), cv(最大连续数), col(颜色, lazy-tag用, 0为空, 1为满, -1为混合).

查询时利用lv,cv,rv, 先看左子树, 再看中间, 再看右子树, 反正就这三种情况. 查子区间前down下去col.

更新时批量改变区间的col, 需要更新子区间的话, 先down下去col, 更新完子区间再up上来lv,rv,cv.

ref: http://hi.baidu.com/legend_ni/blog/item/4d757b2ca91da9ece6cd40c2.html

#include<cstdlib>

int inline max(int a,int b) {return a>b?a:b;}
#define MAX 100000
#define lcd root<<1
#define rcd root<<1|1
struct Node 
{
    int l,r,lv,cv,rv,col;//col -1:mix 0:empty 1:full
    int len(){return r-l+1;}
    int mid(){return (l+r)>>1;}
    void doit(){lv=cv=rv=col?0:len();}//if empty or full, update lv,cv,rv
} 
tree[MAX<<2];

void build(int root,int l,int r)
{
    tree[root].l=l; tree[root].r=r;
    tree[root].col=-1;
    tree[root].lv=tree[root].cv=tree[root].rv=tree[root].len();
    if(l==r) return;
    int m=(l+r)>>1;
    build(lcd,l ,m);
    build(rcd,m+1,r);
}

void down(int root)
{
    if(tree[root].len()==1 || tree[root].col==-1) return;
    tree[lcd].col=tree[rcd].col=tree[root].col;
    tree[root].col=-1;
    tree[lcd].doit(); tree[rcd].doit();
}

void up(int root)
{
    tree[root].cv=max(tree[lcd].rv+tree[rcd].lv,
            max(tree[lcd].cv,tree[rcd].cv));
    tree[root].lv=(tree[lcd].cv==tree[lcd].len())?
        tree[lcd].len()+tree[rcd].lv:tree[lcd].lv;
    tree[root].rv=(tree[rcd].cv==tree[rcd].len())?
        tree[rcd].len()+tree[lcd].rv:tree[rcd].rv;
}

int query(int root,int k)
{
    if(tree[root].len()==1) return k==1;
    down(root);
    if(tree[lcd].cv>=k) return query(lcd,k);
    if(tree[lcd].rv+tree[rcd].lv>=k)
        return tree[lcd].r-tree[lcd].rv+1;
    if(tree[rcd].cv>=k) return query(rcd,k);
    return 0;
}

void update(int root,int l,int r,int col)
{
    if(tree[root].l==l && tree[root].r==r)
    {
        tree[root].col=col;
        tree[root].doit();
        return;
    }
    down(root);
    int m=tree[root].mid();
    if(r<=m) update(lcd,l,r,col);
    else if(l>m) update(rcd,l,r,col);
    else update(lcd,l,m,col),update(rcd,m+1,r,col);
    up(root);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int n,m,a,b,c;
    scanf("%d%d",&n,&m);
    build(1,1,n);
    while(m--)
    {
        scanf("%d%d",&a,&b);
        if(a==1)
        {
            int s=query(1,b);
            printf("%d\n",s);
            if(s) update(1,s,s+b-1,1);
        }
        if(a==2) 
        {
            scanf("%d",&c);
            update(1,b,b+c-1,0);
        }
    }
}

 

评论(0) 阅读(4094)

poj 3277 线段树,离散化,扫描线

2010年12月15日 23:23

从昨晚上开始看,终于搞明白线段树怎么求面积并了.忘得快,得记.

对y轴上的坐标做离散化,在y轴上建立线段树.

对每一个矩阵的左右边,建立入边和出边,并记录在y轴上的投影.把所有的入边和出边排序,从左到右按x轴方向扫描,若扫到的是入边,则在线段树上对投影线段的val加1,若出边则减一.

边扫描,边统计和上一条边之间的扫过的面积,即x轴上的跨度乘y轴上测度(测度为在线段树上val>1的线段的总长度,不必连续).测度可以用线段树查询,也可以对线段增加一个属性,并在插入过程中动态的计算,对查询量多的情况如poj3695更快.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef __int64  i64;
#define IN false
#define OUT true
i64 q[40001],top;
struct edge
{
    i64 x,y1,y2;
    bool type;
    void init(i64 a,i64 h,bool t)
    { x=a,y1=0;y2=h;type=t; }
} e[80000]; int tot;

bool cmp(const edge& e1,const edge& e2)
{
    return e1.x<e2.x;
}

struct node { int l,r,val; } tree[80000*3];

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

void update(int l,int r,int root,int val)
{
    if(l==tree[root].l && tree[root].r==r)
        tree[root].val+=val;
    else if(tree[root].l<tree[root].r-1)
    {
        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,r,root*2+1,val);
        }
    }
}
i64 query(int root)
{
    if(tree[root].val>0)
        return q[tree[root].r]-q[tree[root].l];
    else if(tree[root].l<tree[root].r-1)
        return query(root*2) + query(root*2+1);
    return 0;
}
int rank(i64 y)//二分离散化后的位置
{
    int l=0,r=top-1,m;
    while(l<=r)
    {
        m=(l+r)>>1;
        if(q[m]==y) return m;
        else if(q[m]>y) r=m-1;
        else l=m+1;
    }
}
i64 a[40000],b[40000],h[40000];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int i,j,n;
    i64 ans;
    scanf("%d",&n);
    q[0]=0;top=1;
    for(i=0,tot=0;i<n;i++)
    {
        scanf("%I64d%I64d%I64d",a+i,b+i,h+i);
        q[top++]=h[i];
    }
    //离散化
    sort(q,q+top);
    for(i=1,j=1;i<top;i++)
        if(q[i]!=q[i-1])//去重复
            q[j++]=q[i];
    top=j;
    for(i=0;i<n;i++)
    {
        h[i]=rank(h[i]);//离散化后的值
        e[tot++].init(a[i],h[i],IN);//入边
        e[tot++].init(b[i],h[i],OUT);//出边
    }

    create(0,top-1,1);
    sort(e,e+2*n,cmp);//对所有入边出边排序
    for(ans=0,i=0;i<2*n;i++)//扫描
    {
        if(i)
            ans+=(e[i].x-e[i-1].x)*query(1);
        if(e[i].type==IN)
            update(e[i].y1,e[i].y2,1,1);
        else
            update(e[i].y1,e[i].y2,1,-1);
    }
    printf("%I64d\n",ans);
}

面积并也可以用容斥原理求,不过比线段树慢,这个是poj 3695的TLE的代码:

#include <cstdio>
struct rec
{
    int x1,y1,x2,y2,area;
    void cross(const rec &r)
    {
        if(r.x1>x1) x1=r.x1; if(r.y1>y1) y1=r.y1;
        if(r.x2<x2) x2=r.x2; if(r.y2<y2) y2=r.y2;
        if(x2<x1) x2=x1; if(y2<y1) y2=y1;
        area=(x2-x1)*(y2-y1);
    }
} r[22];
int cnt,q[22];
int cntone(int k)
{
    int ans=0;
    while(k)
    {
        if(k&1) ++ans;
        k>>=1;
    }
    return ans;
}
void solve()
{
    int i,j;rec tmp;
    int ans=0;
    for(i=1;i<(1<<cnt);i++)
    {
        tmp.y1=tmp.x1=-10000;tmp.y2=tmp.x2=10000;
        for(j=1;j<=cnt;j++)
        {
            if(i&(1<<(j-1)))
                tmp.cross(r[q[j]]);
            if(tmp.area==0) break;
        }

        if(cntone(i)&1)
            ans+=tmp.area;
        else
            ans-=tmp.area;
    }
    printf("%d\n",ans);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int i,j,n,m,cas=1;
    while(scanf("%d%d",&n,&m),(n+m))
    {
        printf("Case %d:\n",cas++);
        for(i=1;i<=n;i++)
            scanf("%d%d%d%d",&r[i].x1,&r[i].y1,&r[i].x2,&r[i].y2);

        for(i=1;i<=m;i++)
        {
            printf("Query %d: ",i);
            scanf("%d",&cnt);
            for(j=1;j<=cnt;j++) scanf("%d",q+j);
            solve();
        }
    }
}

 

评论(1) 阅读(4208)