loonsw's Tech Blog

Algorithm, Mathematics, C/C++, GNU/Linux, Emacs/Vim…

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  6 随笔 :: 1 文章 :: 0 评论 :: 0 Trackbacks
如何剥离出问题的表象后抽象出问题的本质,是解决问题所必需具备的能力。
拿做过的一些题目来看:ZJU1028Flip and Shift,大意是指给定密闭椭圆环,内有若干黑白球,问能否通过flip和shift操作使得黑白球分开。
分析这个问题,可以认为一系列的flip和shift操作就是移动某个球,这样我们可以着眼于一个球,接下来,我们会注意到球的总数是奇数还是偶数是对球的移动有影响的,当球总数为奇数时,任意球可以通过一些列的操作后到达任意位置,但是总数为偶数时候,则有相应的变化,因为此时无论怎样操作,球位置的奇偶性是不会发生改变的,所以我们可以得到结论:当球的数目为奇数的时候,我们总是可以通过一系列的操作得到我们想要的结果;当球的数目为偶数时,不是一般性,我们考虑黑球,则必须要黑球奇数位置球和偶数位置球的个数差不大于2。有了上面的分析并得到结论后,代码变的很简单。当然这道题目我们仍然可以使用DP或者BFS的方法求解,但是效率是极低的。
另外一道很有意思的题目是Ural的1639. Chocolate 2题意是给定大小m×n的巧克力,两人轮流掰这块巧克力或它已经掰开的部分,直至不能掰者输掉游戏。对于这道题目,如果从使用博弈搜索,那么肯定效率是非常低的。实际上,我们分析掰巧克力这个过程,在每掰一次的过程中,我们的巧克力“碎片”数目是只增加1的,这点很重要,而我们最后得到的集合里面有m×n小块巧克力,这可以证明我们实际上掰的次数是一个常数:m×n-1,那么这个问题又变得出乎简单了。
上面的两个小例子说明了分析问题抽象出本质的重要性,有些时候,这样的思考可以对问题的理解产生质的变化。
posted on 2008-11-26 21:35 redcode 阅读(112) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理