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

完全不需要分情况考虑奇偶

Posted by 00648057 at 2011-11-08 17:52:29 on Problem 2893 and last updated at 2011-11-08 17:53:25
首先不要删掉0,吧0放在那里。

那么所有可达的状态的S值奇偶性一定是一样的:

S = x0 + y0 + 逆序对个数(包含0)

x0 y0指当前状态的0的坐标

所以最终就是判断

(初始的 x0 + y0 + 逆序对个数) %2   ==  ( m-1 + n-1 + m*n-1 )%2
一句话足够

只要找逆序对别超时就行了

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