PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] Codeforces R11 Problem B

看板Prob_Solve (計算數學 Problem Solving)作者LPH66 ((short)(-15074))時間14年前 (2010/04/28 14:26)推噓0(0推 0噓 2→)

留言2則, 1人參與討論串4/4 (看更多)

※ 引述《bleed1979 (十三)》之銘言： : 以下這個方法只是能AC，但不代表恆正確，也可能是錯的。 : 解這題的基本認知︰ : 1.測資的正負是一樣的，所以一開始要轉正來解。 : 2.相鄰兩步數最少會差一步，2和3最小可能是+1或-1。 : 3.0，0 + 1 = 1， 0 + 1 + 2 = 3， 0 + 1 + 2 + 3 = 6， : 0 + 1 + 2 + 3 + 4 = 10， 0 + 1 + 2 + 3 + 4 + 5 = 15， : 0 + 1 + 2 + 3 + 4 + 5 + 6 = 21， : 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 : 為0，1，3，6，10，15，21，28.... : 0不要看，依序是奇奇偶偶奇奇偶偶奇奇偶偶.... : 解題，數據觀察。 : 1 2 3 最大為6 : + + + 6 : + + - 0 : + - + 4 : + - - 4 取絕對值，以下皆是。 : - + + 4 : - + - 2 : 推到這就可以發現，最大為6，但0，2，4，6通包了。 : 1 2 3 4 5 最大15 : + + + + + 15 : + + + - + 7 : + + + - - 3 : + + - + + 9 : + + - + - 1 : + + - - - 9 : + - + + + 11 : + - - + + 5 : - + + + + 13 : 我跳著推，但推到這就發現，最大為15，但1，3，5，7，9，11，13，15通包了。 : 到此階段可以合理的假設。總和如果是奇數，從1開始的奇數會包含。 : 同理如偶數。其實這是可以證明的若 1+2+...+n = K 是奇數則 -1+2+3+...+n = K-2 1-2+3+...+n = K-4 1+2-3+...+n = K-6 ... 1+2+3+...-n = K-2n -1+2+3+...-n = K-2n-2 1-2+3+...-n = K-2n-4 ... 依此類推即知 [-K,K] 當中的所有奇數都包了 K 是偶數時同理 : 所以，我的作法就是用for迴圈一直加總， : 跳出迴圈的條件為總和大於測資且測資%2和總和%2相等。 : 有人可能會說，如果找14呢？ : 14相當於15差兩步(5 + 2 = 7)(基礎知識1) 或是 : 加總到7(15, 21, 28)(基礎知識3) : 都是7步。 : Bleed 我這題送 ACM 10025 的做法是建表 ______ 建出一個 1~n 的總和表 n 建到 45000 (比 √2*10^9 稍大) 然後找和時就二分搜尋再往後找奇偶相等的就是了因為二分搜尋的關係往後找頂多找個三四步所以還滿快的但意外的在這個地方也可以過... (這裡和 ACM 不一樣是一次執行一組測資這種的寫法會比 Bleed 的稍慢) -- "LPH" is for "Let Program Heal us".... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.30.84