together: Find's Blog

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 »

贴一点冬令营的东西..

2008/1/24

飞机晚到了20分钟. 不管怎么说, 坐飞机里时间比坐教室里过得快多了.

到达绍兴. 一中的老师在机场等着. 想我两次去福州都是自己花五十多块钱打的去的学校 ( fzyz的同学们纷纷举起砖头.. ) 坐机场大巴到绍兴. 找到学校, 又是城市的一角(除了乌鲁木齐, ms所有的城市都将一中设在近郊..)

方便面. 晚上, 开幕式. 两次冬令营, 我竟没有一次占到一个稍微居中的座位, 我在一个极为偏僻的角落里坐下. (所以贴的照片的视角有些..) 不曾想, 一会儿, yy, ghy, twb, cqf相继进来 ( p.s, 顿时会议室里闪出一道令人睁不开眼的亮光 ), 会议室里早已座无虚席, 除了我这偏僻的角落. 于是, 四人并排坐到了我的座位旁. 我担心自己的RP会不会因此番了四番.. 再过一会儿, twb拿出本本开始敲字, 看着bamboo的手指在键盘上流畅的滑动着, 键盘发出一种特别清脆流畅好听的声音, 那个, 看着手指都有些若隐若无的, yz同学, 你看着办吧.

主席作主持, 特意现场更衣( 就是换了件西服 ), 胸前插花, 嘴里附道: “这都照相呢, 打扮下” 刹那间 “咔咔咔咔”, 大家纷纷按动快门, 对得起主席现场更衣的一片心意.

准三星级双人间. NOI要也是这标准, 比赛就是度假.

首先我们要承认noip"难一年水一年"是真理, 今年果然水了. 纵使水了, 我们还是用一个更水的水平答复了它.

第一题, 送分. ms难度还不如matrix67第二基础代码中的"谁是队长2".

第二题, 送分. 如果某位同学像我一样惜内存如金, 因此由于数组超界而挂了几个点, 我真挚地想跟您握手… 我当时干吗要把答案存起来, 不直接输到文件中去呢? 吃饱撑的不行.

第三题, DP. USACO-game简化版+高精度. 由于speed的原因, 我将这一百大胆的扔了, 交了一个空的文件. 当我把第四题做完后, 留下的时间连写个输随机数的程序都不够. 这道题的可惜程度不亚于上一道.

第四题, 乱搞. 我不明白这道题想考我们什么, 乱搞就行了. 硬搞就拿五六个点吧, 优化一下八九个点吧, 您要是比我聪明一点就AC了吧?

人说湖南一等要290+. 靠, 生在湖南我连个省一都拿不上. lsb拿的340跟我哭, 我无言.

觉得应该做一些让生活有些意义的事, 怎么总是一天重复一天, 一天重复一天..

明天就是初赛了, 罗罗的签名告诉大家, 只要有爱, 就能过初赛.

初赛, 一个用于明天不上课的理由, 一个用于今晚不写作业的理由, 然后, 好像就是告诉我们, noip开始了.

还有就是, usaco 十月份月赛开始了, 第一次参加月赛.

标题的意思不是说计算几何是basic but most useful, 是说我学到的几个算法是这样的. 每一次这样的标题下MS都是对CLRS的一次复述. 说句良心话, CLRS实在是一本好书, 一本大好书. 切入正题.

先说凸组合, 设点 p1, p2, p3. 若 p3 = x * p1 + ( 1 – x ) * p2 ( x, y 坐标对就相乘, 0<= x <= 1 ), 则称p3是p1-p2的凸组合. p1-p2 ( 包括p1和p2 ) 是全体p3. 矢量就不说了, 我自己也没完全弄懂它呢. 暂且理解为有向线段, 即有长度限制的射线.

叉积, 我完全是用一次函数推出来的, 它所算的有向面积, 我不明白原理, 或者它只是一个很本质的东西? 就像矩形的面积是长乘高般原始? 不知道, 这些以后再扩充吧. 我的主要目的是弄懂凸包. 三维空间中的一个向量, 这就更不用说了, 不知道.

相对原点p0, p1 和 p2 的叉积公式: p1 * p2 = ( x1 * y2 ) – ( x2 * y1 ) . 当叉积大于零,p1 在 p2 的顺时针方向, 当叉积小于零, p1 在 p2 的逆时针方向. 当它等于零, p0, p1, p2共线. 共线时, 可以用判断p2是否在p0-p1为对角线的矩形中的方法, 判断点是否在一条线段上. Read the rest of this article »