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 new_star at 2008-12-22 16:20:46 on Problem 2605
分析
根据样例说明,每次跳动时必须是隔着相邻的子。

如下研究某些模型
[1]研究规模不大于3*3的模型发现
   如果规定行数n不大于列数m,则当m小于3时,必剩余(m+1)/2个

   并且在的研究中发现两个特殊的模型
   变换1
   xxxx ->xx__-> xx__->__x_->_xx_->x___->...
   xxxx   xx__   xx__  xx__  x___  x___
               xx    x     x

   变换2
   xxx->xx_ ->xx_->xxx->...
   xxx  xx_   __x  ___  
          x     x


  变换1和变换2的等价情况
  xxxx <==>xxxx<==>_xxx
  xxxx     _xxx    xxxx

  xxx <==> __x<==>x__
  xxx      xxx    xxx

[2]研究规模大于3*3的模型(规定行数不大于列数)
   发现结合变换1和变换2,可以消去边界上行数大于1的连续3列
   每次消去后要确保行数不大于列数,否则将矩阵转置
   这样连续消去可以递归到3*3规模以下的解

   但是有一个特殊的规模4*4,不能这样消去列
   xxxx->xxxx->xx__->xx__->__x_->____->____->____->____
   xxxx  xxxx  xx__  xx__  __x_  ____  x___  x___  ____
   xxxx  x___  x_xx  xx__  xx__  xxx_  _xx_  x___  ____
   xxxx  x___  x___  x___  x___  x___  ____  ____  x___

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