Re: [問題] Codeforces R11 Problem B
看板Prob_Solve (計算數學 Problem Solving)作者tkcn (小安)時間14年前 (2010/04/28 11:56)推噓2(2推 0噓 6→)留言8則, 3人參與討論串2/4 (看更多)
※ 引述《chchwy (mat)》之銘言：
: http://codeforces.com/contest/11/problem/B
: 請問一下這題到底該怎麼解呢
: 感覺應該是有某種規律....不過我找不出來 orz
: 建表跟暴力搜尋都太慢了
: ==
: 順便偷問..這裡也有人在打code force嗎
只考慮 x 為正數的情況(反正負數也一樣)。
令 y = 1+2+...+j (假設全部都往右跳)
先找到 j 使得 y >= x，
如果 y > x，表示其中有一些 "向右跳" 要改成 "向左跳"，
所以只要能夠找到一組 1~j 之間的 subset A，使得 y - 2*sum{A} = x 即可。
很顯然 x-y 必須是偶數，否則一定找不到 subset A。
(所以如果不是偶數，可以把 j 的值加 1 然後從頭開始)
寫到這裡應該夠了?
--
◤ ◥ ◢ ◣
T$，修好它吧。 ⊙▁⊙─ ─⊙▂⊙ 碰到問題，用SoftICE就對了！
╰ ∕皿﹨ ◥皿◤ ╯
◥█◤◢ ◥ ︶◤
Lee ◤ ︶ ◥◤ ﹨▼∕◥ T$ Chen
ＭＹＴＨＢＵＧＴＥＲＳ ◥ ◤＼◥ by dajidali
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.122.183.199
→
04/28 13:08, , 1F
04/28 13:08, 1F
推
04/28 13:27, , 2F
04/28 13:27, 2F
→
04/28 13:27, , 3F
04/28 13:27, 3F
推
04/28 13:30, , 4F
04/28 13:30, 4F
→
04/28 14:13, , 5F
04/28 14:13, 5F
→
04/28 14:17, , 6F
04/28 14:17, 6F
→
04/28 14:49, , 7F
04/28 14:49, 7F
→
04/28 15:08, , 8F
04/28 15:08, 8F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 4 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
