作者tkcn (小安)
看板Prob_Solve
标题Re: [问题] Codeforces R11 Problem B
时间Wed Apr 28 11:56:35 2010
※ 引述《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
1F：→ bleed1979:这题我只写19行。 04/28 13:08
2F：推 LPH66:我刚刚才仔细看这一题 这不就是 ?1?2...?n=k problem ? 04/28 13:27
3F：→ LPH66:(ie. ACM 10025) 04/28 13:27
4F：推 LPH66:我拿这题的 code 改个输入丢上去就过了....(连范围都没动) 04/28 13:30
5F：→ tkcn:这题我还没写过，晚点试试 04/28 14:13
7F：→ tkcn:顺利 AC，应该可以写得比 19 行短。 04/28 14:49
8F：→ tkcn:缩过之後，总共 14 行 (Java) 04/28 15:08