目录
给定一个元素两两不同序列 (a)，要求生成一个新的序列 (b) ，使得对于任意一个下标集合（全集和空集除外），两个序列对应的数之和不同。
解析
这题 (nle 22) 是骗人的……因为 spj 复杂度是 (2^n)……
注意到元素两两不同，考虑一个简单的操作：将每一个数用数值意义上的下一个数替换。当不考虑最大值时，这个操作显然可以满足条件。考虑将最大值替换成最小值并证明该结论。
令 (f(S,a)=sumlimits_{xin S} a_x)，即下标集合 (S) 在序列 (a) 中的元素和。并令 (U=[1,|a|]capmathbb{Z})，即下标集合的全集。
- 如果 (S) 不包括最大值，则显然 (f(S,a)< f(S,b))；
- 如果 (S) 包括了最大值，考虑 (S) 的补集。根据上述结论，(f(U-S,a)<f(U-S,b))。又因为 (f(U,a)=f(U,b))，得证。