※ 引述《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