BZOJ 5071 – 小A的数字

题目链接:BZOJ 5071

上午刚比完蓝桥杯省赛,下午看到大家讨论B组最后一题和BZOJ 5071的套路是相同的,遂记此题。

题解

记$\{a_n \}$的前缀和为$f$,那么经过题目描述的操作$a_{i-1} \leftarrow a_{i-1} + a_{i}, a_{i+1} \leftarrow a_{i+1} + a_{i}, a_i \leftarrow -a_i$后,$(f_{i – 1}, f_i, f_{i + 1})$变成了$(f_{i – 1} + a_i, f_i – a_i, f_{i + 1})$,即$(f_{i}, f_{i – 1}, f_{i + 1})$,前两个互换位置。根据这个操作可以把任意相邻两项互换得到$f$的所有排列。那么只要判断$\{ b_n \}$的前缀和与$f$能否一一对应,即可判断是否可行。

变式

2019年蓝桥杯省赛B组(C++):通过这个操作使得$|a_i|$最大的项最小,同样,为了使得最大的差最小,对$f$排序即可。

说点什么

avatar
50
  Subscribe  
提醒