题解：CF2077E Another Folding Strip

· · 题解

怎么都不是这么做的？？？

先考虑计算 f(a_1,a_2,\cdots,a_n)。

考虑一次折叠相当于将编号为 p_1<p_2<\cdots<p_k 的格子减一，然后要求 p_i 和 p_{i-1} 奇偶性不同。

考虑构建一张二分图，其中左部点表示入度，右部点表示出度。入度 i 能和出度 j 匹配，当且仅当 j<i，且i,j 奇偶性不同。

那么最少操作次数，就等价于 \sum_{i=1}^{n} a_i-\text{maxmatch}。

计算 \text{maxmatch} 考虑 Hall 定理，对于权值，我们可以等效看成多个点，令 L 表示左部点集合，N(S) 表示 S 集合出边的并集。由于 \text{maxmatch}=|L|-\max_{S\subseteq L}\{|S|-|N(S)|\}，所以最少操作次数为 \max_{S\subseteq L}\{|S|-|N(S)|\}。

对于 N(S)，我们发现我们只关心 S 集合中的编号最大值 mx_1，以及编号和 mx_1 奇偶性不同的编号最大值 mx_2。我们发现，mx_2 前面的位置选，不会对 N(S) 造成影响，同时 (mx_2,mx_1] 之间和 mx_1 奇偶性相同的位置，也不会对 N(S) 产生影响。于是，为了使得 |S| 尽量大，我们会将这些点全选。

我们发现此时 S 为 \{i|i\le mx_2\}\cup\{i|i\in[mx_2,mx_1]\land i\equiv mx_1\pmod 2\}，N(S) 为 \{i|i\le mx_2\}\cup\{i|i\in(mx_2,mx_1]\land i\not\equiv mx_1\pmod 2\}。

那么 |N(S)|-|S| 就为：

\max_{mx_1>mx_2\land mx_1\not\equiv mx_2\pmod 2\}}\{\sum_{i\in (mx_2,mx_1]\land i\equiv mx_1\pmod 2} a_i - \sum_{i\in (mx_2,mx_1]\land i\not\equiv mx_1\pmod 2} a_i\}

就得到了这个重要结论。

然后，我们发现，如果单纯是求最大区间偶数位置和减奇数位置和，是Treasure Hunt，所以一定有玄机。

我们考虑令 s_i 为前 i 个数，奇数位置减去偶数位置的差。

那么我们惊讶的发现，求的东西就可以等效成 \max_{i=l-1}^{r} \{s_i\}-\min_{i=l-1}^{r} \{s_i\}。

于是拆成两部分，单调栈维护了。