frkstyc

点名游戏 (From frkstyc)

发现被 frkstyc 点名了, 早知道就不上他 Blog 溜达了…

规则:

被点到名字的要在自己的博客上写下答案,并且将这几个题目传到其他七个人,还要到这七个人的博客上留言通知对方“你被点名了”。
这七个人要在博客上注明是在哪接到的题目,并且再将题目传给其他七个人,让游戏继续下去,不得回传,被点名的人将得到大家的祝福,并且所有美丽的愿望都会在不久以后得以实现。
问题:

1. 2006你最开心的事是什么?
跟 MM 在一起的时间吧.

2. 2006年最难过的事是什么?
很多吧, 不过自己应该不会去想了

3. 2006冬天最大的心愿是什么?
冬天? ACM/ICPC 完了, 最大愿望就是这个学期成绩能好点, 虽然貌似没太多用了

4. 最大的愿望?
最大的愿望就是我所有合理的愿望都能实现

5. 如果现在可以让你随心所欲去旅行,你想去哪?
回家吧, 家里其实挺好的.

6. 你最满意自己身体哪个部位?与别人初次见面你会先注意他(她)哪个部位?
对自己没什么满意的, 头发比较软算不? 跟别人初次会面我会关心他的言行举止而不是部位, 更多关注别人说话吧

7. 失眠过吗?你用什么办法对抗失眠?
貌似有过, 都是被吵的, 找东西把耳朵捂住基本就好了

8. 会不会做饭?你希望你的伴侣(OR未来的伴侣)会做饭吗?
在家一个人不会让自己饿死, 也仅仅如此而已. 我 MM 会做饭

9. 你最想做哪个动画片角色?为什么?
很久很久没看动画片了, 对角色没太多印象. 机器猫吧, 口袋里有很多好玩的 :)

10. 在你心中我是怎么样一个人?
styc, 嗯. 很强的一个人, 但不是我心中最强的那一拨人

11. 如果可以重来,你最想改变的是什么?
上个学期三门课的成绩

12. 觉得自己是个自恋的人么?
有时候会吧

13. 爱人爱到怎样的程度才算是超过爱自己呢?
没好好想过, 我觉得是不会超过自己的, 爱人等于爱自己吧

14. 你理想的伴侣应该具备什么样的品质?
我想要的我 MM 都做到了, 就那样的

15. 谈谈你最近在听的音乐吧。
有点沧桑的励志的, 合乎现在自己的心态啊

16. 你会出于什么样的理由结婚? 或者出于什么样的理由单身?
结婚? 到时候就自然结婚了吧

17. 你是一个比较平稳的人还是可能作出一些出乎寻常举动的人?
想做出异常举动, 不过一般来说貌似都还比较平稳的

18. 你计划什么时候结婚?(可以给个时间段^_^)
我计划的又不是能决定的, 这个事情要我 MM 说了算

19. 想象一下,十年以后你最珍惜的事物可能会是什么,工作,家庭,朋友,闲暇,学习的机会?
十年以后, 应该会是家庭, 因为我觉得那个时候应该会有自己的小孩子了

20. 人生既有快乐又有痛苦,但是死后一切皆归零,那么我们为什么还会那么忙碌的活着呢?
既然我们已经来到了这个世界上, 那就好好过现在的每一天啊, 对于无法改变的事情, 只能顺应

21. 你们相信自己可以改变一切吗?
我可以改变我能改变的一切, 但是不是一切的一切

22. 你还生活在过去吗?
过去的既然都无法改变, 还活在里面干吗, 现在更多是活在现在偏将来中

23. 爱情中最重要的是什么?
理解一切的理解

24. 道是何物?德又是何物?
道? 想过去解释, 但是从来没能解释清楚. 德? 凡人所推崇的圣人的价值观吧

25. 你对于永远的定义是什么?
永远, 就是比永远更久一点

26. 大四毕业之后你想干什么?最留念的人是谁?如果在南京有同学会,你来吗?
我想读研, 不过事实上很可能是只能去工作了. 留念的, 会是依然在千里之外的 MM. 南京有同学会? 貌似我没那边的同学, 如果在上海工作, 也许会过去玩

27. 你最欣赏我的哪点特质?最讨厌我的哪个方面?
欣赏你的严谨. 没什么讨厌的

28. 06年度你心中最欣赏的人是谁?
没有一个人自始至终的占据这个地位, 目前来说, 选 MagicPig 吧

29. 你最想定居的地方?
想呆南岭中的家乡, 毕竟在那长大, 什么都熟悉, 不过工作时是回不了那的

30. 圣诞怎么过?
平常地过,不反对不提倡的态度。(同意 styc 的, 自己也是这么做的)

31. Ikki的问题:2007年有什么打算?
找个好工作

32. frkstyc的问题:人们为什么要做研究?如果你问同一个问题,你的动机是什么?
研究, 就是让我们继续无限逼近完美, 在任何领域均是如此. 动机? 没什么动机吧, 我要想的想明白了, 想不明白的也都不去想了

33. Snoopy 的问题: 最喜欢的书是什么? 为什么?

点名:Ray@Tongji, cnHawk@TJU, Gardon@HFUT, 在这个圈子找人真是麻烦… 有人做过了我就不想烦他们了, 先这三个吧.

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中选取最小的即可。