CF1110E Magic Stones 做题记录

一次操作选择$1<i<n$，使$c_i$变为$c_i'$，$c_i'=c_{i+1}+c_{i-1}-c_i$

是否能做若干次操作，使每个$c_i$和$t_i$相等？

$2\le n\le 10^5, 0\le c_i\le 2*10^9, 0\le t_i\le 2*10^9$。

首先遇到这种序列操作的题，肯定要考虑原序列、差分序列和前缀后缀和序列。

那么原序列似乎规律，那么观察差分序列。设 $a_i=c_{i+1}-c_i$，那么一次 $c_i=c_{i-1}+c_{i+1}-c_i$ 的操作相当于让 $a_{i-1}=c_{i-1}+c_{i+1}-c_i-c_{i-1}=c_{i+1}-c_i=a_i$，$a_{i}=c_{i+1}-(c_{i-1}+c_{i+1}-c_i)=c_i-c_{i-1}=a_{i-1}$，也就是交换 $a_{i}$ 和 $a_{i-1}$。

那么本题就变得就很简单了，特判掉 $c_1\not=t_1,c_n\not=t_n$ 的情况，排序即可。