B. Missing Subsequence Sum
题意:构造一个长度不超过 25 的序列,保证任意子集的和的集合为 { x ∣ 1 ≤ x < k a n d k < x ≤ n } \{x|1\leq x<k ~and ~ k<x\leq n\} {x∣1≤x<k and k<x≤n}
【不会解决空缺的问题,看了题解】
思路:容易想到先构造 [ 1 , k ) [1,k) [1,k) 的。接下来塞入 k + 1 k+1 k+1 ,这样会形成类似 [ 1 , 2 , ⋯ , k − 1 ] ( k ) [ k + 1 , ⋯ , 2 k ] , [ 2 k + 1 , ⋯ , 2 k + k ] ( 2 k + k + 1 ) [ . . . ] [1,2,\cdots ,k-1](k)[k+1, \cdots,2k],[2k+1, \cdots,2k+k](2k+k+1)[...] [1,2,⋯,k−1](k)[k+1,⋯,2k],[2k+1,⋯,2k+k](2k+k+1)[...] 。此时注意到空缺需要填充,我们可以添加一个 2k ,这样第一个空缺可以由 ( k + 1 ) + ( 2 k ) (k+1)+(2k) (k+1)+(2k) 来填充。
AC代码:https://codeforces.com/contest/1965/submission/269581726