《快乐的小侏儒》 海尔曼·黑塞

2011年2月17日 09:48

(小时候看到的一篇童话,找了好些年,曾找到一篇不完整的贴在以前的博文里,今天突然人品爆发,搜到了, (补:这里有全书在线阅读),以前一直无视这个超星什么什么的,没想到关键时刻给力了,20页试读图片就够了,找OCR软件,发现oneNote的右键菜单里居然有这么一项,简单快速正确率高,想起初中时用的汉王那啥的就是个渣,识别完又校对了一遍,一个晚上就这样过去了.感觉挺好,有些过去事也不是完全找不回来的)

快乐的小侏儒

海尔曼·黑塞

    蔡可是个善讲故事的老头儿。一天晚上,他又在码头上有声有色地讲起来。

    诸位,今天我给大家讲个古老的故事。说的是一位美丽的女人,一个侏儒,一种爱之水,忠诚和背叛,爱与死。其实,所有的故事都是这样。

    玛格丽塔.卡多林小姐是贵族巴蒂斯沓·卡多林的女儿。在那时,她是威尼斯最美丽的女人。赞美她的诗歌比大运河边宫殿的窗子还多,比春夜里河上的游艇还要多。威尼斯、木拉诺和巴丢阿的几百位老少贵族做梦都梦到她,早上一睁眼就渴望见到她。在全城中,很少有人不嫉妒她。我不是在夸耀她,我是要告诉你们,她是个金发姑娘。高高的个子,苗条得像细竹。风儿在抚摸她的金发,大地在抚摸她的双脚,当画家提香见到她后,就会放弃一切,埋头画上她一年。

    她的服饰、她那拜占庭织锦、她的石刻和装饰品都精美无瑕。她的宫殿富丽堂皇:铺的是小亚细亚的彩色厚毯,柜中是银器,桌上铺着闪光细缎,摆着精致的瓷器,起居室中铺着拼花地板,天花板、墙壁上挂着丝锦挂毯、美丽而色彩明快的油画。她的仆人成群,还有很多游艇和划船手。

这些贵重的东西别人当然也有,而且有人的宫殿比她的更辉煌,柜中宝贝更多,值钱的东西、画毯和装饰品更丰富、当时威尼斯城真是富有呀,可是年轻的玛格丽塔小姐所独有的宝贝却引起很多有钱人的嫉妒,这就是那个侏儒。他叫菲力浦,还不到三尺高,长着两条小短腿,是个非常滑稽的小家伙。

菲力浦原是塞浦路斯人,维多利亚·巴蒂斯杳先生旅行的时候,把他带回家来。那时,他只会说希腊语和叙利亚语。现在,他说一口地道的威尼斯话,好像他是这儿土生土长似的。他的女主人长得那么苗条而动人;他却那么丑陋。和他那发育不全的身躯比起来,她显得那么高大和显贵,就好比是渔屋旁耸立着一座教堂的塔楼。侏儒的双手又皱又黑,关节处弯曲着。他的鼻子大得可怕,脚很宽,脚尖向内,走起路来可笑极了。可他打扮得简直像个王公贵族,穿着漂亮的丝绸,戴着金首饰。

评论(0) 阅读(3503)

获得 wp Audio Player 文件地址

2011年2月11日 21:47

只是把hacklog中的php代码用python改写了一下

def decode(str):
    codekey='ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_-'
    bins=''
    res=''
    for i in range(len(str)):
        curpos=codekey.find(str[i])
        bin6=('000000'+bin(curpos)[2:])[-6:]
        bins+=bin6

    for i in range(0,len(bins),8):
        bin8=bins[i:i+8]
        res+='%c' % int(bin8,2)

    return res

if __name__ == '__main__':
    while True:
        src=raw_input('code:\n')
        print 'decode:'
        print decode(src)
        

 

评论(0) 阅读(1175)

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

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

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