从上周四开始我就在折腾系统, 一直到现在, 期间装了两次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%.
今天重新听五月天的倔强: 我就是我自己的神, 在我活的地方
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~
Littleken had been back wuhan last week, but I didn’t meet him in campus. Today we got a BG from littleken. We spent more than 2 hours to play basketball this afternoon, with all the guys tired. Then RanC guide us to a little restaurant for the chicken, it’s very good.
I’m weak now, back for sleep~
写一下习惯的中文, 免得又会忘记怎么写字.
昨晚回去还困的要死, 打了个电话后又兴奋了, 等12点开网络玩, 学校ruijie的时间慢了15min左右, 等的时候看了看硬盘里哪些东西可以删的, 翻出<此间的少年>, 随便看了看. 果然看书还是纸质的好, 电子版的看了什么都不知道, 再看的时候注意了一些细节, 注意了一个叫穆念慈的女生, 那个经常在某人嘴里提到的名字.
也许她真的如同书里的那个女生一样, 很无奈的感觉, 今天很唐突的问了一下这个问题, 感觉和我预想的差不多. 杨康啊, 想不明白为什么就是这样的男生偏偏会有那么好的女子喜欢呢, 难道真的现在是流行有点小邪的男生么?
今晚被拉去看金秋艺术节服饰大赛, 很热闹的场合, 我不喜欢的场合, 看那些流光溢彩, 看那些稀奇古怪, 我还是喜欢朴素的感觉, 所以某人才会说:你一定很喜欢清纯的女生. 还好吧, 她就是那样的吧, 很简单很自然的感觉, 自己也是这样吧, 试过把自己弄的稀奇古怪的, 不过自己都不习惯, 还是简单的好.
穆念慈, 这个角色, 在金庸原版里是一个悲剧, <此间>里也同样是很无奈的一曲, 希望某人不要这样, 生活还是色彩缤纷的. <此间>适合的是故事原型北大, 在武大, 至少我是在本院里感受不到这种氛围的, 也许我只是从来都生活在自己的空间里, 丝毫没管别人的喜怒哀乐. 如果我在<此间>, 我会是谁呢? 可能会像段誉吧, 那个每天趴在窗口等一个身影出线的傻傻的大男生.
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!
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.
%SystemRoot%system32;%SystemRoot%;%SystemRoot%System32Wbem;C:Program FilesJavajdk1.5.0_02bin;C:MinGWbin;C:Program FilesVimvim70
决定今天不用英文, 对Missing这个词的解释还是无法做到用英文表达, 迷失, 思念, 真是敬佩发明这个词的人. 现在就处于这种状态, 迷失自己, 想你, 想家.
一直以为自己已经能很坚强的离开家, 事实上我也在外面过了几年了, 偶尔回去, 但是这一次有超过8个月没回去了吧, 真的还是想家呢. 本来爸爸妈妈说暑假可能会过来玩的, 最后还是没来. 今天接到妈妈的电话, 很开心, 本来都准备打电话回去了. 放假还有接近4个月呢, 亲爱的爸爸妈妈, 我想你们 :)
Missing you, 失去or想念? 这个词曾经不停的以两种用法同时出现, 想你, 如果有超过24个小时没有你的消息, 我会坐立不安, 害怕不知不觉间你就从我的生命里消失.
迷失自己? ACM/ICPC吧, 关于这个, 不知道怎么说好, 最近突然发现自己已经有一种麻木的感觉了, 这样不好, 我需要调整.
以下内容引用自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(x) h(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(p, n)。对于n< 90，c(f, n)可以直接利用动态规划或者限制次数地直接展开f(x)得到。（注意：这个不是c(g,n)！）对于n >= 90，记n = 30 k + r，其中0 <= r < 30，那么根据f(x) = g(x) h(x)，有以下公式
c(f, n) = C(2, k + 2) c(g, r) + C(2, k + 1) c(g, r + 30) + C(2, k) c(g, r + 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中选取最小的即可。