-problem: 100个人站成一排, 各自有各自的价值, 相邻之间可以比赛, 输的出去, 直到剩下一个, 给你一个矩阵i行j列为1表示i能赢j. 随你安排比赛顺序, 问最后留下的价值最大为多少. solution: dp, not floyd! --source: 2010 ACM-ICPC Multi-University Training Contest（19）——Host by HDU ----link: http://acm.hdu.edu.cn/showproblem.php?pid=3632 ----code: http://goo.gl/zFO7
Helanic Abyss
I am the answer.
{HDU}{3632}{A Captivating Match}
Next Station: CAD&CG of ZJU
浙大玉泉的大门很高, 我抬头看了一眼, 没有拍照, 就进去了, 似乎还有点当年刚进华理时的感觉, 感叹自己的卑微和渺小.
29号杭州下着雨, 不远处的山上腾着雾气, 朦朦胧胧, 我一直以为杭州位于平原上来着, 而且公交车上因为晕车的缘故一直低着头, 下车的时候看见周围都是山, 吃了一惊.
国际交流大楼上的招待所单间没有了, 于是要了180的双人间, 于是移动硬盘里的毛片就充当了另一张床上的角色:P
CAD&CG实验室所在的教一很古老的样子, 进去boss的办公室的时候看见了阳台, 突然想起了爷爷家的老房子. boss比想象中的矮一点, 比想象中的随和很多. 交谈的内容集中在他的课题, 读博的辛苦, 以及我做过的相关工作. 其间我有一下子停了他说了很多他们课题组的东西, 不知道说什么好了, 于是摩挲了一下书包, 很二的说了一句: “呃…我不知道说什么了.”, 最后有个同学进来让boss看他们的东西时我才想起来给boss演示一下我们大学生创新实践的作品, 功能很不全, 很多算法上实现好的东西没有用Ogre的GUI做出来, 感觉有点炯, 而且有点紧张, 连IK也忘记演示了. 不过面谈过程总的来说还是挺融洽的, 毕竟我对这方面有兴趣而且又做过相关的东西. 结束的时候boss说今年有3个人报了他的博士, 原则上只能接收两个, 然后口头上说把一个名额给我了, 我傻愣愣的, 竟然忘记说两句感谢的话就说再见了…
29号晚上从7点开始睡了整整12小时.
今天早上的学院面试异常轻松, 来8个取8个. 当然结果出来之前大家还是挺紧张的, 事先不知道会不会刷人. 两个大连理工, 两个西北工业, 一个华科, 一个西电的女生, 其余两个不知道. 7个人英文部分都是自我介绍, 唯独我被问了对杭州的印象…昨天下了一天的雨, 不是我想窝在宾馆里看毛片, 是老天逼我的…于是我支支吾吾地说了什么下火车以后鞋子wet了, 下汽车以后看见很多山, 印象里杭州应该是flat的, 然后看见有云twist around(不知道萦绕怎么说)山…然后是在挤不出跟风景相关的单词了, 就来了句”that’s all, thank you”. 然后说项目经验, 当我说到10天5000行代码实现带有相关子查询的DBMS的时候, 一位老师对另一位重复了一遍10天5000行的时候, 我再一次欣喜地感觉到连着的两天通宵没白花. 有意思的是中间的那位老师是DCD实验室的, 也是做人体运动什么的, 就跟我聊起了DTW算法, 我跟他说了我们在找时间配准起点的时候遇到的问题. 最后问到社会工作的时候我想说大一的时候做过, 不知道为什么开口就扯到了插班生的事情, 也许考插班生这件事对于我来说就是跟社会工作决裂的分界点, 所以就本能地说出来了. 结果最右边的老师开始质疑我考插班生是不是凭关系进去的. 我当时就蒙了, 只是简单地说了句没有, 后来想想, 为什么我不回他一句”请看看我的专业排名”呢? 结束以后取拟接收函的时候瞄了一眼面试分数统计, 看到前6个人, 貌似我是最高的.
浙大的直博竞争远没有华理推外名额的竞争来得激烈. 可能没有计算所的激烈(一想到初审就被刷了, 我就一肚子不爽…). 大家都不愿意花5年时间积累10000小时, 那我就去试试好了, 反正我也就是这么一路尝试过来, 并且看起来一路交了好运.
也许就像Cortana在Halo3第一章里的旁白:
They let me pick, did I ever tell you that? …choose whichever Spartan I wanted.
You know me. I did my research. Watched as you became the soldier we needed you to be.
Like the others, you were strong and swift and brave. A natural leader.
But you had something they didn’t. Something no one saw…
…but me.
Can you guess?
Luck.
Was I wrong?
或者就像[Outliers]里所说的:
The professional hockey player starts out a little bit better than his peers. And that little difference leads to an opportunity that makes that difference a bit bigger, and that edge in turn leads to another opportunity, which makes the initially small difference bigger still—and on and on until the hockey player is a genuine outlier. But he didn’t start out an out lier. He started out just a little bit better.
{SCU}{3777}{Ensure no absence}
-problem: 3000点20000边的无向图上以1, 2, 3分别为起点, 找若干终点t, 使得任意两起点到t的所有最短路没有公共边. solution: dijkstra, 判终点前驱是否有交集 ----link: http://cs.scu.edu.cn/soj/problem.action?id=3777 ----code: http://goo.gl/Ci5m
{SCU}{3774}{B-number}
-problem: 1~1000000000有多少个数以13为字串且可以被13整除. solution: DP ----link: http://cs.scu.edu.cn/soj/problem.action?id=3774 ----code: http://goo.gl/DoXD
Typeclass & CRTP & boost::operators
今天把Haskell的Typeclass Eq和Ord在C++中用CRTP做了个简单的实现, 写完了才想起来boost里也有类似的(更强大)实现.
Dream Control
看了Science America的一篇关于怎样控制梦的文章, 虽然很多内容大抵早就知道了, 不过还是有几条挺好玩的.
仅仅关于控制自己的梦, 大致有几点比较有意思:
- 想梦见什么, 或者想在梦中解题(梦中的想法通常没什么逻辑性, 所以也不是什么题目都合适), 方法似乎只有睡前不断想, 最好在床边放上照片或者字条什么的.
- 醒的时候不能马上起来, 否则会忘记.
- 想知道自己在做梦(lucid-dream), 方法除了睡前自我暗示(告诉自己自己可以控制梦境), 睡多点(貌似是废话)以外, 还可以在梦中做判断, 有两种判断比较奏效:
- 在梦中阅读. 梦中阅读的时候通常看不清字, 或者句子意义不明.
- 在梦中拨开关什么的, 比如灯. 在梦中通常这些开关都坏了.
- 在lucid-dream里解题很低效.
{ZJU}{3296}{Connecting the Segments}
-problem: 给你一个长度不大于50000的串, 问它最少可以由多少个回文子串拼接而成, 子串可以重叠. solution: 原串拼接反转串后构造后缀数组, RMQ预处理height数组, 再预处理出以i为首的最长回文子串长度, 然后贪心. ----link: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3671 ----code: https://docs.google.com/document/pub?id=1V2_nl-QEyeBW8PODGwwdVXTABTTmoineOnBo2H2gT_Q
{Ural}{1092}{Transversal}
-problem: 一个(2n+1)*(2n+1)的网格, n< =20, 里面是'+'或'-'. 每次可以同时翻转2n+1个格子, 使'+'变成'-'或者反之, 要求这2n+1个格子的行, 列都不相同. 现在要你输出翻转步骤, 使得最后'+'的数量不超过2n. solution: 贪心. 关键是如何用两次操作翻转一个矩形的4个角. ----link: http://acm.timus.ru/problem.aspx?space=1&num=1092 ----code: https://docs.google.com/document/pub?id=1sEOzqZiI9kz-qBkkSjblq9_PafP8xCg2rrhw17CKGD0
德国馆需要排4个小时的队吗?
今天去世博会. 上午10:20到的德国馆. 看见队尾的牌子上写着4小时, 心里有点凉, 但是因为决定今天一定要看德国馆的, 所以就排了.
大概过了一个大棚的时间, 感觉人流前进的速度还是挺快的, 感觉用不到2小时, 但具体要多少却说不清. 想起来前一阵子看的[编程珠玑]上的little定律, 就试着估算了一下时间.
little定律大概是这么个意思:
队列中物体的平均数量为进入速率与平均滞留时间的乘积.
我是这么估算的:
每个大棚有11根支柱, 每两根支柱之间间隔2.5m, 所以每条走道长25m.
每1m长的走道里有大概5人, 所以每条走道里有约125人. 每个大棚里有4条走道, 一共9个大棚, 加上外面的人算有10个大棚, 这样总共大概有5000人.
走完一条走道需要将近3分钟, 所以人流量0.7人/s.
根据little定律需要5000/0.7s, 大约2个小时.
事实上我们用了2小时10分钟. 于是之后我又算了一下意大利馆大概需要排40分钟, 于是就去了.
事实证明little定律还是挺靠谱的.
顺便一提, 意大利馆非常赞!