之所以把这两道题放到一起,是因为这两道题是同一种题型,我把它们叫做"穿越题"。解这种题型的题目,关键是要用穿越的思想。一般这种题目,如果不能想进去的话,会感觉无从下手,可一旦想进去,就会发现题目太简单了。
解1852时,关键是要看出,就算两只蚂蚁相遇各自会朝相反方向移动,但如果我们假设相遇的蚂蚁依然能按照原来的方向移动,即它们穿越了对方的身体,这样问题就简单多了,而且,这样的假设,对最后的答案并没有影响。
同样地,在题3684中,我们也可以假设,两个球相互碰撞时,它们也穿越了对方的球体,依然朝着原来的方向运动,这时,我们就可以忽略其他球,把每个球当做一个个独立的球体,它们之间的运动不受其他球的影响,这样问题也就变得很简单了,而且,这样做并不影响最后的结果,不过最后得再对这些球的位置进行一次排序,因为这些球的相对位置关系是固定的。
Read full article from PKU ACM 1852、3684解题报告 | Jorbe's Blog
No comments:
Post a Comment