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 |
规律的证明In Reply To:Re:其实很简单,看似N复杂 Posted by:gdczcpy at 2010-06-03 01:37:17 > 这规律怎么观察出来的? 观察的确很难,但是证明相当简单。 对任意状态,把所有的堆从大到小排序,设为a[1],a[2],a[3]……,a[n]>0。 首先确定操作最大的一堆a[1]。把a[2]-a[3]个石子放到第3堆,a[4]-a[5]个石子放到第5堆,等等。 如果n是奇数,直接把剩下的石子扔掉。如果n是偶数,最后第一堆留an个石子,其余扔掉。 当n是奇数,扔掉的石子数为a[1]-(a[2]-a[3])-(a[4]-a[5])-……-(a[n-1]-a[n])=a[1]-a[2]+a[3]-a[4]+……+a[n-2]-a[n-1]+a[n]>=a[n]>0,操作必定成功。 当n是偶数,扔掉的石子数为a[1]-(a[2]-a[3])-(a[4]-a[5])-……-a[n]=a[1]-a[2]+a[3]-a[4]+……+a[n-1]-a[n]。操作不成功<=>扔掉的石子数为0<=>a[1]-a[2]=a[3]-a[4]=……=a[n-1]-a[n]=0,即当前已经为必败态。 显然操作成功时能够得到必败态,必败态无法转化为必败态。证毕。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator