never lost, never will.
2008/1/29
周源讲了好多关于生成函数的东西, 没听过叫生成函数的东西,听了半天才发现原来就是母函数.. 比去年讲矩阵的那节课好多了, 至少听懂了不少东西, 我觉得ms这东西数学考试上更实用一些. 下午就去玩, 绍兴一中说天气不好, 原先定的那些地方不去了, 就带我们去城市广场转了一圈就回来了.. 好不爽.. 路上和三位重庆队的同学谈论Matrix67, 开始的话题是谈论gs牛文理兼备, “文科, 理科, 傻傻分不清楚”的杰出才华, 谈着谈着其中一位同学悄然的离开了我们, 跑去和前边绍兴一中的导游MM聊天( 绍兴一中请他们的学生给我们做导游, 名曰: 学生导游. ) 于是我们的话题转移到了matrix67系列情书模拟赛.. 呃, Matrix67牛不会来这里, 对吧?
2008/1/28
今天一天是中国前国家队的表现时间.. cqf以 “ioi我搞的比较差, 排第八, 中国队中最差”作为开场, 讨论了ioi2007的习题, 郭华阳讲了一些关于计算几何的知识, 而杨弋用他精美的flash课件, 向我们系统的介绍了线段树这一数据结构, 并告诉我们, 越是这样简单常用的东西, 在关键时刻越是顶用. 今天的课程非常具有针对性, 好像就没有什么特别一般化的感受. 晚上听到了noi可能会将系统环境换成Ubuntu7.10这一算是激动人心的消息, 学校机子跑Ubuntu比Red Hat爽多了. 讲更新后的评测系统时, 北航的学生们用了好些 “不便公开的技术细节”这类词汇, 听着很像新闻发布会..
2008/1/27
上午是刘汝佳关于 “智能”的讲座. 借用ghy的一句话: “相当意识流”. 截取意识中的片断, 大概写一些有印象的东西.
至少从我参加的这两届Wc上来看, 刘汝佳讲的题目好像很少有一个完美的算法, 或者说, 就是那种经典的, 可以很容易的估计出时间复杂度的算法. 很多题目都是用一些很让人想不到的方法, 而且往往会用在很多题目中使用调整的思想. 这次来冬令营感受最深刻的内容就是调整. 很复杂的一道题目就用这样一种方法很神奇地解决了. 刘汝佳将“智能”划为四部分: 博弈问题, 图像理解, 探路和智能体决策. 说句题外话, 本届Wc找lrj签名成了一种风气..
博弈问题中讲了两道很相似的题目, 就是制定一种攻击策略, 分别在已知敌人位置和未知敌人位置的情况下干掉敌人. 但是方法却完全不一样, 一种是从特殊情况开始分析, 一种情况一种情况的分析, 最终发现在满足某种条件下, 不存在满足题意的策略, 从而完成分析. 可见由特殊到普遍的这样一种思想不仅很有用, 也很需要耐心和冷静. 另一道题是将其转化成网络流的模型, 好像还用了一点调整的思想. 就像这样, 说实话, 听lrj的课两次, 我没有一次明白的听过, 总感觉是在听解题的那样一种感觉而已, 并不知道这道题的算法细节怎么实现之类的. 最大的感受还是从特殊情况开始分析, 让题目的脉络逐渐清晰. Read the rest of this article »
2008/1/26
很荒废的一天. 上午是李学武教授点评noip2007, 因为看过解题报告, 好像就没什么太大的收获..
下午讲的BOI. 从第三题开始睡着了( 这几天很容易睡着, 大概是课程太紧张没休息好 ), 醒来时第四题讲完了. 好好的听懂了三道, 模糊理解一道半, 压根没明白一道. 心里涌起一股做完CEOI十年题目的想法, 回去有付诸于现实的强烈欲望. 嗯, 相信我会好好学习的!!
2008/1/25
上午, 吴文虎, 搜索.
主要讲DFS和BFS. 吴老师讲课时从不会拿很难的东西吓我们. 很基础的DFS, 非常详细的展示了一道用DFS解决的题目的思想过程, 以及如何剪枝. 又一次引入了与结点和或结点, 感觉或节点就是if语句, 与结点就是顺序的语句. 按吴老师的话, 这是用图示的直观性帮助思维. 印象最深的一句话: 问题要从简单到复杂, 从特例到一般, 我好像就是少这样一种思考问题的方法. BFS讲了USACO上那道亚瑟王, 最终得出这样一个结论, 这是一类这样的题目: 正确的作法显而易见, 却又很难证明. 吴老师在学生间走动时, 忽然把话筒递给了我, 我首次, 第一次, 史无前例的一次, 在国家级比赛活动的站起来发言, 尽管是被人点起来的, 但毕竟是起来了, 写下纪念. 至于我的发言, 自然是像我本人一样没有水平, 好像就是把前前一位同学的发言重复了一遍( 但, 这道题我就是这么做的, 我也不明白为什么这样就对 ). 然后讲了递归, 强调递归在计算机算法中的重要性, 提了两道题, 一道是著名的青蛙过河, 另一道是同样著名的汉诺塔问题. 汉诺塔问题的一般情况我明白. 但是又提出如果有N个盘子, M个柱子( M >= 3 )时, 怎么解决汉诺塔问题. 解法是DP+递归. 方程 f[ i ][ j ] = f[ i – k ][ j ] + f[ k ][ j – 1 ] + f[ i – k ][ j ], 其中f[ i ][ j ]表示有i个盘子j个柱子时至少需要多少次移动才可以将所有盘子从A盘移动到B盘. Read the rest of this article »