Month: 10月 2006

崩溃

从上周四开始我就在折腾系统, 一直到现在, 期间装了两次Solaris, 一次失败, 然后发现不会用也不好用(我要能快速上手), 用虚拟机装Fedora Coer 6, 编译系统的时候因为libtool的问题无法继续(怀疑是1.3.x跟1.4.x/1.5.x的兼容问题), 放弃后用Ubuntu, 与Ubuntu奇怪的更新方式斗争了n久之后搞定Apache和php, 编译系统的时候gcc版本问题(4.0的要求更严格), 重新定义到3.4, 现在的问题是为灭一个leonlux不需要编译的东西我要编译… cashcat写的那个用户排名的程序, extrafun.c, 引用的bbs.h在那个目录下根本找不到, 并且从那个目录的名字fb2k2smth来看, 似乎也是老系统的东西, 就卡在这里动不了了, ll也不理我了 :(

今天中午接到通知, 开始准备入党的材料, 一份2000字的申请, 一份5000字的自传, 四份1500字的思想汇报, 以及其他种种材料若干, 初步估算我要写15000字, 现在完成的只有自传, 就差最后一点了. 要求下个周二交… omg

还是要坚持唯心论的

今天做timus, NEERC, Eastern Subregion, Yekaterinburg, 算是Moonmist很失败的比赛了吧. 开场10分钟有人过4题, 而我却看错简单题题目意思白白WA了一次, 然后是另一个简单题直接没看懂意思, 让Moon去写又慢了很多. G自己一直觉得很迷惑, 那个Sample… 但是自己一直没去怀疑Sample是错的, 还是努力的去理解俄式英语, 同时刷页面期待有更正, 到1个半小时并且错了2次(其中一次是完全理解错误)后才AC, 太失败了.

现在已经很少去怀疑数据了, 特别是像今天这种根本对题意没理解的情况下, 因为看不明白英语在说什么, 只能从Sample上去理解题意了, 结果还是很郁闷. 周四的Romania2006, 那个C, 错的也太那个什么了, 差点跟DC吵起来. 后来到了89min的时候KO觉得很奇怪再看了一下数据发现前面还有个case_total, 不然还是有问题的, 其实前面两次错的都一样, 我的唯心论还是对的. 那个并查集的, 自己对tank的程序已经几乎优化到极限了还是TLE, PC^2提问DC也不理, 最后还是KO给ReJudge发现已经过了, 2s多, 比tank的快了5s左右.

我要重新唯心起来, 这样才会有那种舍我其谁的霸气, 才会让80%的实力发挥到120%.
今天重新听五月天的倔强: 我就是我自己的神, 在我活的地方

To Be A Good Manager

It’s time to do something for our BBS, the LuoJiaShanShui.

Last summer the SYSOP asked me to be a manager of the system, I accepted directly, but since then I did nothing as a manager. The reason is I didn’t know what to do, and didn’t know how to, just because they considered me as a good coder so maybe I’ll be a good manager. Actually I’m a newbie, and want to learn how to do from leonlux. As there is no time for me to do anything except coding during the summer, I did nothing with it, now they all want me to do something or drop out. I’m shamed on that point, so tried to add a little function. But this noon I found that there is a bug makes other more discomforts, then with leonlux’s help, I fixed it up in a minutes, but still makes it unstable in others’ eyes, sigh~

穆念慈/此间的少年

写一下习惯的中文, 免得又会忘记怎么写字.

昨晚回去还困的要死, 打了个电话后又兴奋了, 等12点开网络玩, 学校ruijie的时间慢了15min左右, 等的时候看了看硬盘里哪些东西可以删的, 翻出<此间的少年>, 随便看了看. 果然看书还是纸质的好, 电子版的看了什么都不知道, 再看的时候注意了一些细节, 注意了一个叫穆念慈的女生, 那个经常在某人嘴里提到的名字.

也许她真的如同书里的那个女生一样, 很无奈的感觉, 今天很唐突的问了一下这个问题, 感觉和我预想的差不多. 杨康啊, 想不明白为什么就是这样的男生偏偏会有那么好的女子喜欢呢, 难道真的现在是流行有点小邪的男生么?

今晚被拉去看金秋艺术节服饰大赛, 很热闹的场合, 我不喜欢的场合, 看那些流光溢彩, 看那些稀奇古怪, 我还是喜欢朴素的感觉, 所以某人才会说:你一定很喜欢清纯的女生. 还好吧, 她就是那样的吧, 很简单很自然的感觉, 自己也是这样吧, 试过把自己弄的稀奇古怪的, 不过自己都不习惯, 还是简单的好.

穆念慈, 这个角色, 在金庸原版里是一个悲剧, <此间>里也同样是很无奈的一曲, 希望某人不要这样, 生活还是色彩缤纷的. <此间>适合的是故事原型北大, 在武大, 至少我是在本院里感受不到这种氛围的, 也许我只是从来都生活在自己的空间里, 丝毫没管别人的喜怒哀乐. 如果我在<此间>, 我会是谁呢? 可能会像段誉吧, 那个每天趴在窗口等一个身影出线的傻傻的大男生.

Oct.21th, Preliminary of Shanghai

Shanghai Univ. did a lot of work on the OnlineJudge System, but there is still many bugs, because so many team tried to submit and refresh the page, but Shanghai Univ. did a lot of remedies to fix it, by delayed a hour to finish, all the contestants praised the hard work of repair.

I updated my signing messages before the contest, said "Oct.21th, Wuhan, Sunny, Wish our Moonmist, Wish our WHUACM~", then updated it with "Oct.21th, Rainy, We got 7/35 Accept and got a ticket to Shanghai~". It’s the day we have a good job, I’ve got 5 AC of our team’s, with many fearless guesses, they all thought that I must crazy, but actually I’m right :P

We’ll have two teams to Shanghai on November, wish our Moonmist and Silence, we are the best!

Good Luck for This Weekend

I’ve received the invitation from Tsinghua University yesterday, and filled the table to check. We have two team to join the on site contest, our Moonmist and the DeathDecay, good luck, wish them win a prize on Nov.12th.

Preliminary contest of Shanghai will be taken on this weekend, but it looks like there is still many bugs on the OJ of Shanghai University, wish them to fix them up before the preliminary. We’ll win a ticket to Shanghai by a good standing, Nov.22th, we’ll see Moonmist and Silence on Shanghai.

Windows下使用gVIM工作

前面有一个_vimrc的文件说明, 用了几天还是有一些小修补更改了一些小细节使得使用更加顺手, 这次一起写一下gVIM的全部安装, 方便大众, 推广vim :P
1.要使用的软件描叙
  1.1 环境为WindowsXP SP2 + gVIM7.0 + vimdoc1.5.0sc + MinGW3.0.0.1, 各软件的下载直接点前面的链接.
  1.2 gVIM7.0就是我们要介绍的主角啦, 完美的编辑器, 任何赞美加在这个几十年历史并且还依然青春依旧的艺术品上都不为过的.
  1.3 vimdoc1.5.0sc是VIM中文帮助文档, 别以为跟Windows下那些无聊的软件帮助一样, 这个才叫帮助, 对不管新手还是老鸟的完美指导参考帮助, 感谢国内无私的译者让我们享用.
  1.4 MinGW3.0.0.1是GNU标准的各个编译器集合, 有更新的版本, 但是似乎这个版本更加通用, 我只是用这个编译C/C++文件.
2.软件安装
  2.1 gVIM, 没什么好说的, 一路next就好了. 装好后需要对其进行必要的配置从而更符合我们的使用习惯, 配置方法在后面一部分详细介绍, 如果想在命令行下能直接唤出gVIM, 可以把安装目录下的vim70文件夹加入到系统环境变量中.
  2.2 vimdoc, 也没什么好说的, 一路next搞定. 如果嫌麻烦可以在安装时把 [安装完成后显示帮助] 的钩去掉.
  2.3 MinGW, 安装到默认目录下, 切记, 如果不这样会出问题, 对Eclipse可能会有影响. 安装完成后将MinGW下的bin目录添加到系统环境变量中, 如果没有一个g++.exe文件则将mingw32-g++.exe改名为g++.exe, 如果使用Eclipse, 推荐将mingw32-make.exe也改名为make.exe.
  2.4 环境变量配置. 桌面上打开[我的电脑], 选[属性], 选[高级]标签页, 点开下面的[环境变量], 双击下面系统变量中的Path, 要加入的就是在原始的后面加;和要添加的目录了, 比如我的在装了JDK和MinGW以及gVIM后(均为默认目录)的环境变量为

%SystemRoot%system32;%SystemRoot%;%SystemRoot%System32Wbem;C:Program FilesJavajdk1.5.0_02bin;C:MinGWbin;C:Program FilesVimvim70
3. vim配置
  3.1 配置vim就是配置安装目录下的_vimrc文件(Windows下, Linux下是用户自己的根目录下的.vimrc), 有时候这个文件会出现在C:Documents and Settings当前用户名下, 很奇怪, 我在实验室和宿舍的机器位置就不一样.
  3.2 关于此配置文件, 网络上有很多样例, 比较推荐的有下面链接给的,有英文注释,上面一个是彩色高亮的,下面一个是纯文本的. 可以通过这个文件来学习一下vim的详细配置. 不过事实上能用到的远远没有这么多, 这个只是一个比较完全的, 我只是看懂了里面的一些直接用户界面有关的东西, 更详细的跟Windows的沟通部分没明白…
http://www.vi-improved.org/vimrc.php
http://www.vi-improved.org/_vimrc
  3.3 vimrc里面注释是以 ” 开始到行末尾, 注意这一点, 其他的都没什么.
  3.4 点击_vimrc打开我给出的一个有详细解释的说明, 或点击_vimrc.rar下载我打包的配置文件, 可以根据自己喜好来改动, 如果不熟悉可以先拷贝到指定位置, 然后重新用gVIM打开来慢慢调整.
4. 使用
  4.1 使用没什么好说的, 如果需要VIM的使用指南, 看看安装后提供的新手入门就能在30分钟内被手把手教会常用的功能了, 然后就可以跟用一般的编辑器一样了, 只是注意, 你用的是gVIM, 你可以在使用中不断发现很多奇妙的地方的, 并且可以通过帮助文件来获得更高级的使用方法.
  4.2 快速编译. 安装MinGW就是为了编译C/C++, 我的配置文件里面加入了几个快捷键来快速实现, 均在命令模式下有效, 详细的可以看_vimrc文件里面的map部分, 简单来说F2是保存(w), F3是保存退出(wq), F10是编译(!g++ -o %< %), F11是运行(!%<).

Missing

决定今天不用英文, 对Missing这个词的解释还是无法做到用英文表达, 迷失, 思念, 真是敬佩发明这个词的人. 现在就处于这种状态, 迷失自己, 想你, 想家.

一直以为自己已经能很坚强的离开家, 事实上我也在外面过了几年了, 偶尔回去, 但是这一次有超过8个月没回去了吧, 真的还是想家呢. 本来爸爸妈妈说暑假可能会过来玩的, 最后还是没来. 今天接到妈妈的电话, 很开心, 本来都准备打电话回去了. 放假还有接近4个月呢, 亲爱的爸爸妈妈, 我想你们 :)

Missing you, 失去or想念? 这个词曾经不停的以两种用法同时出现, 想你, 如果有超过24个小时没有你的消息, 我会坐立不安, 害怕不知不觉间你就从我的生命里消失.

迷失自己? ACM/ICPC吧, 关于这个, 不知道怎么说好, 最近突然发现自己已经有一种麻木的感觉了, 这样不好, 我需要调整.

NWERC 2005 Unequalled Consumption

以下内容引用自frkstyc’s Blog, 原文地址:
http://www.blog.edu.cn/user2/frkstyc/archives/2006/1180760.shtml

——————————————————-我是分隔线——————————————————

有人曾经在POJ webboard上声称生成函数是“没用的东西”。但这个题却是利用生成函数解决问题的一个很好的例子。

题目的大意是有不超过5种重量在10以内的糖果(不同的糖果可以有相同重量),给一个整数P<= 1015,要求一个最小的重量w,只得做一个重量为w的糖果盒的不同方法数至少是P

看到P的规模就可以立即否决普通的动态规划解法。容易联想到的算法是二分法,但这个题乍看之下没有明显的单调性。尝试用生成函数解决。为描述方便,以下直接用一个实例来说明。

假设有3种糖果,重量分别为2, 3, 5。用生成函数中xn项的系数表示做重量为n的糖果盒的方法数,那么对应的生成函数就是

f(x) = 1 / ((1 – x2)(1 – x3)(1 – x5))。

这个形式是没有办法直接利用的,因为里面三个因子的展开式都有无穷项,要直接找系数的通项公式也不容易。但是利用一个很简单的技巧就可以解决这两个问题。(应当说明,这个技巧虽然看起来很简单,但的确是要费一番思考的。)注意到2, 3, 5的最小公倍数[2, 3, 5] = 30,因此将上面的式子改写一下,变成

g(x) = ((1 – x30) / (1 – x2)) ((1 – x30) / (1 – x3)) ((1 – x30) / (1 – x5)),
h(x) = 1 / (1 – x30)3,
f(x) = g(xh(x)。

这样,g(x)是一个一般的多项式,h(x)虽然有无穷项但形式很规整,f(x)只是g(x)和h(x)的乘积。

g(x)只需直接展开即可,展开的结果是一个次数小于3 * 30 = 90次的多项式。对于h(x),为方便起见,作一个换元,记

h’(y) = 1 / (1 – y)3。

通过计算或者查阅工具书可以知道h’(y)中yn项的系数为组合数C(3 – 1, n + 3 – 1),其中的3就是h’(y)的解析式中1 – y的次数。因此h(x)中x30 n的次数也是C(3 – 1, n + 3 – 1),而其他项的系数都是0。

综合上面的讨论,可以得到计算f(x)中xn项的系数的方法。记p(x)中xn项的系数为c(pn)。对于n< 90,c(fn)可以直接利用动态规划或者限制次数地直接展开f(x)得到。(注意:这个不是c(g,n)!)对于n >= 90,记n = 30 k + r,其中0 <= r < 30,那么根据f(x) = g(xh(x),有以下公式

c(fn) = C(2, k + 2) c(gr) + C(2, k + 1) c(gr + 30) + C(2,  kc(gr + 60)。

f(x)直接相关的计算已经基本解决。剩下求最小的问题,方法还是二分法。虽然从整体看,c(f,n)关于n不一定是单调的,但是假如把n写成n = 90 k + r,其中0 <= r < 90,就可以发现对固定的r,c(f, 90 k + r)关于k是单调的。因此只需枚举r,对k应用二分法,然后从所有候选的n = 90k + r中选取最小的即可。