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 |
Re:那位大虾告诉我怎么证明的???In Reply To:那位大虾告诉我怎么证明的??? Posted by:xiaoyezi at 2006-07-20 09:08:45 依题意我们可以想成disks不动,而是turnstile capable可以向左循环移动,并作flip操作, 我们给disks编号。 这样的话相当于即我们可以把某个disk循环左移或右移偶数的距离,该操作只影响路径上与该点距离为偶数的点的位置,但不影响他们位置的奇偶性(产生循环的那次移动除外)。 如果编号奇数的个数和编号偶数的个数相差不超过1的话,一定可以聚在一起的: 随便假设一个地方为集中区域,那么只要按集合位置从中间到两边的顺序依次把不在集合位置的disks插入对应的位置即可。从中间到两边的顺序是为了保证后面的操作不会影响前面已经集中好的disks的位置。 如果n是奇数的时候,任意位置,一定可以从某个位置循环左移或右移偶数的距离到达。即编号奇数的个数和编号偶数的个数可以改变,n是偶数时则无法改变。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator