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 KatrineYang at 2016-05-25 01:25:04 on Problem 1067 and last updated at 2016-05-25 01:31:05
首先挫败状态的线性规律很好找。。但是并没有什么用...
然后就发现了几组比较刺眼的数据 (1,2)(3,5)(8,13)(21,34)。。。
但是其他的数据呢!
之后多列了几组,又发现比如(4,7)(11,18)(29,47)。。。
(6,10)(16,26)。。。
等等,即构成抢义F数列的,如果可以这样递归的话就是log级的时间了,但是关键是不知道何时终止递归,因为第一个不好找啊,比如(4,7)前面的(1,3)就不是。。。

找了半天终于找到了,发现a和b两个数的比都很接近\frac{1+\sqrt{5}}{2},再把这些数研究一下发现它们中间不满足的都是b比较接近\frac{1+\sqrt{5}}{2}*a的下整,因为这题和根号5有千丝万缕的联系,我大胆假设这个界就是\frac{3-\sqrt{5}}{2}(0.386),没想到就过了!
比如(7,12)就不是,因为\frac{1+\sqrt{5}}{2}*7=11.326<11+\frac{3-\sqrt{5}}{2}
比如(12,20)就是,因为\frac{1+\sqrt{5}}{2}*12=19.416>19+\frac{3-\sqrt{5}}{2}

实际上正确的规律应该是下面这样的吧:
(a,b)其中a<b,除了(0,0)之外应该满足:
(1)b=\frac{1+\sqrt{5}}{2}*a取上整;
(2)\frac{1+\sqrt{5}}{2}*a-(b-1)需要大于\frac{3-\sqrt{5}}{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