Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
300题纪念,分享下自己的一个思路In Reply To:那位大虾告诉我怎么证明的??? Posted by:xiaoyezi at 2006-07-20 09:08:45 先有一个结论,如果可以相邻两个互换,则所有的可能序列都可以操作出来,不管初态如何。 这一题只能隔一个互换,想像一个互换连一条边: 如果n为奇数,则所有的点形成一个环,任何可能的状态都可以操作出来,当然包括要求的解,输出yes; 如果n位偶数,则所有点形成两个n/2的环(也就是奇数环和偶数环),环内部可以任意,但环间有约束,以白点为对象讨论,首先两个环各自将白点汇集在一起,然后两个环再交错排起来,我们可以发现如果相差大于1,则总有一个白点不能与另一环上的白点相邻。故而有差大于等于2是NO,小于2是yes Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator