Monthly Archives: August 2010

TopCoder入门教程(转载)

本文根据经典的TC教程完善和改编。
TopCoder:http://www.topcoder.com/

基本规则

TopCoder的比赛类型很多,最常见的是周赛SRM(Single Round Match),另外还有TCHS SRM(TopCoder High School SRM,题目和SRM一样,仅限中学生参加,参赛者水平较低,据说涨rating很容易),马拉松(Marathon Matchs),还有TCOpen(每年两次的大比赛)之类的比赛。因为大多数人都在做SRM,所以本文介绍的TC比赛即为SRM。

SRM的规则总结起来就是一句话:75分钟做完3道难度递增的题。

TC的每个用户(handle)都有自己的积分(rating),从0-3000+不等。成绩越好,分数越高。积分与颜色的对应为:白色——未参赛(unrated);灰色——0~899;绿色——900~1199;蓝色——1200~1499;黄色——1500~2199;红色——2200+。另外排名最高的几个人在TC客户端中会变成红色靶子图标。

比赛分为两个Division,Div I和Div II。白色灰色和绿色的参加Div II,蓝色黄色和红色的参加Div I。Div I的题要比Div II难许多,一般DivII的最后一题和Div I的第一或第二题是一样的。无论是Div I或Div II。三道题目的Score一般为250, 500和1000。

TC的计分规则很诡异,可以见http://www.topcoder.com/wiki/display/tc/Algorithm+Competition+Rating+System,但基本是没人看的懂。不过,TC积分规则的基本思想很简单。

首先是SRM每道题的计分规则。题目从打开开始计时,随着时间的流逝,你这道题目可能得到的分数也越来越少。不过分数减少的速率会逐渐变慢(有人说是先快后慢再快再慢,我不清楚到底哪个是对的,不过总体趋势是越来越慢),一般1000分的题目在降低到300分的时候就基本不会再下降太多了。每道题点击Submit才算正式提交,如果Submit之后发现错误,还可以再次点击Submit修改提交,不过这样会扣除这道题一定的分数。

其次是TC的计分规则。复杂的数学公式很难看懂,但大概的计分思想是:根据此次比赛的得分算出一个这次比赛的rank,然后和以前的rank做比较,求出一个期望的rank,再根据这个期望的rank调整rating。而有时也会出现考得很砸但依然涨rating的情况,不过总体来说TC的计分公式是十分稳定的。

Read more »

Stars in Your Window(翻译)

译/陈维晃,王泽辉,张木兰

Fleeting time does not blur my memory of you.
流光并未模糊你留给我的记忆。

Can it really be 4 years since I first saw you?
我们初次见面真的已经4年过去了么?

I still remember, vividly, on the beautiful Zhuhai Campus, 4 years ago, from the moment I saw you smile, as you were walking out of the classroom and turned your head back, with the soft sunset glow shining on your rosy cheek, I knew, I knew that I was already drunk on you.
我依然清晰的记得,4年前,在美丽的珠海分校,看到你走出教室,落日的余晖洒落在你微笑的脸上,从那一刻起,我知道我已为你倾倒。

Then, after several months’observation and prying, your grace and your wisdom, your attitude to life and your aspiration for future were all strongly impressed on my memory.
经过数月的关注,你的优雅,你的学识,你对生活的态度以及你对未来的憧憬都深深地印在我的脑海。

You were the glamorous and sunny girl whom I always dream of to share the rest of my life with.
迷人而开朗的你,是我做梦都想共度余生的女孩。

Alas, actually you were far beyond my wildest dreams and I had no idea about how to bridge that gulf between you and me.
唉,我最漫无边际的梦想是架起一座桥,一座能够通往彼此心灵的桥。

So I schemed nothing but to wait, to wait for an appropriate opportunity.
我一直在等待,等待一个合适的机会。

Till now — the arrival of graduation, I realize I am such an idiot that one should create the opportunity and seize it instead of just waiting.
直到临近毕业的现在,我才意识到我是多么的愚蠢,我本该去努力创造那个机会,而非等待。

These days, having parted with friends, roommates and classmates one after another, I still cannot believe the fact that after waving hands, these familiar faces will soon vanish from our life and become no more than a memory.
这些天,朋友们陆续离开了,我无法接受那么多熟悉的面孔一个一个从我生活中消失,只留下记忆。

I will move out from school tomorrow. And you are planning to fly far far away, to pursue your future and fulfill your dreams.
明天我也要走了。而你将要飞到很远很远的远方,去追逐你的梦想。

Perhaps we will not meet each other any more if without fate and luck. So tonight, I was wandering around your dormitory building hoping to meet you there by chance.
也许我们再也不会见面。今晚我在你的宿舍外徘徊,希望能够见到你。

But contradictorily, your appearance must quicken my heartbeat and my clumsy tongue might be not able to belch out a word.
但事与愿违,你的出现使我紧张的说不出话。

I cannot remember how many times I have passed your dormitory building both in Zhuhai and Guangzhou, and each time aspired to see you appear in the balcony or your silhouette that cast on the window.
我不知道有多少次我经过你的宿舍渴望你出现在阳台上或在透过窗户看到你的轮廓。

I cannot remember how many times this idea comes to my mind: call her out to have dinner or at least a conversation.
我不知道有多少次这样的想法出现在我的脑海里:约她出来吃个晚饭,至少可以说说话。

But each time, thinking of your excellence and my commonness, the predominance of timidity over courage drove me leave silently.
但每次想起你的优秀,我的平庸,胆怯打消了我的念头。

Graduation, means the end of life in university, the end of these glorious, romantic years.
毕业,意味着我的大学生活结束了,快乐而烂漫的时光结束了。

Your lovely smile which is my original incentive to work hard and this unrequited love will be both sealed as a memory in the deep of my heart and my mind.
你那驱使我努力学习的笑容和我这份得不到回应的爱将一起深深封存在我的心里。

Graduation, also means a start of new life, a footprint on the way to bright prospect.
毕业,也意味新生活的开始,美好的未来将印上新的足迹。

I truly hope you will be happy everyday abroad and everything goes well.
我真诚的希望你在国外一切都好,每一天都开开心心。

Meanwhile, I will try to get out from puerility and become more sophisticated.
同时,我会努力把自己从幼稚变得成熟。

To pursue my own love and happiness here in reality will be my ideal I never desert.
我不会放弃我理想中的爱情和幸福。

Farewell, my princess!
再见了,我心爱的女孩!

If someday, somewhere, we have a chance to gather, even as gray-haired man and woman, at that time, I hope we can be good friends to share this memory proudly to relight the youthful and joyful emotions.
如果有一天,在世界的某一个角落,我们有机会相聚,即使已是头发花白的老人,我希望我们能像好朋友一样分享这回忆,重新点燃青春还有这美好的情感。

If this chance never comes, I wish I were the stars in the sky and twinkling in your window, to bless you far away, as friends, to accompany you every night, sharing the sweet dreams or going through the nightmares together.
这一天也许永远不会到来,我希望我就是那天空的星星在你的窗前闪烁,像朋友一样祝福远方的你,与你共度每个夜晚,无论梦是否甜蜜,我们都在一起。

Read more »

山楂树

歌声轻轻荡漾在黄昏的水面上,
暮色中的工厂已发出闪光,
列车飞快地奔驰,
车窗的灯火辉煌。
山楂树下两青年在把我盼望。
当那嘹亮的汽笛声刚刚停息,
我就沿着小路向树下走去。
轻风吹拂不停,
在茂密的山楂树下,
吹乱了青年旋工和铁匠的头发。
啊!茂密的山楂树呀,白花满树开放。
我们的山楂树呀!它为何要悲伤!

Read more »

并查集笔记

最近做了一些并查集的题目,所以在这里整理一些笔记。
并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。用树的根节点来区分是否处于不同集合。对于每个节点只需要记录其父节点的编号即可。
如建立int pre[]数组表示树结构,下图在数组中的表示为
pre[1]=3;pre[2]=1;pre[3]=3;pre[4]=3;pre[5]=3;pre[6]=1;

所有的节点都指向其父节点,只有根节点是指向自身。

一.并查集的主要操作:

1.1 判断两个元素是否属于相同的集合

需要注意的是,在初始状态我们认为每个元素都是一个独立的集合,既pre[i]=i;
要判断两个元素是否属于相同的集合,只要找到其根节点就可以,不同的集合属于不同的树,自然根节点也就不同了。查找根节点只要判断pre[x]是否等于x即可。

C语言代码表示形式

int Find(int x)
{
  while(x!=pre[x]) x=pre[x];
  return x;
}

1.2 合并两个不同集合

因为每个节点只记录其父节点的编号,所以只要将其中一棵树的根节点指向另一棵树的根节点(其实可以指向另一棵树的任何一个节点)。

C语言代码表示形式

void Union(int a,int b)
{
  a=Find(a);
  b=Find(b);
  pre[b]=a;
}

二.并查集的优化

2.1 路径压缩

并查集的一棵树有可能像左边的那个图一样么?

......

Read more »