P9086 「SvR-2」令人为难的区间操作问题 题解

CSP_Sept · 2023-02-18 21:52:34 · 题解

解法

Solution 1

萌萌签到题，我们考虑到记 S(i) 表示 F(1),F(2), \ldots ,F(i) 的和，发现 S(i) \equiv i \pmod 2。

而若干次进行长度为 len 的操作相当于给数列的总和加上若干次 S(len)。这样的操作在模 2 域中是等价的。

容易发现，计算出操作前后序列元素和的差，对 2 取模输出即可。

Solution 2

实际上我们有一种更为有趣的做法，定义 -1 次操作，从而将所有操作全部变为若干次 len = 1 的情况。

具体如下：

对于每个 i，

• 若 a_i<b_i，则相当于在 [i,i] 上进行了 b_i-a_i 次 len=1 的操作；
• 若 a_i>b_i，则相当于在 [i,i] 上进行了 -(a_i-b_i) 次 len=1 的操作。

所以这种情况下，操作总长度即为 \sum_{i=1}^n(a_i-b_i)。