Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

300题纪念,分享下自己的一个思路

Posted by treert at 2012-07-09 17:13:30 on Problem 1063
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator