题解：[ARC153C] ± Increasing Sequence （加强版）
tobie
·
·
题解
这个 A_i\in \{ -1,1\} 太逊了，我们看看丢掉这个条件能不能做。
考虑使用差分数组刻画限制：
\begin{align*}
&\sum_{i=1}^n A_i \sum_{j=1}^i c_i=0\\
&\sum_{i=1}^n c_i \sum_{j=i+1}^n A_i=0
\end{align*}
设 B_i 为 A_i 的后缀和，则题目条件可以表示为 \sum B_ic_i=0。
此外，我们还有一个 \forall i>1,c_i>0 的要求，我们对 c_1 的大小没有要求，考虑从此处入手。接下来我们分两种情况讨论：
情况1：B_1\neq 0。
不妨设 B_1>0，否则可以全部取反。
现在 c_1=-\sum_{i=2}^n B_i, c_i=B_1 满足要求。
情况2：B_1 = 0。
相当于说现在 c_1 没用了，直接设为 0。
先把 \forall i, B_i=0 的情况特判掉。
我们发现，如果剩下的 B_i 都有 B_i\le 0，则最终的和一定小于 0，反之同理。
所以我们现在能找到一个 B_{x}>0 和一个 B_y<0。
设 s=B_x+B_y-\sum B，不妨认为 s>0，则 c_x=B_x-\sum B, c_y=B_x, c_i=B_x 为一组合法解，否则 c_x=-B_y, c_y=\sum B- B_y, c_i=B_i 为一组合法解。
这样我们就成功地构造出来了答案。