uva 10025 The ? 1 ? 2 ? … ? n = k problem

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=966
题意:?1?2?3?4…?n=k,把每个?替换成+或者-,找到最小的n使得式子成立。
题意:这道题最关键的一点是。如果s1=1+2+3+.,x+..+n>=k (所有数取正数),那么一定有s2=1+2+3+..-x+..+n=k

非严格证明如下:

s1-s2 = 2x,s1-k=2x

一个数减去偶数,奇偶性不变。x是从1到n中的一个,2*x则包含了s1和s2相差的数所有可能性。

 

具体做法就是找到一个大于等于k的s1,且s1-k是偶数。

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz