poj 2104 2761 树状数据结构

2011年10月07日 00:51

两道题都是裸裸的求区间第k大数(kth number),先给出总的区间,每个查询给出小区间[l,r]和k。
用这两道题学习了不少数据结构,感觉有些非常巧妙,记录一下。

1 平衡树

平衡树就是平衡的二叉搜索树(BST),对每个区间建立平衡树并维护size域(以此节点为根的树的节点数),便可很容易的实现select(找第k大数)和rank(查某数是第几大)两个操作。因为要反复针对区间建树,所以先对区间排好序会比较好,这样后一个区间的树就是对前一个区间的树的增删操作了。

1.1 Treap
Tree就是Tree(BST)+Heap。 首先要满足BST的性质,节点的key要左小于中小于右。然后每个节点加上了一个附加域fix,这个域没什么意义,就是个随机数,但是需要保持树上的这个域符合堆的性质,比如最小堆,中小于左右。 怎么能又保持BST又保持Heap呢?这就要靠一个神奇的BST的操作了!BST中的左旋和右旋是不会破坏BST的性质的!于是先保证树是BST,再用左旋和右旋把整棵树调整成Heap。于是就可以看到添加节点时,先加到最下面,然后,扭啊扭啊扭上去,删除时把节点扭啊扭啊扭下去再删掉~ 显然,fix和堆的存在就是为了搅乱整棵树的,这样就不会对特定的数据恶化了。而且扭的过程中还可以降低树的高度,所以Treap是随机平衡的树,各操作均摊复杂度才是O(nlogn),不像AVL和红黑树那样是近似绝对平衡的树。但是Treap编程难度低啊,所以很好用,我觉得,这个把BST和Heap结合起来的扭来扭去的树和Dancing links一样优美~ 对size域的维护放到旋转时就可以了。具体资料可见《随机平衡二叉查找树 Treap 的分析与应用 by 郭家宝》。

#include <cstdio>
#include <cstdlib>

#define nil 0
#define MAX 1000010
int key[MAX],left[MAX],right[MAX],size[MAX],fix[MAX];
int root,node;

inline void Left_Rotate(int &x) {
    int k = right[x];
    right[x] = left[k];
    left[k] = x;
    size[k] = size[x];
    size[x] = size[left[x]] + size[right[x]] + 1;
    x = k;
}

inline void Right_Rotate(int &y) {
    int k = left[y];
    left[y] = right[k];
    right[k] = y;
    size[k] = size[y];
    size[y] = size[left[y]] + size[right[y]] + 1;
    y = k;
}

void Insert(int &T,int v) {
    if(T == nil) {
        key[T = ++node]= v;
        fix[T]=rand(); size[T]=1;
    } else {
        size[T]++;
        if(v < key[T]) {
            Insert(left[T], v);
            if(fix[left[T]]<fix[T])
                Right_Rotate(T);
        } else {
            Insert(right[T], v);
            if(fix[right[T]]<fix[T])
                Left_Rotate(T);
        }
    }
}

void Delete(int &T,int v) {
    if(!T) return;
    size[T]--;
    if(v == key[T]){
        if(!left[T] || !right[T])
            T=left[T]+right[T];
        else if(fix[left[T]]<fix[right[T]]) {
            Right_Rotate(T);
            Delete(right[T],v);
        } else {
            Left_Rotate(T);
            Delete(left[T],v);
        }
    } else if (v < key[T])
        Delete(left[T],v);
    else
        Delete(right[T],v);
}

int Select(int &T,int k)
{
    int r = size[left[T]] + 1;
    if(k == r)
        return key[T];
    else if(k < r)
        return Select(left[T], k);
    else
        return Select(right[T], k - r);
}

int arr[100010];
typedef struct {int l,r,k,org;} Q;
Q q[50010];
int ans[50010];

int cmp(const void *a,const void *b)
{
    Q *qa=(Q*)a,*qb=(Q*)b;
    if(qa->l!=qb->l) return qa->l-qb->l;
    else return qa->r-qb->r;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    //init
    //srand(1984);
    root=0;
    int n,m; scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",arr+i);
    for(int i=1;i<=m;i++)
    {
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        q[i].l=l; q[i].r=r; q[i].k=k; q[i].org=i;
    }
    qsort(q+1,m,sizeof(Q),cmp);
    int lastl=1,lastr=0;
    for(int t=1;t<=m;t++)
    {
        int l=q[t].l,r=q[t].r,k=q[t].k;
        if(lastr<l)
        {
            for(int i=lastl;i<=lastr;i++)
                Delete(root,arr[i]);
            for(int i=l;i<=r;i++)
                Insert(root,arr[i]);
        }
        else if(lastr<=r)
        {
            for(int i=lastl;i<l;i++)
                Delete(root,arr[i]);
            for(int i=lastr+1;i<=r;i++)
                Insert(root,arr[i]);
        }
        else
        {
            for(int i=lastl;i<l;i++)
                Delete(root,arr[i]);
            for(int i=r+1;i<=lastr;i++)
                Delete(root,arr[i]);
        }
        lastl=l;lastr=r;
        ans[q[t].org]=Select(root,k);
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    
}


1.2 Splay
Splay和Treap很像,也是扭来扭去的。Splay树的独特之处就是splay操作,把某一个节点扭到root处,在扭的过程中同样可以搅乱整棵树,降低树高。Splay操作也仅仅是用单旋和双旋两种操作,应对节点和节点父亲及节点的父亲的父亲之间的多种情况,快速的把节点向上提升。 Splay树中的插入操作是在普通BST插入操作后,把插入节点splay到根。删除操作有多种实现,我是先把要删除节点splay到根,再把左子树中最大的节点splay到根,然后,其右节点即为要删除的节点,而此时他只有右子树了,所以很容易就删除了。Splay也是随机的平衡树,可以证明的是splay操作均摊复杂度为O(1),所以各操作的均摊复杂度为O(nlogn)了。size域的维护在单旋和删除操作时维护即可。资料参见《伸展树的基本操作与应用 by 杨思雨》、《伸展树操作详解  By Ma Shuo》和《The Magical Splay by sqybi》。

#include <cstdio>
#include <cstdlib>

struct Node 
{
    Node *pre,*ch[2]; int size,key;
    Node(){pre=ch[0]=ch[1]=NULL;size=1;}
} node[1000100];
int tot=0;
Node *root;

void print(Node *x)
{
    if(!x) return;
    print(x->ch[0]);
    printf("%d ",x->key);
    print(x->ch[1]);
}

void Rotate(Node *x)
{
    bool c=(x->pre->ch[0]==x);//0:left(zag) 1:right(zig)
    Node *y=x->pre; 
    y->ch[!c]=x->ch[c];
    if(x->ch[c]!=NULL) x->ch[c]->pre=y; 
    x->pre = y->pre; 
    if(y->pre!=NULL) 
        y->pre->ch[y->pre->ch[0]!=y]=x; 
    x->ch[c]=y; y->pre=x; 
    x->size=y->size; y->size=1;
    for(int i=0;i<2;i++)
        if(y->ch[i]) y->size+=y->ch[i]->size;
    if(y==root) root=x;
}

// up x until x->pre = f, f==NULL means root 
void Splay(Node *x,Node *f=NULL)
{
    while(x->pre!=f)
        if(x->pre->pre==f)
            Rotate(x);
        else
        {
            Node *y=x->pre,*z=y->pre;
            if((z->ch[0]==y)==(y->ch[0]==x))
                    Rotate(y), Rotate(x);
                else
                    Rotate(x), Rotate(x);
        }
    if(f==NULL) root=x;
}

Node* Search(Node *x,int k)//return the last found
{
    if(!x) return NULL;
    while(k != x->key)
    {
        bool c=(k > x->key);
        if(x->ch[c]==NULL) break;
        x=x->ch[c];
    }
    return x;
}

void Insert(int k)
{
    Node *x=root,*y=NULL;
    while(x)// && k != x->key)
    {
        x->size++;
        y=x; x=x->ch[k > x->key];
    }
    Node *z=&node[tot++]; z->key=k;
    z->pre=y;
    if(y==NULL)
        root=z;
    else
        y->ch[k > y->key]=z;
    Splay(z);
}

Node* Extreme(Node *x,bool c)
{
    while(x && x->ch[c]!=NULL)
        x=x->ch[c];
    return x;
}

bool Delete(int k)
{
    Node *x=Search(root,k);
    if(!x || x->key!=k) return false;
    Splay(x);//make x the root
    if(!x->ch[0] || !x->ch[1])// one or none child
    {
        bool c=(x->ch[0])?0:1;
        if(x->ch[c]) x->ch[c]->pre=NULL;
        root=x->ch[c];
    }
    else //combine x's childs
    {
        Node *l=x->ch[0],*r=x->ch[1];
        Splay(Extreme(l,1));
        root->ch[1]=r; r->pre=root;
        root->size--;
    }
    //delete(x);
    return true;
}

int Select(Node *x,int k)
{
    int r=1+((x->ch[0])?x->ch[0]->size:0);
    if(k==r)
        return x->key;
    else if(k < r)
        return Select(x->ch[0],k);
    else
        return Select(x->ch[1],k-r);
}


int arr[1000500];
struct Q{int l,r,k,org;} q[50050];
int ans[50050];

int cmp(const void *a,const void *b)
{
    Q *qa=(Q*)a,*qb=(Q*)b;
    if(qa->l!=qb->l) return qa->l-qb->l;
    else return qa->r-qb->r;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int n,m; scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",arr+i);
    for(int i=1;i<=m;i++)
    {
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        q[i].l=l; q[i].r=r; q[i].k=k; q[i].org=i;
    }
    qsort(q+1,m,sizeof(Q),cmp);
    int lastl=1,lastr=0;
    for(int t=1;t<=m;t++)
    {
        int l=q[t].l,r=q[t].r,k=q[t].k;
        if(lastr<l)
        {
            for(int i=lastl;i<=lastr;i++)
                Delete(arr[i]);
            for(int i=l;i<=r;i++)
                Insert(arr[i]);
        }
        else if(lastr<r)
        {
            for(int i=lastl;i<l;i++)
                Delete(arr[i]);
            for(int i=lastr+1;i<=r;i++)
                Insert(arr[i]);
        }
        else
        {
            for(int i=lastl;i<l;i++)
                Delete(arr[i]);
            for(int i=r+1;i<=lastr;i++)
                Delete(arr[i]);
        }
        lastl=l;lastr=r;
        ans[q[t].org]=Select(root,k);
        //printf("l:%d r:%d k:%d :: ",l,r,k);
        //print(root);puts("");
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
}

1.3 SBT(Size Balanced Tree)
名字大亮,"傻叉树" or "Super BT"树。如其本名,是直接用size域实现近似绝对平衡的树。较复杂,不介绍了,参见《Size Balanced Tree by Chen Qifeng(此树作者)》、《由二叉查找树到容均树 by 田劲锋》(写的大好啊,我就是用这个里面的代码做模板的)。

#include <cstdio>
#include <cstdlib>

int arr[100010];
typedef struct {int l,r,k,org;} Q;
Q q[50100];
int ans[50100];

#define nil 0
const int MAX = 100010;
int key[MAX], left[MAX], right[MAX], size[MAX];
int T, node;
int record; // This is used for the commented Delete
inline void Left_Rotate(int &x) {
    int k = right[x];
    right[x] = left[k];
    left[k] = x;
    size[k] = size[x];
    size[x] = size[left[x]] + size[right[x]] + 1;
    x = k;
}
inline void Right_Rotate(int &y) {
    int k = left[y];
    left[y] = right[k];
    right[k] = y;
    size[k] = size[y];
    size[y] = size[left[y]] + size[right[y]] + 1;
    y = k;
}
void Maintain(int &T, bool flag);
void Insert(int &T, int v) {
    if(T == nil) {
        key[T = ++node] = v;
        size[T] = 1;
    } else {
        size[T]++;
        if(v < key[T])
            Insert(left[T], v);
        else
            Insert(right[T], v);
        Maintain(T, v >= key[T]);
    }
}
int Delete(int &T, int v) {
    size[T]--;
    if( (v == key[T]) || (v < key[T] && left[T] == nil) || (v > key
                [T] && right[T] == nil) ) {
        int r = key[T];
        if(left[T] == nil || right[T] == nil)
            T = left[T] + right[T];
        else
            key[T] = Delete(left[T], key[T] + 1);
        return r;
    } else {
        if(v < key[T])
            return Delete(left[T], v);
        else
            return Delete(right[T], v);
    }
}
void Maintain(int &T, bool flag) {
    if(flag == false) {
        if(size[left[left[T]]] > size[right[T]])
            Right_Rotate(T);
        else {
            if(size[right[left[T]]] > size[right[T]]) {
                Left_Rotate(left[T]);
                Right_Rotate(T);
            } else return;
        }
    } else {
        if(size[right[right[T]]] > size[left[T]])
            Left_Rotate(T);
        else {
            if(size[left[right[T]]] > size[left[T]]) {
                Right_Rotate(right[T]);
                Left_Rotate(T);
            } else return;
        }
    }
    Maintain(left[T], false);
    Maintain(right[T], true);
    Maintain(T, true);
    Maintain(T, false);
}
int Select(int T, int k) {
    int r = size[left[T]] + 1;
    if(k == r)
        return key[T];
    else if(k < r)
        return Select(left[T], k);
    else
        return Select(right[T], k - r);
}
int cmp(const void *a,const void *b)
{
    Q *qa=(Q*)a,*qb=(Q*)b;
    if(qa->l!=qb->l) return qa->l-qb->l;
    else return qa->r-qb->r;
}
int main() 
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int n,m,lastl=1,lastr=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",arr+i);
    //sort query
    for(int i=1;i<=m;i++)
    {
        int l,r,k; scanf("%d%d%d",&l,&r,&k);
        q[i].l=l; q[i].r=r; q[i].k=k; q[i].org=i;
    }
    qsort(q+1,m,sizeof(Q),cmp);
    //do
    for(int t=1;t<=m;t++)
    {
        int l=q[t].l,r=q[t].r,k=q[t].k;
        if(lastr<l)
        {
            for(int i=lastl;i<=lastr;i++)
                Delete(T,arr[i]);
            for(int i=l;i<=r;i++)
                Insert(T,arr[i]);
        }
        else if(lastr<=r)
        {
            for(int i=lastl;i<l;i++)
                Delete(T,arr[i]);
            for(int i=lastr+1;i<=r;i++)
                Insert(T,arr[i]);
        }
        else
        {
            for(int i=lastl;i<l;i++)
                Delete(T,arr[i]);
            for(int i=r+1;i<=lastr;i++)
                Delete(T,arr[i]);
        }
        lastl=l;lastr=r;
        ans[q[t].org]=Select(T,k);
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
}

2 线段树

wr大牛说线段树也是一种平衡树,不过至少在这个问题的应用上还是有很大区别的。线段树的解法不再是构造每个查询区间的树了,而是构造好整个区间的(线段)树,再从上到下查询。

2.1 划分树
据说是专门用来解决kth number问题的。划分树的原理基于快排,线段树的每一层都是快排的一级,最上层就是整个数组,从上往下建立。为了保持绝对平衡,使用中位数做支点,左右平均,所以左右两边可能有相同的元素,在建树时要注意。建树时同时建立好num_left数组,记录每个线段树节点的区间中,在其左侧小于等于某元素的元素数。整个查找过程是从上到下分析num_left并选择向左还是向右的过程。具体参见这里

#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define max 1000010

struct Tree { int l,r; } tree[max*3];
int leftsum[30][max],seg[30][max],arr[max];

void parti_build(int r,int s,int t,int d)
{
    tree[r].l=s;tree[r].r=t;
    if(t==s) return;
    int mid=(s+t)>>1;
    int lsame=mid-s+1;
    for(int i=s;i<=t;i++)
        if(seg[d][i]<arr[mid])
            lsame--;
    int lpos=s,rpos=mid+1;
    for(int i=s;i<=t;i++)
    {
        leftsum[d][i] = (i==s)?0:leftsum[d][i-1];
        if(seg[d][i]<arr[mid])
        {
            leftsum[d][i]++;
            seg[d+1][lpos++]=seg[d][i];
        }
        else if(seg[d][i]>arr[mid])
            seg[d+1][rpos++]=seg[d][i];
        else
        {
            if(lsame)
            {
                lsame--; leftsum[d][i]++;
                seg[d+1][lpos++]=seg[d][i];
            }
            else
                seg[d+1][rpos++]=seg[d][i];
        }
    }
    parti_build(r*2,s,mid,d+1);
    parti_build(r*2+1,mid+1,t,d+1);
}

int find(int r,int s,int t,int d,int k)
{
    int tl=tree[r].l,tr=tree[r].r;
    if(tr==tl) return seg[d][s];
    int s_left_sum=(s==tl)?0:leftsum[d][s-1];
    int s_to_t_sum=leftsum[d][t]-s_left_sum;
    if(s_to_t_sum >=k)
        return find(r*2,tl+s_left_sum,tl+leftsum[d][t]-1,d+1,k);
    else
    {
        int mid=(tl+tr)>>1;
        int s_right_sum=s-tl-s_left_sum;
        int s_to_t_r_sum=t-s+1-s_to_t_sum;
        return find(r*2+1,mid+s_right_sum+1,mid+s_right_sum+s_to_t_r_sum,d+1,k-s_to_t_sum);
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",arr+i);
        seg[1][i]=arr[i];
    }
    sort(arr+1,arr+1+n);
    parti_build(1,1,n,1);
    while(m--)
    {
        int s,t,k;
        scanf("%d%d%d",&s,&t,&k);
        printf("%d\n",find(1,s,t,1,k));

    }
}

2.2 归并树
和划分树不同,归并树用的是归并排序的思想,每一层都是归并排序的一级,从下到上构建,每一个节点区间内都是排好序的(和划分树不同)。线段树是用来查某数的rank的,比较典型的线段树查询操作,不用附加域,而是用二分的思想,因为节点区间内都是排好序的,注意因为有重复值的可能所以二分求的是区间内小于某数的数的个数。对每个查询的结果是用其在所给小区间rank值二分的,注意二分是求使rank值为k的最大的数,原因不太好想。介绍可看这里,代码可看这里

#include <cstdio>
#include <cstdlib>

#define MAX 1000010

struct Tree {int l,r,lev;} tree[MAX*3];
int seg[22][MAX];
int n,m;
int arr[MAX],max,min;

void build(int root,int lev,int l,int r)
{
    tree[root].l=l;tree[root].r=r;tree[root].lev=lev;
    if(l==r)
    {
        seg[lev][l]=arr[l];
        return;
    }
    
    int mid=(l+r)/2;
    build(root*2,lev+1,l,mid);
    build(root*2+1,lev+1,mid+1,r);

    int p=l,p1=l,p2=mid+1;
    while(p<=r)
    {
        if(p1>mid)
            seg[lev][p++]=seg[lev+1][p2++];
        else if(p2>r)
            seg[lev][p++]=seg[lev+1][p1++];
        else if(seg[lev+1][p1]<=seg[lev+1][p2])
            seg[lev][p++]=seg[lev+1][p1++];
        else
            seg[lev][p++]=seg[lev+1][p2++];
    }
}

//the count in a that a[i]<x
int count(int *a,int l,int r,int x)
{
    int m,orgl=l;
    if(a[l]>=x) return 0;
    else if(a[r]<x) return r-l+1;
    while(l+1<r) //assert: a[l]<x && x<=a[r]
    {
        m=(l+r)>>1;
        if(a[m]<x) l=m; else r=m;
    }
    return l-orgl+1;
}

int rank(int root,int l,int r,int x)
{
    if(tree[root].l==l && tree[root].r==r)
        return count(seg[tree[root].lev],l,r,x);

    int mid=(tree[root].l+tree[root].r)/2;

    if(r<=mid)
        return rank(root*2,l,r,x);
    else if(l>mid)
        return rank(root*2+1,l,r,x);
    else 
        return rank(root*2,l,mid,x)+
               rank(root*2+1,mid+1,r,x);
}

int query(int l,int r,int k)
{
    int s=seg[1][0],t=seg[1][n-1]+1,m;
    while(s+1<t) // [s,t) <= ans
    {
        m=(s+t)/2;
        int rk=rank(1,l,r,m)+1;
        if(rk>k) t=m;
        else s=m;
    }
    return s;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        scanf("%d",arr+i);
    build(1,1,0,n-1);
    int l,r,k;
    while(m--)
    {
        scanf("%d%d%d",&l,&r,&k);
        printf("%d\n",query(l-1,r-1,k));
    }
}

评论(0) 阅读(2733)

hdu 3663 精确覆盖 dlx

2011年9月19日 15:47

此文充数.去年哈尔滨的D,残念啊伤心.

一些城市,每个都有电厂,既为自己供电,同时又为直接相邻的城市供电,但是供电有时间限制,而且同一城市不能有两处供电来源.求一个方案.

现在来看还是比较清晰的精确覆盖,有了数独的经验就知道用行来记录结果,用列来避免碰撞,所以拿电厂和发电时间去匹配城市和天数.转化也还算好想,发电时间枚举区间即可,但是题目有个限制,最后方案中的每个电厂的发电时间不能是离散区间,所以要加几列碰撞,使得每个电厂只能选一个发电区间,还要加一个发电区间表示电厂不发电,这几个点不太好想.转化好最后套进模板就出来了(我的模板的行列都是从1开始的,所以我把城市号处理成从0开始的了).

#include<cstdio>
#include<algorithm>
using namespace std;
#include<cstdlib>
#include<cstring>

bool mm[60][60];
int dd[60][2];
int q[16][2],top;

#define MAX 0x7fffffff
#define MAXR 4000
#define MAXC 700
bool arr[MAXR][MAXC];
#define SIZE MAXR*MAXC
int L[SIZE], R[SIZE], U[SIZE], D[SIZE],
    Col[SIZE], Row[SIZE];//所在列 所在行
int S[MAXC]; //列元素数
int sel[MAXR],seln;//选择的行

struct Dancer
{
    void init(int height,int width)
    {
        int p, x, y, last;
        for (p = 1; p <= width; p++)
        {
            L[p] = p - 1; R[p] = p + 1;
            U[p] = D[p] = p;
            S[p] = 0;
        }
        p = width + 1;
        for (y = 1; y <= height; y++)
        {
            last = R[0] = L[0] = 0;
            for (x = 1; x <= width; x++)
            {
                if (arr[y][x] != 0)
                {
                    L[p] = last; R[last] = p;
                    U[p] = U[x]; D[p] = x; U[x] = D[U[x]] = p;
                    Row[p]=y; Col[p]=x;
 
                    S[x]++; last=p++;
                }
            }
            R[last] = R[0]; L[R[0]] = last;
        }
        R[width] = 0; L[0] = width; R[0] = 1;
        S[0] = MAX;
    }
  
    void remove(const int &c)
    {
        L[R[c]] = L[c]; R[L[c]] = R[c];
        for (int i = D[c]; i != c; i = D[i])
            for (int j = R[i]; j != i; j = R[j])
            {
                U[D[j]] = U[j];
                D[U[j]] = D[j];
                --S[Col[j]];
            }
    }
  
    void resume(const int &c)
    {
        for (int i = U[c]; i != c; i = U[i])
            for (int j = L[i]; j != i; j = L[j])
            {
                U[D[j]] = j;
                D[U[j]] = j;
                ++S[Col[j]];
            }
        L[R[c]] = c; R[L[c]] = c;
    }
  
    bool dance()
    {
        if (R[0] == 0) return true;
        int c=0, i, j;
        for (i = R[0]; i != 0; i = R[i])
            if (S[i] < S[c]) c = i;
        remove(c);
        for (i = D[c]; i != c; i = D[i])
        {
            for (j = R[i]; j != i; j = R[j])
                remove(Col[j]);
            sel[seln]=Row[i];
            seln++;
            if (dance()) return true;
            seln--;
            for (j = L[i]; j != i; j = L[j])
                resume(Col[j]);
        }
        resume(c); return false;
    }
} dc;
/////////////////////////////////////////////////////////////

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int n,m,d;
    while(scanf("%d%d%d",&n,&m,&d)!=EOF)
    {
        //all internals
        top=1;
        for(int i=1;i<=5;i++) for(int j=i;j<=5;j++)
            q[top][0]=i,q[top++][1]=j;
        
        memset(mm,false,sizeof(mm));
        for(int i=0;i<n;i++) mm[i][i]=1;
        for(int i=0;i<m;i++)
        {
            int a,b; scanf("%d%d",&a,&b);
            a--;b--;
            mm[a][b]=mm[b][a]=1;
        }
        
        for(int i=0;i<n;i++)
            scanf("%d%d",&dd[i][0],&dd[i][1]);
        //转化
        memset(arr,false,sizeof(arr));
        for(int i=0;i<n;i++)//each power station
        {
            for(int k=0;k<top;k++)//each internal
            {
                int r=i*top+k+1;//station i work on internal k
                arr[r][n*d+i+1]=1;//station collision
                int d1=q[k][0],d2=q[k][1];
                if(k==0) continue;//not work
                if(d1<dd[i][0] || d2>dd[i][1])//bad date
                    continue;
                for(int j=0;j<n;j++) if(mm[i][j])//each city
                    for(int di=d1;di<=d2;di++)
                    {
                        int c=j*d+di;
                        arr[r][c]=1;//soga
                    }
            }
        }
        //dance
        seln=0; dc.init(n*top,n*d+n);
        if(!dc.dance())
            puts("No solution");
        else
        {
            for(int i=0;i<seln;i++)//get data from line number
            {
                int s=(sel[i]-1)/top;//station
                int k=(sel[i]-1)%top;
                dd[s][0]=q[k][0]; dd[s][1]=q[k][1];//record
            }
            for(int i=0;i<n;i++)
                printf("%d %d\n",dd[i][0],dd[i][1]);
        }
        putchar('\n');
    }
}

评论(0) 阅读(1437)

python生成epub电子书

2011年9月10日 15:17

epub格式其实就是个zip压缩包,用python也不过是一些简单的文件操作
一个简单的解压后的epub目录树:

tmp
   │─ META-INF
   │   └─ container.xml (固定内容文件)
   │─ mimetype (固定内容文件)
   └─ OPS
        │─ 1.txt.xhtml (html文件)
        │─ 2.txt.xhtml (html文件)
        │─ content.ncx (目录文件!)
        │─ content.opf (信息及内容文件!)
        └─ cover.jpg   (封面,可选,位置啊名字啊都不太重要)

一个示例: gist

参考:
epub格式电子书剖析之一:文档构成
Simple EPUB ebooks with Py­thon

评论(0) 阅读(4791)

带上传的HTTP文件服务器脚本(Bottle)

2011年9月08日 16:23

轻量级的框架当然要用来做轻量级的事了!

尝试用 Bottle 做一个类似 Python 自带的 SimpleHTTPServer.py 的东西,记得有人给 SimpleHTTPServer.py 加过上传功能,看了 Bottle 后觉得可以用很少量的代码实现,而且文档里都有上传的例子了(囧)。

单文件的 Bottle 再加一个 50 行的脚本这样的组合也不比 SimpleHTTPServer.py 差多少,而且还可以随用随改,自用蛮方便的。

updated at 2013.5.8: 在 win 下,os 的函数的输入输出都是 gbk 编码的,所以有一些恶心的 hack ……

# coding: utf-8
from bottle import *
import os
import sys
from os.path import abspath, basename, join, isfile, isdir

basepath = abspath(sys.argv[1] if len(sys.argv) > 1 else '.')

struct = '''
<!doctype html>
<html>
  <head>
    <meta charset=utf-8>
    <title>Directory listing for {path}</title>
  </head>
  <body>
    <h2>Directory listing for {path}</h2>
    <hr><ul>
{lis}
    </ul><hr>
    <form action="" method="post" enctype="multipart/form-data">
      Upload file: <input type="file" name="file"/>
      <input type="submit" value="submit">
    </form>
  </body>
</html>
'''
li = '<li><a href="{name}">{name}</a>'


@get('/<path:re:.*>')
def main(path):
    if sys.platform.startswith('win'): # f**k gbk
        path = path.decode('utf8').encode('gbk')
    curpath = join(basepath, path)
    if isfile(curpath):
        return static_file(path, root=basepath, download=path)

    childs = [join(curpath, c) for c in os.listdir(curpath)]
    dirs = filter(isdir, childs)
    if path:
        dirs = ['..'] + dirs
    files = filter(isfile, childs)
    lis = [li.format(name=basename(d)+'/') for d in dirs]
    lis += [li.format(name=basename(f)) for f in files]
    if sys.platform.startswith('win'): # f**k gbk
        path = path.decode('gbk').encode('utf8')
        lis = [l.decode('gbk').encode('utf8') for l in lis]
    return struct.format(path=path if path else '/', lis='\n'.join(lis))

@post('/<path:re:.*>')
def upload(path):
    upfile = request.files.get('file')
    filename = join(basepath, path, upfile.filename)
    if sys.platform.startswith('win'): # f**k gbk
        filename = filename.decode('utf8').encode('gbk')
    outfile = open(filename, 'wb')
    try:
        buf = upfile.file.read(upfile.bufsize)
        while buf:
            outfile.write(buf)
            buf = upfile.file.read(upfile.bufsize)
        outfile.close()
        return 'Uploaded %s !' % upfile.filename
    except Exception, e:
        print e.message
        return 'Failed in uploading %s !' % upfile.filename

if __name__ == '__main__':
    debug(True)
    run(reloader=True, host='0.0.0.0', port=8080)

评论(0) 阅读(3479)

解决secureCRT和vim乱码

2011年9月03日 14:50

secureCRT 和 vim 都有乱码问题,有时候以为是一个的问题结果却是另一个的,不如统一设成utf-8。

对于 secureCRT:
会话选项 -> 终端 ->外观:字体选为 fixsys 或 terminal,字体编码选为UTF-8。

对于 vim:
.vimrc 中加入:
set encoding=utf-8
set fileencodings=utf-8,chinese,latin-1

对于文件:
用:
$ file 文件命名
来查看文件编码,用:
$ iconv -f big5 -t UTF-8 -o users.txt users.utf8.txt
转换文件编码。
如果按如上 vim 设置后,文件打开无乱码,可用:
:set fenc
查看文件编码,用:
:set fenc=utf-8
转换文件编码并保存。

对于screen,新开或恢复时都加-U参数就可以了。

评论(0) 阅读(3390)