谁能寄我一封笔记本

Unboxed Laptop - Macbook Air




当时我和父母在吃饭，电视屏幕上出现一个信封。。。 （只有嚼米的声音）
一只手在拉信封上的线，爸爸说：“各撒广告啊”（上海话，这是啥广告）
“跨地伐”（快递吧）
手伸进信封,(我拿起可乐的杯子)
拉出一台笔记本。（六只大大的眼睛紧紧盯着屏幕）

“哦~哦~ 平股额笔记簿” （我啪地放下杯子，右手举过头，左手指着电视说）
“啥么事啊~ 哪能噶小额啦” （妈妈语，“怎么回事？怎么这么小的啊？”）
“各平股啊，各笔记簿噶小额”（爸爸语，“这是苹果的，这个笔记本小的”）
“比额了额笔记簿小较贵了嘛”（妈妈语，“比我们的笔记本小好多啊”）

六只眼睛没有离开过电视机，直到广告结束。。。
惊奇有二：
一是苹果的广告
二是爸妈在我的影响下居然也对IT类产品感兴趣了。。。爸爸连我工作的公司都不知道，居然知道“苹果”公司。。。

最想买的两个东西

小学的时候最想买的两个东西：模型和乒乓球。模型（1）是通过对父母/爷爷/外公撒娇成功获得，乒乓球是小伙伴攒钱买的。当时唯一的社交就是在菜市场剁肉的板上打乒乓。

初中的时候最想买的两个东西：电脑和乒乓球拍。电脑未果，但买了一个步步高学习机充饥；乒乓球拍买了两幅，第二幅是横板的25元，攒了一个学期（2），在第九百货商店（3）买的，还买了好几套3星+一套四星的乒乓球，最幸运的是有一次捡到一个白色的四星球~哇塞，如获珍宝，四星的~而且是白色的。。。弹性超好！

高中的时候最想买的两个东西：《石器时代》的养羊得益包和老手削暴包。高中荒废了~ 老手削暴包（4）是得手的，养羊得益包太贵（5）

大学的时候最想买的两个东西：刻录机和羽毛球拍/网球拍。大一的时候有个朋友向我倾诉，他老哥买了个刻录机，叫他不要读大学了，跟他哥一起去卖盗版碟。当时我幼小的心灵被深深地触动了，我想我怎么就没这么好的老哥呢。于是，刻录机成为我大学的第一个目标，结果最后还是被归为奢侈品，忍住了没买。大学里，我选了羽毛球和网球的体育课，为了上这两门课，我狠下心买了一副15元的羽毛拍和一副30元的网球拍。我知道我是班级里拍子最差的，但我成绩很不错，羽毛球拿过一次4.0，网球我还是国家二级裁判呢。

最近最想买的两个东西：GE G2数码照相机和全套羽毛球装备/一副高档网球拍，猫了好久才发现的如此高性价比，又相当适合我的口味的照相机~ 认定它了！羽毛球拍已经有了，已经做好了和体育用品店做羽毛球消耗战的准备了！网球的话，一个是消费高，另一个是不太打，所以可以搁着。

注释：
1 高达/魔神斗士/舰艇等等模型，收集了很多魔神斗士的模型！有一只黄色的老虎，是生日的时候买的，158大元~ 当时对父母来说可是大出血啊！

2 当时小摊上有买1角/包的零食，巨不卫生，但销量始终很好。

3 百老汇旁边，现已拆。

4 一个包59元，传闻后来炒到500一个。我第一次体验了预定购物的乐趣。

5 据说上海限量1000个，但过了近一年我依然能在“音乐书店”（上海很老牌的店，现在拆了，我在里面买过bsb的正版碟）里找到。

将来准备做些什么？

前天某君问我将来还准备做些什么？
今天乘着休息时间跑到办公室阳台那里想了一想~

志愿一： 想开一家小的体育用品商店。
志愿二： 想做专业网球场管理员（不是小区里就一个场地那种，至少八个场地起），同时兼职给别人做网站或写程序补贴自己的收入。

想象一下，某天你去打网球，看到网球场管理员收完费后，打开一台笔记本开始啪啦啪啦打程序。HOHO，一定很有趣。

What's Up? Feb 6, 2008 Check

http://www.kloonigames.com/blog/games/crayon

So cool! A nice game.



And here, the biggest news before Chinese New Year:



Last year, big company becomes bigger, Oracle buy Bea, Sun buy MySQL, NVIDEA buy AGEIA, of cause Autodesk acquired a lot of business, I could see a big war is brewing...

笔记本贴纸

今天去宝山做贴纸，走了4家才搞定～ 这玩意果然没人喜欢玩。

第一家：你打多少？
我：一张A4
第一家：太少了，不打。

第二家：没有

第三家：你有纸么?
我：没
第三家：我帮你找找（纸）
翻了一圈后，第三家：对不起，没找到

柯达打印：好点的纸行不，照片的贴纸。
我：可以
打印。。。OK

What's Up? Jan 11, 2008 Check

http://www.perceptivepixel.com/



Something related?
Microsoft Surface, Autodesk Touch Wall, Google TouthEarth and Apple iphone multi-touch tech

Multi touch application? Application 2.0?
http://www.naturalui.eu/

Oops! Blogger available again!

Oops! Blogger and Google Page available now (in China)... I have suspend my post working for a long time~ :)

My first post to celebrate blogger come in china, would be an introduction of DevExpress and Rapture.

Since I have to use C# in company, I learned some interesting work from C# guys. DevExpress is the fantastic one! Here is the demo picture of DevExpress, check it and u will love it:





A new concept of GUI application, Ribbon comes, maybe Microsoft Office was the first guy introduced it. Instead of menus, Ribbon is provide a new vision of user experience. Here is the common structure of Ribbon:

Ribbon Page 1<-->* Ribbon Page Group 1<-->* Ribbon Button Group 1<-->* Ribbon Button

Quite similar to menu system, which has menu bar, menu list, menu item...

---

Rapture is a Screen Capture Tool that is developed by Raymond, me.. :) . To remember my first company, Hanna Strategy Ltd. , which would be closed next year.
Get Rapture from my gPage

It's only work for Windows, since I use MS C#, maybe one day I would migrate it to Mono C#.

1. Start it, and got notify icon.
2. Double click it to start Region Rapture, or right mouse click it to see the menu.
3. When u are capturing, click the right mouse button or press enter to finish the job.

The most important feature of Rapture is multiply regional capturing, which allowed u capture several regions at one time.

［转］Firefox 3/4 的最新新闻

Firefox 3.0的开发代号为"Gran Paradiso"，按照Mozilla基金会的计划，Firefox3.0将于2007年三季度正式推出。与现有的2.0不同，Firefox 3.0采用了全新的Gecko 1.9渲染引擎，这也是Firefox 3.0解决资源占用率高的关键。相比Firefox 2.0所采用的Gecko1.8引擎，Gecko 1.9在图形架构方面有了根本性的改变。Gecko 1.8采用传统的gfx图形架构，它是一种软件方案，由CPU来完成对2D图形图像的渲染；而Gecko 1.9改用"Cairo "图形架构，Cairo可以借助GPU来负责渲染2D图形图像，相当于实现网页渲染的GPU硬件加速，这样，CPU就被完全解放出来。由于现在的GPU普 遍都拥有非常强劲的硬件效能，承担网页渲染任务会非常轻松，因此从理论上说，Gecko 1.9引擎既可以实现更快的渲染速度，又能够大幅度降低CPU资源占用率，实现真正意义上的飞跃。

作为系统应用的基础构件，Cairo提供了一个稳定的用户层API，它可以提供现代化的图形处理管理能力，例如绘制与填充、映射转换、合成以及改 变Alpha半透明效果、高清晰文本显示等等，并且能够在不同的媒介上实现相同的显示输出。这个概念并不难理解，简单点说，它与OpenGL、 DirectX等图形API实际上是类似的东西，只不过OpenGL和DirectX属于3D加速的API，它们都可以让应用程序直接与图形硬件紧密地协 作；而Cario则是针对2D图像绘制的API，它向更高级的应用程序提供了一系列的图形处理功能，同时又借助OpenGL API实现与图形硬件的互动（Cario与OpenGL的衔接由Glitz函数库完成）形成，借助GPU的运算能力来处理2D图像相关的应用。那么，如果 我们将Cairo作为应用程序的图形架构，这个应用程序所涉及到的所有图像处理任务都可以由GPU来完成，在这一方面，专用化的GPU显然要比通用的 CPU更具效率。这样，应用程序不仅可以实现更丰富、更复杂的图像效果（如抗锯齿、半透明、阴影、映射转换、变形等等），同时还能在低CPU占用的前提下 保证流畅的运行。

除了这些原本就有的后端外，Cairo的后端还包括pdf、svg等，分别可对pdf格式和svg格式提供原生支持，这将能显著提升pdf文件和svg矢 量图形的渲染速度。现有PC还缺乏这样的能力，不论你拥有多么强劲的CPU，在浏览pdf文件或者放大缩小svg 矢量图形时都会感觉到显示的停滞感。但如果你的图形系统基于Cairo构建（例如Gnome），并且拥有一块主流性能的3D显卡，执行pdf、svg相关 操作将会变得非常流畅，从而有效提升用户的使用体验。显然，基于Cairo的Gecko 1.9渲染引擎也可以获得相同的效果，如果你直接在Firefox 3.0浏览器中打开pdf文档或者svg矢量图形，内容渲染速度将大大快于以往，并实现真正意义上的同步显示。

实现Gecko与Cairo的融合是一项费时费力的工作，开发者并没有试图一下子将Gecko的图形架构完全转为Cairo，而是以模块化的方式 循序渐进地进行。事实上，早在Gecko 1.8/Firefox 1.1版本中，开发者们就着手Cairo的整合工作，如Cairo中的Canvas、SVG矢量图支持模块已经在Gecko 1.8中实现，而非Cairo的SVG实现方式（例如GDI+）仍得到保留，另外Gecko 1.8/Firefox 1.1的Windows版本也没有实现SVG功能。另外，GPU硬件加速功能也没有在Gecko 1.8中实现，依然只能通过软件的方式进行页面内容渲染。基本上，Gecko1.8只是实现最初级的Cairo整合， 图形架构仍然是基于2D的gfx API。除了Firefox 1.1外，后来的Firefox 1.5和现在的2.0版本也都是采用Gecko 1.8引擎，这三者的差异更多在浏览器外壳以及对安全功能的增强。

Adobe公司并未考虑通过加大技术力量来解决这一问题，而是采用一个十分英明的办法，将Flash源代码直接捐赠给Mozilla基金会，这也 是Mozilla基金会有史以来收到的最大一次代码捐赠。Adobe表示未来将把最新的Flash源码直接提供给开源业界，以实现未来浏览器与Flash 播放功能的更佳整合。有鉴于此，Mozilla基金会决定建立一个名为"Tamarin"的新项目，专门用来管理使用Adobe所贡献的代码，而新项目将 由Adobe与Mozilla共同管理监督，相关源代码将被下一代"SpiderMonkey （Gecko的JavaScript脚本引擎）"直接整合。除了贡献Flash源代码外，Adobe还将向Mozilla基金会提供 "ActionScript Virtual Machine（简称AVM）"虚拟机软件，该软件是Flash Player播放器中的一部分，它的功能就是负责对ActionScript代码的解释。ActionScript是Adobe Flash产品平台的脚本解释语言，该语言可以实现Flash中内容与内容，内容与用户之间的交互，目前它的最新版本为3.0。与广泛使用的Java Script和微软Jscript一样，ActionScript完全符合ECMA International的ECMAScript标准。

Firefox的锐意进取将给对手带来前所未见的压力，显卡加速网页浏览即将进入现实，而Firefox将无可争议成为最快的浏览器。微软将首当 其冲面对这些压力，显然微软不会打算以IE 7.0应战，但IE 8.0似乎还没有将显卡加速渲染功能考虑在内，那么它就很难有效遏制Firefox 3.0/4.0对市场的进一步蚕食。Opera同样将大受影响，它一向被认为是浏览器家族族 中的速度冠军，在Firefox 3.0出现之后Opera很可能将失去光环。同样遭受Firefox3.0/4.0技术冲击的还有Konqueror，目前KDE项目组正在向KDE 4.0发起冲击，Konqueror也将升级到4.0版（KDE 4.0计划于07年第四季度推出），但Konqueror 4.0同样来不及增加显卡加速渲染功能，它的重点更多会放在W3C新标准新技术的支持方面。至于苹果的Safari，过去它一直采用Konqueror的 渲染引擎，现在苹果打算与Konqueror分道扬镳自行发展，缺乏开源支持的Safari要实现网页3D加速就更加困难。对整个开源来说， Firefox 3.0/4.0标志着自由软件开始在技术上超越商业软件，而伴随着开源阵营的日益壮大，这样的事情未来将会越来越多。令人愉快的是，自由软件与商业软件并 非迥然对立，两者已经开始进行紧密的合作─Adobe贡献源码、微软支持XEN莫不是如此。

n多ubuntu发行版

ubuntu确实满疯狂的：

Ubuntu 主力发行版，基于Gnome桌面环境
Kubuntu 基于KDE桌面环境
Xubuntu 基于Xface桌面环境
Edubuntu 用于教育目的的发行版
Fluxbuntu 基于Fluxbox桌面管理器
Elbuntu 基于E17桌面管理器
nUbuntu 安全性至上
Hiweed 中文环境至上
Dubuntu 同样是针对中文用户
Ubuntu CE 基督教徒专用
Ubuntu ME 回教徒专用
Ubuntu SE 魔鬼用ubuntu
Ubuntu Studio 多媒体工作环境
Scibuntu 某科学家的科学家版本
Impi Linux 针对非洲的ubuntu
zSeries Ubuntu 针对IBM主机的ubuntu
Ubuntu Ultimate 有个家伙居然想搞ubuntu终极版
Linuxmint Ubuntu盗版

2007年7月第一周

第一周上班，好累，知道赚钱的不容易了～，周末在Ubuntu论坛上逛了一圈，发现不少扯谈，分享一下：

网络操作系统：plan 9

Linus高调回应微软专利侵权指责
（当我第一次听到微软这事的时候，我的第一反应是～微软好假）

基于 Windows 的 Ubuntu 安装程序
（邮购，刻盘，现在又多了一种spread ubuntu的方法了）

世界上第一辆开源汽车

Google连续两年成为全球最有价值的商标

在公司用windows，而且公司走的是保密路线，任何代码/资料都不准带出公司，任何移动设备都不准带入公司，除了带入和带出的限制，还有一个倘若离开了项目组，不准滞留任何和原项目相关的任何资料的限制～ OMG

在家里使用ubuntu（上班的这一周，还没进过win），宣扬个性和民主，呵呵，整个人就像双重人格一样了～～
不过这样也好，至少公司用正版软件，家里用开源的，我是遵纪守法的好公民。

我很喜欢这份工作，我当初找工作的时候投了两类公司，一类是很有名的（谋生类），另一类就是建模软件的公司（兴趣类），虽然有一家建筑软件公司因为我没有 建筑的背景所以没给我二面的机会。我从小就喜欢玩模型玩具（拼飞机阿，轮船阿，四驱车阿，还有高达机器人（很贵）），很喜欢拼装成功的感觉，所以大一就选 了3DMAX，很喜欢三维的东西。

公司也不错，一周里许多公司上层都作了讲座，算是认识了吧。知道公司很年轻，但已经有相当的规模了，为了跟上这个规模，公司提供了许多给员工发展的空间。而且公司待遇满好，环境非常舒适，最让我印象深刻的是公司的厕所，豪华级别的～偶用过google、微软和IBM的厕所。。。都不及现在公司这么豪华。

同事大都是外地的本科生，公司总体上员工都很年轻，华中科技大学的人特别多～也许有特别去那里宣传过吧。其他的我有知道的是四川大学、成都大学、华东理工等等。

公司最让人头疼的一点是人多，上下班的时候电梯挤啊，吃饭的时候找个座位都很难。

Ubuntu 7.04

“Ubuntu" is an ancient African word that means "humanity to others".

继firefox热潮之后，ubuntu今年开始热起来，可以说这款打着“为人民服务”旗号的操作系统，已经愈来愈受“人民”的欢迎了。现在已经出现了不少get Ubuntu的连接，而且 ubuntu的传播方式比firefox更疯狂（下载/邮寄+免费+鼓励传播的标语）。

头条是Dell表示将在几款机型上预装linux操作系统，而且选择的就是ubuntu这么一个非企业级别（至少和redhat/suse相比）的个人系统。可以参考该网站 http://www.dellideastorm.com/

Dell的问卷调查表示，有70％的人要求能在机器上预装l inux。在Dell确定了预装的计划后，ubuntu及一些linux的粉丝们便开始组织要求各大公司发布linux版本软件的需求，其中包括要求暴雪发布基于linux的星际2，要求google移植主要软件到linux平台等等。（网站我都没记，不好意思）

除了ubuntu本身的四套发行版，Ubuntu/Kubuntu/Xubuntu/Edubuntu以外，不少网友都在为ubuntu扩大阵容：

• Wubuntu － ubuntu狂热fans写的基于web的模拟ubuntu环境的网站，用的都是js写的。
• Hiweed & Dubuntu — 在ubuntu中文站看到的，不知道其目的是什么，可能就是一个发行包吧。
• Medibuntu － 提供关于media的ubuntu包。

当然，ubuntu本身在7.04 里作了不少工作。ubuntu本身bug改了不少，感觉更加舒适稳定了。如果是邮寄ubuntu光盘的话，可以用win来运行光盘，可以看到ubuntu为win用户同样提供了一些win下的软件。果然是for human beings，即使是对头的用户也要服务，这种精神太伟大了（当然不排除抢客户的嫌疑-_-b），如果仔细观察的话，就可以发现，目前大量的开源软件都是同时支持win和linux的，而且有许多人是同时在使用win和linux的，我想这和linux包容的心态是分不开的，毕竟人不应该在一棵树上吊死，不然就死得太冤了（我也支持win的哦），多样化的世界才是多彩的世界嘛。

最后不得不谈的是ubuntu疯狂的传播策略，真的是钱多得用来砸人了。要获得ubuntu或其他发行版，可以通过免费下载，这是大部分linux采用的。而ubuntu还提供了免费邮寄的服务，可以在ubuntu的网站上直接申请少量的光盘，或者申请大量光盘（需要确定）。在上大，机器人协会就申请了500张光盘，Canonical尽还都是免费地寄过来了（-_-b, so cool）。同时，ubuntu每张光盘上会写到，请与你的朋友分享该光盘的字样。我就要求了10张光盘（送贴纸），其中有一些是重复的，也就是～你可以拿出去送人，汗，要ubuntu找我。

China va Indonesia- very fast badminton game

Badminton is exciting...

Netbeans的UML工具

今天差点被Netbeans的UML工具感动得哭了出来。从Netbeans4.0开始知道除了Eclipse还有一个这么好的IDE。虽然当时Netbeans离JBuilder和Eclipse还有很大的距离，但我一直十分坚持使用Netbeans，因为我从Netbeans身上学到的不光是使用一个IDE，更多的是做程序开发的思想。

记得那次我是写一个八数码的搜索算法分析的程序，用到了GUI，那时我发现在Label修改文本的时候可以有一个叫Resource Bundle的东西，于是我知道了Java的国际化，当时感叹啊。。。 于是呼，以后写程序坚决不在程序内直接放字符串常量，要么在头上声明个final引用，要么就Resource Bundle一下。

Netbeans的GUI编辑器是让我感动最多的地方，它的易用性给我减轻了很多的负担，使编程变得愉快而轻松。除了GUI编辑器以外，当时他的Web开发包也是让我感动死掉~，整合的Tomcat使得调式如此简便，就在当时我一再向周围的人推荐Netbeans，希望大家能把目光从Eclipse身上转移一点给Netbeans，但最后都是以失败告终。

后来Netbeans的合作开发包，虽然当时一直是对Eclipse的ECF感兴趣，但Netbeans的合作开发实在太先进了。还有JavaHelp等等，从Netbeans身上学了好多好多东西。

今天，为了在毕业设计里加几个UML图，尝试性地下载了Netbeans的UML工具包。哇！哭了，一上来就有三个选项：平台无关模型、Java模型、对Java项目做逆向工程。思路非常清晰，Java模型是主打，其他的仍然可以用平台无关模型。而我选择的是Java逆向工程，完美！把我那个项目所有引用到的类都解析出来了。然后使用使用看看，哦~~~太感动了，功能so强大。前一阵子在唠叨Poseidon For UML又慢又龊，于是乎去网上找了N个UML 开发工具，要么是付费的，要么就是太龊，而Eclipse的UML工具，建模没问题，只是图形开发环境得用最新的Eclipse，更新最新的满麻烦的。

以下这张UML，是我通过选中几个模型之后，自动创建的类图，然后稍加修饰的结果：

总之，Netbeans的UML工具智能化程度已经很高了，可能还不如一些收费工具来的厉害。但作为一款免费的IDE，免费的UML工具，已经是相当相当专业的。Sun不愧是开源的老大啊。

X over SSH

今天又学到一招，用ssh来图形远程登录。原本linux的图形远程登录比较熟悉的是vnc，但这次用ssh登录，比vnc快，而且犹如在本地运行一般。

可以用windows或linux登录有ssh server和x server的linux服务器。理论上，本地需要的是能运行x，及ssh客户端。

详细文档见此：X over SSH - A Tutorial

《为什么时光不能倒流》推荐

终于看完了。我一共参加过三次ACM/ICPC的比赛，另外有一次是在本校组织的地区赛。很幸运，四次都见到了CJ教授，而第五次则是CJ教授到学校里来宣传书的那一次。感觉教授有点嬉皮，很能调节气氛，就这一点算是个满讨人喜欢的教授。

昨天晚上睡不着，有点头疼（疼了有一段日子了），再加上蚊子嗡嗡的折磨，更加令我难以入睡。于是，捧起CJ教授的书，本打算是用作催眠的，却没有想到直到凌晨3点才有意识到太晚了。

《为什么时光不能倒流》宛如一碗鸡汤，滋补着我的心灵。拿到书的第一反应是惊讶CJ教授传奇的人生经历，而后从感动到感悟，每个故事都给了我一个人生的哲学。

今早起床，只睡了6个小时，但却额外精神，头不疼了，咦？真是有点奇怪哈，难道是心灵治愈了，身体就可以自然地治愈么。乘着头还没开始疼，赶快读完了书的剩余部分，确实是被感动了。这是一本适合年轻人，特别是那些儿时还是充满了憧憬和幻想，而现在却是忙忙碌碌，只是忙碌地不再是为了儿时所有的美好愿景的人，停下片刻，细细品味的美味鸡汤。

Stoer-Wagner算法

Stoer-Wagner算法是用来计算无向图的全局最小割的，理论上复杂度可以为O(|E|+|V|log|V|)。我的实现不是最好的，但觉得还行吧。

网友的好文章：最小割Stoer-Wagner算法

题目是百度06年的复赛题，星球大战。可以在POJ上练习，POJ2914。

相关论文和偶的代码，可点此下载。

Stoer-Wagner算法的实现：

#include  <iostream>
#include <algorithm>
using namespace std;

#define initSet(n,Arr) for(int i=0;i<n;++i)Arr[i]=i;
#define MAX 1<<30;
int graph[600][600];

// Stoer-Wagner Algorithm
int globalMinCut(int n){
// A is A set for Stoer-Wagner Algorithm
bool* A=new bool[n];
// V is vertex index
int* V=new int[n];
int* W=new int[n];

initSet(n,V);

int best=MAX;
while(n>1){

//the most tightly connected vertex.
int maxj=1;

// initialize set A and other vertex's weight
A[V[0]] = true;
for(int i=1; i<n; ++i){
 A[V[i]]=false;
 W[i]=graph[V[0]][V[i]];

 if(W[i]>W[maxj])
  maxj=i;
}

// find a min-cut
int prev=0,buf=n;
while(--buf){
 // add it to A
 A[V[maxj]]=true;

 if(buf==1){
  // update min cut
  best=min(best,W[maxj]);

  // merge prev and last vertex
  for(int k=0; k<n; ++k)
   graph[V[k]][V[prev]]=(graph[V[prev]][V[k]]
     +=graph[V[maxj]][V[k]]);
  V[maxj]=V[--n];  
 }
 prev=maxj; 
 maxj=-1;

 // update the weights
 for(int j=1; j<n; ++j)
  if(!A[V[j]]){
   W[j]+=graph[V[prev]][V[j]];
 
   if(maxj<0 || W[j]>W[maxj])
    maxj=j;
  }
}
}

delete[] A;
delete[] V;
delete[] W;
return best;
}


int main(){
// n - vertex number
// m - edge number
int n,m;

while(scanf("%d %d",&n,&m)==2){
memset(graph,0,sizeof(graph)/sizeof(bool));

// v-w is an edge with c weight
int v,w,c;

while(m--){
 scanf("%d %d %d",&v,&w,&c);
 graph[v][w]+=c;
 graph[w][v]+=c;
}

// output min cut
printf("%d\n",globalMinCut(n));
}
}

百度之星2007初赛

HOHO，恭喜恭喜，上大的四人都过初赛啦！ 我，梁老大，沈还有Jackie Yu。我和Jackie两天都做了，沈做了第一天，梁做了第二天。最后沈和梁晋级，我靠第一天晋级，Jackie靠第二天晋级。我第一天拿了30分（题1全过，题2过一半），比期望的低哦，最后的那道SQL本来希望能过两个CASE的，结果全挂了，555，沈也是用暴力解的，但他过了两个CASE，估计是我哪里细节出了问题，导致全错。第二天很郁闷，中午做题果然没晚上精神爽，直打瞌睡。第二天只做了两道（1，4），最后的结果是第1题只对了一个case， -_-b，超级郁闷，后来发现程序里少了两句判断，555，不然第二天也能晋级啦，现在只有9分，不过还好有第一天保底（只是对不住陈胖子了呀）。

题目可以见某网友的帖子，感谢他保留了百度试题：
http://www.ninstein.com/blog/article.asp?id=199
http://www.ninstein.com/blog/article.asp?id=202

其他的题目就不说了，百度有点评（第二天要准备trie的模板呀），我个人对第一天的第四题SQL的SELECT语句比较感兴趣，所以重新做了一遍：

基本上是做了两点的优化（较暴力法），一个是结构上加了索引，二是计算满足条件的几个集合的交集（在结构的基础上优化的求交算法）。

为了说明结构我画了图，还不错吧 ^_^

简单说明一下，该结构完全是为了针对题目而做的，我考虑下，为了实现Delete, Update还需要修正一下结构，而且结构改动后后面的Select算法也要调整。另外，Select是单向的，即只能由条件找出记录号，不能由记录号找出记录的所有信息，要实现的话应该在Record上再加一些变量。不管了，只是针对AND逻辑的嘛。

Table[i][j]的位置不是存放第 i 记录的第 j 字段值，而是存放一个指针，指向下一个与Table[i][j]值相同的记录号，也就是链表结构。索引表存放的才是字段值，对应一个startId是在Table中的第一个拥有该字段值的记录号，即链表的head。

假设，按图中sample有5条记录，0 1 3的c3字段值为a，2 4的c3为b。那么Select c3为a的所有记录，就是在IndexTable中找c3的字段索引，然后找对应的a的startid，得0。然后回表中开始找出所有记录，Table[0][c3]=1, Table[1][c3]=3, Table[3][c3]=-1。-1为终止，于是有 0 1 3 三条记录。

由上可以求出，满足某字段值的一个集合。第二步是求满足多个字段值的一个交集。由于结构本身提供了一个很有利的条件，即若Table[i][j]的字段值等于Table[i][k]且两者均不为-1，则Table[i][j]<table[i][k]当且仅当 j<k，算法描述如下：

（假设满足求n个condition的记录数count=0）
if condition is empty
count=recordNum, exit

准备一个索引数组tb，tb[i]代表 i 条件下的当前记录号。tb初始全-2。
foreach condition as ci
int tmp= IndexTable中ci条件的startid值，无法满足ci，则tmp=-1
if tb[ci] 已存在，即 !=-2
 if tb[ci]!= tmp
     count=0, exit
  else
      next condition
else
  tb[ci]=tmp

依某算法（算法很多，自定吧）取字段c为主键，可以理解为取某个condition为主条件

while tb[c]!=-1
foreach condition as ci
if ci==c
    continue
else
    while tb[ci]<tb[c] && tb[ci]>=0
     tb[ci] = Table[tb[ci]][ci] // next record
    if tb[ci]>tb[c] || tb[ci]==-1
        break;
if all condition matched
count++
else
tb[c]=Table[tb[c]][c]

count is result

复杂度分析： 空间复杂度上是不会亏的啦，字段值没有重复保存过，索引用的都是数字。设记录数n，字段数c，构造DB时的复杂度O(nc)。设某个查询的条件是q条，查询的复杂度min(q,c)+sum(count(qi)) min(q,c)是条件数和字段数取小者，qi表示第i个条件，count是满足i条件的记录数（可以缓存一下的），sum()为求和函数。

其他建议：取主键的算法很多（甚至可以不取，直接假设第一个条件对应的键为主键），可以单纯地用缓存过的满足条件的记录数来决定记录数最少的那个为主键。但对于复杂度不会有提高，因为如果按我上述的算法，复杂度是固定的，主键不影响复杂度。

存在不同主键的情况下会影响复杂度的算法，假设已经求到Table[i]是满足所有条件的记录，那么求下max(Table[i][cj]) cj为每个条件对应的字段，只有最大值对应的记录才有可能为下一条满足所有条件的记录，即使他不是满足所需要的记录，那么只要循着该字段一定能找到真正的下一条满足所有条件的记录。这种跳跃式的算法，可以有效减小复杂度。

缺点：结构只是针对select and做了优化，并没考虑太多，可能会不方便其他操作。优化中将记录标号了，虽然现在大部分表都喜欢加个id，但数据库本意是记录无序的。如我图中所画，DB有许多Table，而只有一个IndexTable，我的想法是一个IndexTable可以管理所有有关联的Table的所有字段，以优化做select and操作。但还没设计完，现在的IndexTable显然是不行的，以后有机会再说吧。

偶的代码（C++），大致实现了上面的结构和算法，测试数据使用MySQL 的sakila sample 的payment表，修正后的数据以及代码点此下载 (放在上大ACM论坛，-_-b荒废好久的论坛啊，只能用来摆摆文件了)：

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <utility>
#include <sstream>
#include <algorithm>
using namespace std;

// DB structs
// first is startId, second is len(len may be tempory used for other target)
typedef pair<int,int> Index;
typedef map<string,Index> FieldIndex;
typedef vector<FieldIndex> IndexTable;
typedef map<string,int> ColumnName;
typedef vector<int> Record;

struct DB{

// a table (since only one table provided)
string name;
vector<Record> records;
int recordNum,columnNum;
ColumnName nameMap;

IndexTable it;

DB(int n,int c):recordNum(n),columnNum(c){
 records.resize(n);
 it.resize(c);
 for(int i=0;i<n;++i){
  records[i].resize(c);
 }
}
};

// Query structs
typedef pair<string,string> Expression;
typedef vector<Expression> Query;

// called while constructing the DB and IndexTable
int addValue(FieldIndex& index, string& value,int curIndex){
map<string,Index>::iterator iter=index.find(value);
int lastIndex=-1;

if(iter==index.end()){
 index[value]=Index(curIndex,curIndex);
}else{
 lastIndex=index[value].second;
 index[value].second=curIndex;
}

return lastIndex;
}

void initDB(DB& db){
string buf;
// parse db name
cin>>db.name;
getline(cin,buf);

// parse column name
getline(cin,buf);
stringstream ss(buf);
string name;
for(int i=0;i<db.columnNum;++i){
 ss>>name;
 db.nameMap[name]=i;
}

// parse db records
for(int i=0;i<db.recordNum;++i){
 getline(cin,buf);
 stringstream ss(buf);

 for(int j=0;j<db.columnNum;++j){
  string value;
  ss>>value;
  db.records[i][j]=-1;
  int lastId=addValue(db.it[j],value,i);
  if(lastId>=0){
   db.records[lastId][j]=i;   
  }
 }
}
}

bool isExpression(string& str){
int len=str.length();
for(int i=0;i<len;++i){
 if(str[i]=='=')return true;
}
return false;
}

bool validChar(char c){
return (c>='0' && c<='9') || (c>='a' && c<='z') || (c>='A' && c<='Z');
}

void parseExpression(string& str, Expression& exp){
int i=0,st=0,len=0;

while(!validChar(str[i]))++i;
st=i;
while(validChar(str[i]))++i;
len=i-st;

exp.first=str.substr(st,len);

while(!validChar(str[i]))++i;
st=i;
while(validChar(str[i]))++i;
len=i-st;

exp.second=str.substr(st,len);
}

int doQuery(DB& db,string& q){
int cnt=0;
stringstream ss(q);
string buf;
Query query;

while(ss>>buf){
 if(isExpression(buf)){
  Expression exp;
  parseExpression(buf,exp);
  query.push_back(exp);
 }
}

if(query.empty())return db.recordNum;

int* tb=new int[db.columnNum];
fill(tb,tb+db.columnNum,-2);
 
for(Query::iterator iter=query.begin(); iter!=query.end(); ++iter){
 int col=db.nameMap[iter->first];
 map<string,Index>::iterator mapIter=db.it[col].find(iter->second);
 if(mapIter!=db.it[col].end()){
  int st=(mapIter->second).first;
  if(tb[col]>=0 && st!=tb[col]){
   return 0;
  }else if(tb[col]<0){
   tb[col]=st;
  }
 }else tb[col]=-1;
}

int lastValue=-1;
while(true){
 int i=0,curValue=-1;
 for(;i<db.columnNum;++i){
  if(tb[i]==-2)continue;
  if(lastValue>=0 && tb[i]==lastValue){
   tb[i]=db.records[tb[i]][i];
  }  
  if(tb[i]==-1)break;  
 
  if(curValue==-1){
   curValue=tb[i];
  }else{   
   while(tb[i]<curValue && tb[i]>=0){
    tb[i]=db.records[tb[i]][i];    
   }
  
   if(tb[i]>curValue || tb[i]<0){
    break;
   }
  }
 }
 lastValue=curValue;
 if(tb[i]==-1 || curValue==-1)break;
 if(i==db.columnNum){
  ++cnt;
 } 
}

delete[] tb;
return cnt;
}

// main entry
int main(){
int c,n,q;
cin>>c>>n>>q;
DB db(n,c);
initDB(db);

string line;
while(q--){
 getline(cin,line);
 cout<<doQuery(db,line)<<endl;
}
}

07年5月29日 在复旦大学的topcoder比赛

先是匹萨，棒约翰的，还不错，我和肖各吃了两块，就饱了，其实是不太好意思吃多 ^_^

然后是比赛，感觉脑子的转速要比在家里做快得多，时间也貌似比一般的一个半小时长得多（因为单位时间的思考能力强了，所以感觉时间就多了）。算是三校联赛吧，被复旦踩是必然的，目标是踩东华。最后338.31，是room2的第7，divsion的第13，还是被两个东华的踩了。

很久没写tc报告了，因为很久不关心算法。但今天还是满有意思的，写一下，纪念一下：

总得来说DIV2的题目就是比较简单的呀。

problem 250:
一个Set包括0-9个数字，其中6和9可以互用，隐含的意思就是可以表示 66 或 99 或 69。
然后给个门牌号，问至少买多少Set能够摆出这个门牌号。

算法很简单，统计一下门牌号中出现过的数字个数。因为6和9可以互用，所以把6的个数和9的个数平均一下，有两个写法：

// method one, after counting
count[6]=count[9]=(count[6]+count[9]+1)/2;  // forget add one will be chanllenged

// method two, in counting iteration
if(count[6]<count[9]) count[6]++;
else count[9]++;

看到两个人用第一种写法忘记+1，cha之~，HOHO，赚100分。

problem 500:
有金G银S铜B三种钱币，去银行转换的规则如下：
11 S -> 1 G
11 B -> 1 S
1 G -> 9 S
1 S -> 9 B
问从G1 S1 B1换到 G2 S2 B2的最少交换次数，或-1表示不可能

与其说是贪心，不如说是逻辑题，只要依存简单的逻辑，就能既保证代码清晰，又可保证准确率：
step 1. 如果B不够，只能用S换B
step 2. 如果G不够，只能用S换G
step 3. B和G都够了，若S不够，先用G换S，再用B换S。因为G换S一次可以满足的S多，所以先G换S。

5555，前面的代码都是好好的，可惜最后在B换S的地方，忘记减去B，加上S了。。。好粗心啊 >.<
一开始沈发现了，但他给的cha数据没能把我cha掉~，洋洋得意地笑沈时，忽然某人把我cha了~ 瞬间郁闷

problem 1000:
比赛的时候想了n套方案，结果还是没能决定用什么方法解之。
题目意思是给出一个序列，要求用最小的cost排序，将i放到某个值后面/前面，花费的cost是i。

大大的程序千奇百怪，有STL库牛人的，有搜索解的，有DP的，不过最欣赏的是这个解法：
可以把问题转换为， 求顺序的最大cost的序列，然后用总cost减一下就行了。

例如sample 中的 6 4 5 3 8 2 7 2 11 2 2，顺序序列可以是 4 5 8 11，也可以是4 5 7 11，对于一个顺序序列，剩余的部分便是待移动的数，为了保证待移动的数的cost尽可能小，就是保证顺序序列的cost尽可能大，所以取 4 5 8 11 的cost和为28，所以只需要用最少52-28=24来完成排序。按照这个思路，有程序：

public int calcMinimalCost(int[] arr){
int total=0,len=arr.length,maxCost=0;
int[] cost=new int[len];

for(int i=0;i<len;++i){
  cost[i]=arr[i];  
  total+=arr[i];

  for(int j=0;j<i;++j){
    if(arr[j]<=arr[i] && cost[j]+arr[i]>cost[i]){
       cost[i]=cost[j]+arr[i];
    }
  }
  maxCost=Math.max(cost[i],maxCost);
}

return total-maxCost;
}

GE海水淡化

GE海水淡化(Desalination)，相当地伟大呀！





http://ge.ecomagination.com/site/index.html#desa

http://ge.ecomagination.com/site/cn/index.html#algiers

Portlet with Ajax Tech (Jetspeed)

I was required to upload a large file via portlet with the process message displaying in the client side, and ajax would be the best choice. In order to ease the job, prototype was included first, so that the Ajax instance would do me a great help.

I've referred so many articles about the ajax application in portal, mostly work for WebSphere Portal rather than Jetspeed, tomcat-based portal. At last, I solved this problem, and as a conclude, I found that the problem could be broken down into three problem:

1. Understanding the principle of the ajax application in portal, JSR-168 would be the most helpful reference. And here is a well-spread diagram to show this principle:
   
   As JSR168 said, portlet session could share the data with servlet session, so render the page via portlet and request the update from servlet, which makes the ajax realizable. Here is the article where the above diagram from.
   


2. Share the data between portlet and servlet. Of cause, there are some applications do not need the servlet and portlet bundled, there would be unnecessary to consider this problem in such cases. But as to my problem, portlet and servlet should bundled together. As the articles I have read, I found it maybe was not a problem for WebSphere, but it's really a problem for tomcat based portal. The solution was so easy, just configure the server.xml like this, I mean to add emptySessionPath="true" attribute:
   

   
   <connector port="8080"
           maxthreads="150" minsparethreads="25" maxsparethreads="75"
           enablelookups="false" redirectport="8443" acceptcount="100"
           connectiontimeout="20000" disableuploadtimeout="true"
           emptysessionpath="true" />
   

   
   And read this article to know what the session identifier do to make such tricky problem.
   


3. Last work is to write the codes and test it. So the last problem is about the coding.
   Most of these coding barriers could be taken easily via careful reading JSR168 Spec. Such as, portlet and servlet share data in APPLICATION_SCOPE, so using APPLICATION_SCOPE to store session. Url and javascript debuging would also cost a lot of time.
   

A good article about Ajax with WebSphere Portal:
http://www-128.ibm.com/developerworks/websphere/library/techarticles/0606_bishop/0606_bishop.html?ca=dgr-lnxw03AjaxPortals

So, it's really fun to work with portal, especially that using the ajax tech to make the portal more vivid. Hope this article help you solve your problem, thanks.