满脑浆糊的病猪的窝

Visual Studio中去掉代码行尾空格的宏

2008-06-08T02:07:00.000+08:00

Sub RemoveTrailingWhitespace()
ActiveDocument.Selection.SelectAll()

' Replace all the trailing whitespace
ActiveDocument.Selection.ReplaceText(":b+{$}", "\1", vsFindOptions.vsFindOptionsRegularExpression)

End Sub

我到过的国家

2008-01-14T22:04:00.000+08:00

这里说的“到过的国家”是出过机场的，在法国和日本只在机场转机，就没有算在内。

我到过的国家:

create your own visited country map
or write about it on the open travel guide

我到过的美国的州：

create your own personalized map of the USA
or write about it on the open travel guide

2007年过去了！

2008-01-14T10:30:00.000+08:00

2007年过去了，大家新年快乐！
很久没有来更新这里，这段时间发生的一件大事是：我终于参加了TC的onsite算法比赛！以algorithm finalist和development review board member的身份参加TCCC07。
semi-final发挥得还不错，杀进wildcard room，可惜还是实力不济没法进入final.
TCCC是在Orlando举行，那里有全球最大的Disney乐园！

我的picasa相册里有一些照片：
http://picasaweb.google.com/iamcs1983

TCO on-site Final

2007-07-01T01:20:00.000+08:00

现在在Las Vegas机场，准备回国了，TCO很好玩，哈哈。

TCO 2007 Algorithm

2007-04-17T22:08:00.000+08:00

止步于Round 2, 太郁闷了, 又犯了白痴低级错误, 做了两题, challenge得到125分, 最后居然两题全挂. 第二题简单的DP写错, 很遗憾, 看来这辈子没法去TC的onsite final.

好像blogspot又被封了

2007-04-17T22:05:00.000+08:00

不过还可以更新文章，但是访问不了页面，好像用zhuaxia可以看到这里的文章。

My TopCoder Card

2007-02-27T11:30:00.000+08:00

type="application/x-shockwave-flash">

离歌

2007-02-26T23:00:00.000+08:00

一开始我只相信伟大的是感情
最后我无力的看清强悍的是命运

你还是选择回去
他刺痛你的心但你不肯觉醒
你说爱本就是梦境
跟你借的幸福我只能还你
想留不能留才最寂寞
没说完温柔只剩离歌
心碎前一秒用力的相拥着沉默
用心跳送你辛酸离歌

原来爱是种任性不该太多考虑
爱没有聪不聪明只有愿不愿意

你还是选择回去
他刺痛你的心但你不肯觉醒
你说爱本就是梦境
跟你借的幸福我只能还你
想留不能留才最寂寞
没说完温柔只剩离歌
心碎前一秒用力的相拥着沉默
用心跳送你辛酸离歌

想留不能留才最寂寞
没说完温柔只剩离歌
心碎前一秒用力的相拥着沉默
用心跳送你辛酸离歌

看不见永久听见离歌

第一届百度之星MV

2007-02-26T21:52:00.000+08:00

挺怀念的，这么多人聚在一起。领略一下当年水哥的风采。

SRM340 DIV1 1000

2007-02-23T18:19:00.000+08:00

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;

public class VegetableGarden
{
    const short INF = 20000;

    int m, n;
    string[] g;

    int cPos, cI, tot, target;
    List<int> px, py;
    short[, ,] f;
    Queue<Node> Q;

    int[] dx ={ -1, 1, 0, 0 };
    int[] dy ={ 0, 0, -1, 1 };

    class Node
    {
        public sbyte x, y;
        public short mask;

        public Node(sbyte x, sbyte y, short mask)
        {
            this.x = x; this.y = y; this.mask = mask;
        }
    };

    void add(Node p, int w)
    {
        if (f[p.x, p.y, p.mask] <= w) return;
        f[p.x, p.y, p.mask] = (short)w;
        Q.Enqueue(p);
    }

    public int[] getMinDistances(string[] garden)
    {
        g = garden;
        m = g.Length;
        n = g[0].Length;

        px = new List<int>();
        py = new List<int>();
        target = 0;
        cPos = cI = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) if (g[i][j] != '.')
                {
                    px.Add(i);
                    py.Add(j);
                    if (g[i][j] == 'I') { target |= 1 << cPos; cI++; }
                    cPos++;
                }

        tot = 1 << cPos;
        f = new short[m + 1, n + 1, tot];
        for (int i = 0; i <= m; i++)
            for (int j = 0; j <= n; j++)
                for (int k = 0; k < tot; k++) f[i, j, k] = INF;
        Q = new Queue<Node>();

        add(new Node(0, 0, 0), 0);
        while (Q.Count > 0)
        {
            Node p = Q.Dequeue();
            int w = f[p.x, p.y, p.mask] + 1;

            for (int i = 0; i < 4; i++)
            {
                int x = p.x + dx[i], y = p.y + dy[i], mask = p.mask;
                if (x < 0 || x > m || y < 0 || y > n) continue;

                if (i <= 1)
                {
                    for (int j = 0; j < cPos; j++)
                        if (y > py[j] && ((p.x == px[j] && i == 1) || (x == px[j] && i == 0))) mask ^= 1 << j;
                }

                add(new Node((sbyte)x, (sbyte)y, (short)mask), w);
            }
        }

        int[] ans = new int[cI];
        for (int i = 0; i < cI; i++) ans[i] = INF;
        for (int i = (1 << cPos) - 1; i > 0; i--) if ((i | target) == target)
            {
                int k = -1;
                for (int j = 0; j < cPos; j++) k += (i >> j) & 1;

                ans[k] = Math.Min(ans[k], f[0, 0, i]);
            }

        return ans;
    }


}


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003] [modified for C# by Petr]
// Powered by CodeProcessor

SRM340 DIV1 250

2007-02-21T02:40:00.001+08:00

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;

public class ProblemsToSolve
{
    const int INF = 999999999;

    int n, m;
    int[] a;

    int com(int l, int r, int min, int max)
    {
        int[] f = new int[r + 1];

        if (a[l] < min || a[l] > max) return -1;
        f[l] = 1;
        for (int i = l + 1; i <= r; i++)
        {
            f[i] = INF;
            if (i < r && (a[i] < min || a[i] > max)) continue;

            f[i] = Math.Min(f[i - 1] + 1, f[i]);
            if (i - 2 >= l) f[i] = Math.Min(f[i - 2] + 1, f[i]);
        }

        if (f[r] == INF) return -1;
        return f[r];
    }

    public int minNumber(int[] pleasantness, int variety)
    {
        a = pleasantness;
        n = a.Length;
        m = variety;

        int res = n;

        for (int maxp = 0; maxp < n; maxp++)
        {
            for (int minp = 0; minp < n; minp++) if (maxp != minp)
                {
                    if (a[maxp] - a[minp] < m) continue;

                    int i1, i2;
                    if (minp < maxp) { i1 = minp; i2 = maxp; }
                    else { i1 = maxp; i2 = minp; }

                    int v1 = com(0, i1, a[minp], a[maxp]);
                    if (v1 < 0) continue;

                    int v2 = com(i1, i2, a[minp], a[maxp]);
                    if (v2 < 0) continue;

                    int v = v1 + v2 - 1;
                    res = Math.Min(res, v);
                }
        }

        return res;
    }


}


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003] [modified for C# by Petr]
// Powered by CodeProcessor

以后把程序都贴到网上来

2007-02-20T11:52:00.000+08:00

这次放假回家不小心把硬盘摔坏了，以后要把程序放在网上，比较安全。

扫雷高级38秒视频

2007-02-01T10:48:00.000+08:00

太bt了，据说是目前高级的世界记录。

Kyle XY 里的一道数学题

2007-01-17T09:46:00.000+08:00

这是电视剧集《Kyle XY》里出现的一道数学题，"A professor at MIT presented this problem, it took his students six weeks to crack it. Sort of like a mathematical Mount Everest, if you will."
男主角Kyle看了一眼就会做了。

上面有些字看不清楚，不知道题目是什么意思，谁有兴趣就来看看吧。

考完试了

2007-01-16T11:31:00.000+08:00

前几天考完试了, 发现自己的考试能力每况日下, 看来适当的应试教育还是必需的. 决定开始使用题海战术, 做 Concrete Mathematics, Introduction to algorithms 和 The Foundations of Program Verification 的习题.

哇！肥佬上了TIME的封面！

2007-01-05T15:26:00.000+08:00

我错了

2007-01-04T10:13:00.000+08:00

下面那个唱《因为是女人》的美女是裴涩琪，不是MV的女主角。
去Google了一下，那个女主角叫做Goo Hye-Jin，关于她的资料很少。

我的2006年

2007-01-03T23:41:00.001+08:00

学henry，把我的2006年总结一下，很多事都忘记了，大部分是参照blog的内容写的。

1月，去北京参加GCJ China决赛，第6名。第一次滑雪。
4月，美国San Antonio，ICPC决赛，发挥不太好，全队才做出3题，并列第19名。
6月，被邀请去参观北京Google，也因为这个错过百度之星复赛，可惜。
7月，TC的算法rating达到2584，创本人历史新高。
8月，偷偷回家休息了几天。
9月，Google Code Jam第二轮失利。
10月，TCCC第3轮失利。
12月，做TC的dev第一次win，是.net的组件。
12月，和本科的同学去小肥羊吃火锅。

一首经典的歌《因为是女子》

2007-01-03T15:17:00.000+08:00

这个是MTV女主角唱的：

相信很多人都看过，经典的MTV：

把原来MSN SPACE的内容都搬过来了

2007-01-03T15:09:00.000+08:00

以后就在这里安家吧。

颈部有些不舒服

2006-12-30T14:15:00.000+08:00

头部保持一个姿势久了有点难受,精神无法很集中,烦.

嗯

2006-11-14T14:20:00.000+08:00

邮件的题目全是大写英语字母的,统统要SPAM!

好无聊

2006-11-08T14:21:00.000+08:00

逃课回家呆了10天，每周四下午的英语课已经不知道被点过多少次了，可能要挂了。这周四还要做presentation，我们组两个人要讲20分钟的，麻烦啊。
总是很疲倦，什么也不想做，觉得唯一有意思的事是做算法题，活跃一下大脑，可难题又不会做。总是觉得自己身体不舒服，可能快要死了。

昨天去打球

2006-09-25T13:22:00.000+08:00

昨天上午和牛头、熊去打篮球，随便练了练投篮，已经完全没有手感了，怎么投怎么不进。
今天下午打算和锦标、伟东去打羽毛球。

GCJ06 Over...

2006-09-21T13:23:00.000+08:00

希望越大，失望越大，Google CodeJam 2006 Round2。
第一题被cha，system testing开始前虽然只排在121位，但是还是很有信心进入前100名去onsite finals。这时我和bug,rocking还有dy排名都差不多，我坚信如果后两题都pass一定可以晋级。没想到第三题居然fail...好久没有在TC的比赛里fail，这次最关键的时候居然失手了。
第三题是说给定一个树，树的边有权值，求一个包含最多顶点的子树，这棵子树要包括给定的一个起点，且树中的边的总权值不大于给定的一个上限。简单的DP树形DP。我的程序DP的时候没有把原来的值备份，而更新值的方向也没有选好，会在同一层里把更新过的值再次使用。如果把原来的值复制一份就pass了，好可惜。这题的失误主要是读题时没有看清楚，看漏了给定的是一棵树的条件，还以为是无向图，浪费了很多时间，看清楚以后就疯狂敲程序，能通过所有 sample的时候剩下的时间已经只有6分钟，没有再仔细看一遍代码就匆匆提交了。
bug的第三题也fail，没能入围，rocking和dy进入了决赛，预祝他们在决赛里取得好名次。
想参加GCJ的finals只有等明年了，过两天还有TCCC的比赛，不过TCCC只能有48人去现场，基本没什么希望。

我好像很出名啊

2006-09-17T13:27:00.000+08:00

昨晚在Google上搜索"Savior"，没想到我的这个space居然排在第二位！这里真的这么出名吗？还是Google被我这里指向自己的链接弄晕了？
再搜索我的bbs上的ID: "iamcs"，我上次参加baidu之星写的代码 astar.baidu.com/data/demo/Iamcs.txt 在第二位。
另外还有 International Alliance of Messianic Congregations and Synagogues 以及 International Adoption Medical Consultation Services 的缩写都是 iamcs 。

Google CodeJam 2006 Round 1

2006-09-17T13:26:00.000+08:00

14号晚上10点开始比赛，我发挥还不错，第二题想复杂了一些，分数比较低。

关键还是第二轮，前100名去美国现场比赛。我去年第二轮得了第7名，可惜由于来不及办签证而没能去成。
这次我已经提前预约，签证面谈时间在10月17日。而且由于上次去ICPC Finals的签证是5月过期，还可以使用免面谈获取签证的服务。

开学了

2006-09-11T13:29:00.000+08:00

研究生的生活好像和本科差不多，好无聊，不过可以做TCCC，混完两年吧。
　　长胖了，前几天体检，身高172，体重68。

明天回家啦

2006-08-06T13:29:00.000+08:00

后天到，回去能看电视吃大餐睡大床，真爽。
大家祝我一路顺风。

什么也不想做

2006-08-03T13:31:00.000+08:00

打开自己的space，看着以前的照片，听着最喜欢的歌，对着电脑发呆。
胡思乱想，想起很多事，小学的启蒙老师，第一次的队友axing和splutter，小实和小勇的故事，中学同学们，轻松参加高考，飞沙滩的露营...

今天早点睡

2006-07-30T13:31:00.000+08:00

不知道怎么回事，这两个月来总觉得自己的身体怪怪的，不知有什么问题，可能是心理作用吧，也可能是真的老了。我们这些IT人，也许不知什么时候就会倒在电脑前，永远也醒不来了。
刚才心口有些不舒服，今天早点睡。下个月回到家要去医院好好检查身体...

恭喜妹妹找到好工作

2006-07-29T13:32:00.000+08:00

在三亚，以后我要去海南度假啦。

昨天打篮球很爽

2006-07-24T13:32:00.000+08:00

昨天早上8点多被人叫起来打篮球，和竹信，锋哥，大傻，rocking，mp，KK，还有竹信的两个朋友。没想到竹信这么厉害。太久不运动了，今天早上起床浑身酸疼。
晚上的SRM 312有奖金，0点开始，和ACRush同一间房。第三题1050分，挺麻烦的DP，比赛结束前几分钟提交，后来发现最大的数据是超时的，马上改程序，把用map的地方改成自己写的哈希，比赛结束的N秒前提交，发现算哈希函数的地方打错了，而且没初始化局部变量，晕...这样都过了sample。整个 room只有我和ACRush交了第三题，我排在第一名。
果然challenge phase开始的几秒后我的程序就被他cha掉了，又过了几秒我也把他的cha掉，用的最大规模的随机数据，他的答案错了。互送了50分，我仍然排第一。过了一会我cha错一个，最后的关头我做了一件傻事，就在结束前的几秒钟，我冲动的去cha某人的第一题，fail，扣掉25分后我把第一的位置拱手让给了Swetko，他一个challenge都没有，当时要是我看看时间就好了。不爽，奖金少很多。
测试结束后，前三名的位置没变，我第2，ACRush第3，我的rating又创新高。后来在练习室里我把改对的第三题提交，还是超时，后来又把用vector的地方改成数组，也没用，又去改其他的细节，搞到快3点多，仍然超时，我就不知道怎么优化了，关机睡觉。
最近的几次的SRM我发挥都还比较稳定，rating稳步上升，前两题都做得不错，可惜第三题还是做得不好，大部分都没做出来，做难题的实力和真正的牛人们还是有差距。

放假啦

2006-07-20T13:34:00.000+08:00

前段时间成了病猪，感冒发烧头晕，现在总算好了点。
当了几天4+2选拔赛的评委，看着师弟们努力的样子，不免想起当年的我。的确老了，想去单挑干扰师弟们集训的，发现自己怎么也没力气做完5个小时。希望能有师弟们成长起来，去总决赛拿到金牌吧。
毕业了，发现大学4年来值得我骄傲的东西除了ACM还是ACM。难看的成绩单让我苦恼，Google的实习都拒了我，还打电话来说我各方面都很优秀，就是GPA低了点。勇哥说Google很看重成绩，尤其是本科成绩，看来我以后是没什么机会去Google。而且勇哥也把Google拒了，以后 Google恐怕会不太爽中大吧。
昨晚和复旦的师妹聊天，她说我当年参加NOI的省赛队友本科毕业去了Google。他当年应该算是菜鸟吧，士别三日当刮目相看，何况是四年。我两年后又将何去何从呢？我心目中最理想的当然是Google和MS,BIDU也行吧，不管了，先好好学习，以后看谁要我吧。

观参北京Google归来

2006-06-06T13:35:00.000+08:00

6月3号到4号，应北京Google的邀请去玩，第一次住Shangri-La，第二次吃全聚德，第N次游故宫，总的来说还挺爽的。
Google的办公环境还不错，不过没怎么拍照，反正以后机会还很多。

TCO06

2006-05-09T13:36:00.000+08:00

Congratulations to biotrail, the 4th place on TCO06 Development Finals.
为我们中大增光啦。

Congratulations to fuwenjie, the 4th place on TCO06 Algorithm Finals.
进入算法决赛的唯一的中国人，不愧是我中学时的偶像，昔日的全国第一，果然实力不俗。
dy很可惜，没有能从wildcard room杀出来。
希望我有一天也可以参加这样的onsite finals.

Over...

2006-04-22T13:37:00.000+08:00

Finals结束，我的ACM生涯也结束了。成绩不好，让大家失望，对不起...
以后就在TopCoder里混吧，把rating搞高点。

刚才去看Tomek的CV，发现又多了一个WINNER头衔: January 2006: CodeCup 2006 - WINNER

有进步

2006-02-26T14:39:00.000+08:00

断断续续地，终于把ltc在2004年8月出的比赛题全部做完。我想如果能有他的一半实力，在Finals上应该就可以拿金牌了吧。
　　早上发现昨天写的用Leftist Tree的程序（其实就是POJ的 1738题）犯了一个错误，我傻乎乎地写了一个函数删掉树上的任意节点x，以为只要对x的父亲做一次FixDist，然后再把整个树与x的左、右子树合并就可以，而且这样也能AC，今天早上才发觉这样其实是破坏了左偏树的性质。后来想不到有什么快速的方法能实现这个操作，于是换了一种做法避免这个操作。

今天写程序又用到了左偏树

2006-02-25T14:39:00.000+08:00

Leftist Tree的所有操作都是基于Merge,合并两棵Leftist Tree.
Merge(a,b):
if(a == NULL) return b;
else if(b == NULL) return a;
else if(a->key <>key) {
a->right = Merge(a->right, b);
FixDist(a);
return a;
}
else {
b->right = Merge(b->right, a);
FixDist(b);
return b;
}

FixDist(a):
if(Dist(a->left) <>right)) swap(a->left, a->right);
a->dist = Dist(a->right)+1;

Dist(a):
if(a == NULL) return 0;
else return a->dist;

为啥非要有标题才能发呢？

2006-02-24T14:41:00.000+08:00

前一次的SRM又得0分，每次升上红色都要大跌一次。好在昨晚又爽了一把，可惜的是第三题没做对，结束前的10分钟随便测了测，就发现自己已经提交的程序会超内存。其实在写第三题之前就犹豫了一下是不是应该用滚动数组来保存，根据我以往TC的经验，经常是最直接的方法就可以过的，没想到这次却不行了。我用这组数据瞬间cha掉同房的4个第三题，在一个比我的方法更加暴力的程序面前却失败了，换了一组数据还是不行，我不想浪费分数就没有再试，果然他后来还是被别人cha掉。System test结束时看着自己的名次慢慢地升到第6，希望下次的SRM能够保持住红色吧。
　　前几天重装XP，今晚把XP下的一些常用软件装好；看了看郭德刚的相声，挺逗的；又想了某题的算法，太晚了，还是明天再写程序吧。睡觉吧，晚安。

Timus Top Coders: First Challenge题目总结

2006-02-15T14:42:00.000+08:00

Timus Top Coders: First Challenge题目总结：
A: 一个N*N的方阵，里面填0到100的数，已知每行的数的和分别为SR1,SR2...SRn,每列的数的和为SC1,SC2...SCn，求出一个符合条件的方阵。
我是用网络流做的，想了很久都想不出简单的构造方法。构造一个n*n的二分图，弧的容量都为100，加一个源点和一个汇点。源点出发的n条弧的容量设为SRi，流入汇点的弧的容量为SCi，求最大流。

B: 三维空间中有一些点，求同一条直线能穿过的最多点数。
二维的是老题，改一下就可以做三维。

C:　给定字符串S和T，对S做cycle shift，问能否得到T。
在串SS中用KMP找T是否出现即可。

D: 一辆有最大容量为m的bus，从车站1开到N，已知每位乘客的上车站Si和下车站Fi(Si< Fi)，求最多可以运送多少位乘客。
经典的贪心。把乘客按Fi从小到大排序，Fi相同的则Si大的在前。按序扫描这些乘客判断能其否上车。对于当前乘客u，在已上车的乘客集合P中找到Fv最大的乘客v,且Fv<=Su，如果v存在则把v从P中去掉，此时如果|P|< m则u就能上车，并把u加入P。处理P可以用线段树。

E: 在一个N维，每维大小为S的棋盘中移动皇后，皇后可以按车的走法或象的走法。车的走法是改变任一维的值，象的走法是每一维的值都改变相同的绝对值。问2步之后皇后能走到的不同位置的数目。
这里N<=5,S<=100，每一步粗略估计最多不超过3700种走法，可以用BFS+Hash直接做。这题的内存和时间都比较紧，我是用1 个char和1个integer来表示状态才过的。用1个long long就超内存，用5个char就超时。

F: 在平面上给出任意4点（可能位置相同），求一个矩形使这4点都在矩形的边上。
不会做，你教我...

G: 简单题，扫描一次即可。

H: 已知A,B,C且A,B都是C-1的约数，求X,Y,Z满足X^A+Y^B=Z^C
设pA=qB=C-1，则令X=2^p,Y=2^q,Z=2即可

I: 在平面上给定一些圆的位置，问这些圆的圆周把平面分成多少个区域。
这题和ZOJ2589是一样的，但精度要求更高些。主要思路是用欧拉公式，注意还要求有多少个连通块。先把两两圆的交点求出，同时用hash保存点会比较方便。这题中的圆可能重合，要预处理一下。

J: 已知正整数A,B,N，求最大的不大于N的整数M满足AX+BY=M且X,Y都为非负整数
我们知道X,Y都为非负整数且(A,B)=1时，AX+BY可以表示大于等于AB-A-B+1的所有整数。所以当N不能表示成AX+BY的形式时，必有 AB-A-B+1>N => (A-1)(B-1)>N-2，这时可以直接枚举A,B中较大的数的系数来求，复杂度是O(sqrt(N))的。(A,B)>1时容易转化成 (A,B)=1的情况。