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
由此我们就可以显然地贪心凑$sum_n/2$，原因是假设从大到小枚举，现在只需要凑$sum_n/2-k$，那么$sum_n/2-k$一定小于等于某个$a_i$，所以一定可以凑出来。
2、UVa11925
首先就是转变成逆操作（常见套路），考虑暴力模拟的话数据范围是可以接受的，于是就直接模拟，如果$a_2<a_1$就$swap$，否则移到后面去——但是需要注意判一下，如果$a_1=n$那么交换会产生一堆冗杂状态，此时选择移到后面去（剪枝）。