36 hours early we got off from Z11, and with no medal, although there is two copper, but in my eyes, they are nothing.
We’ve hoped to win a qualification to the final, but at last only a copper, with too many stupid mistake. I still don’t know why we didn’t code the H, sigh.
Hope for Shanghai, hope that won’t be my last show. Good Luck, we are the Moonmist, we are the future.
Nov. 9th
武昌 Z12 到北京西, 晚上 20:49 发车, 离开武汉.
Wish our Moonmist, wish DeathDecay, wish our WHUACM.
Nov. 10th
早上 7:14 Z12 到达北京西, 去清华园, 报到, 安排住宿. 也许我们会去 Google 玩, 看看所谓的极尽奢华, 看看那个万人追捧但是我觉得越来越只是个伪图腾的 KaifuLee.
Nov. 11th
上午教练会, 下午我们会去试机, 记得看看 vim 的配置, 记得改好 gEdit 的显示, 记得看看 long long 等乱七八糟的细节问题, 还有键盘. Java Challenge, 可以考虑玩玩 :P
Nov. 12th
正赛, 没什么好说的, 好好发挥就是了, 希望晚上我们能是获得最多闪光灯的队伍, 希望我们是笑的最灿烂的队伍.
Nov. 13th
准备归程, 一天的空闲时间说不定还是 WHU 的保留节目去故宫玩. 晚上 20:49 北京西 Z11 回武汉.
This Thursday evening we will travel to Beijing, then we need to do a extra work on this weekend. Tsinghua offered 10 Gold, 15 Silver, 20 Copper medals for the teams, more than Chengdu and Hangzhou last year, and less than Beijing last year, but I think that’s enough, and we’d better to win a Gold medal to prove us, and prove our Wuhan Univ. be strong. For Fudan Univ. got the qualification to the Final on Dhaka, Peking Univ. and Sun Yat-Sen(ZhongShan) Univ. got the qualification on Seoul, Shanghai Jiao Tong Univ. got the qualification on Yokohama, there is no more teams need to get the qualification, and according to the new rules, Tsinghua can’t join in the contest on their own site, I agree that if a team can get a Gold on this weekend then they’ll get the qualification, there is a chance for us, fighting for it~
今天做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%.
今天重新听五月天的倔强: 我就是我自己的神, 在我活的地方
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~
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.
以下内容引用自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中选取最小的即可。
This afternoon we did a practice with yzf, but all the three team failed, sigh~
Problems from NordicCPC2005, one of my favorite regional, I typed the first 4 code, then helped moon to finished our 5th code, we kept silence in the middle, which makes us looks like a second-class team. We failed on the Problem B, a Min-Max game, which should be a part of my knowledge architectonic, but which makes me unacceptable is that yzf used a greedy algorithm to solved it.
We need a long way to go, to be a first-class team. We are the Moonmist~
Gardon asked me to produce a problem for his own contest a weed ago, which contest celebrate for his remove. I make the problem that can be solved by a dynamic programming, which is my favorite recently, and used half a hour to write the standard code and the program to generate data. But when I asked flymouse to check the data he said that I make the problem hard to understand, I explained a minutes then decide to give up, replaced to rewrite the problem by English, maybe English is more understandable.