UVa题目泛做

1、UVa1614 先证一个引理，就是$\forall i\in[1,n], 1\leq a_i\leq i$。若令$sum_i$表示$\sum_{i=1}^{n} a_i$，那么$\forall sum_i$，都可以用$1$~$i$中的任意个$a_j$来凑出。 考虑数学归纳。显然$i=1$时满足，那么对于$i>1$，我们设$p\in [1,i]$，那么会有$sum_{i-1}+p=sum_{i-1}+a_i-(a_i-p)$。考虑根据归纳，$a_i-p\leq a_{i-1}$，故$a_i-p$一定是可以用前$i-1 $个$a_j$凑出来的。所以我们只需要在$sum_i$中除掉这些数即可。 由此我们就可以显然地贪心凑$sum_n/2$，原因是假设从大到小枚举，现在只需要凑$sum_n/2-k$，那么$sum_n/2-k$一定小于等于某个$a_i$，所以一定可以凑出来。 2、UVa11925 首先就是转变成逆操作（常见套路），考虑暴力模拟的话数据范围是可以接受的，于是就直接模拟，如果$a_2<a_1$就$swap$，否则移到后面去——但是需要注意判一下，如果$a_1=n$那么交换会产生一堆冗杂状态，此时选择移到后面去（剪枝）。