题解：P13754 【MX-X17-T3】Distraction

· · 题解

很好的思维题。

主要思路

我们只关心 \sum_{j=1}^{i-1}[p_j>p_i]+\sum_{j=i+1}^{n}[p_i>p_j] \pmod2 的值。考虑对上式进行变形。

=\sum_{j=1}^{i-1}(1-[p_i>p_j])+\sum_{j=i+1}^{n}[p_i>p_j]\\& =(i-1)-\sum_{j=1}^{i-1}[p_i>p_j]+\sum_{j=i+1}^{n}[p_i>p_j]\\& \equiv(i-1)+\sum_{j=1}^{i-1}[p_i>p_j]+\sum_{j=i+1}^{n}[p_i>p_j]\\& =(i-1)+\sum_{j=1}^{n}[p_i>p_j]\\& =(i-1)+(p_i-1)\equiv i+p_i\pmod2 \end{aligned}

这就得到了 v_i 的简单表达式，有 v_i 只与 i 和 p_i 的奇偶性有关，且有

\sum_{i=1}^{n}v_i\equiv\sum_{i=1}^n(i+p_i)=2\sum_{i=1}^ni\equiv0\pmod 2

考虑对排列执行一次操作后，v_i 的值如何变化。

设 p_j 被插入到位置 k（此处考虑 j<k 的情形，j>k 的情形类似），则

$$v:(v_1,\cdots,v_n)\rightarrow(v_1',\cdots,v_n')$$，其中 $$v_i'\equiv p_i'+i=\begin{cases}p_{i+1}+i&j\le i\le k-1\\p_j+i&i=k\\p_i+i&else\end{cases}\equiv\begin{cases}1-v_{i+1}&j\le i\le k-1\\v_j+k-j&i=k\\v_i&else\end{cases}\pmod2

有 v' 元素大致为将 v 第 j 至 k 位进行取反（0 变成 1，1 变成 0）。

故为使权值增加尽可能多，(贪心）选择 v 的区间使得区间内 0 的个数与 1 的个数之差尽可能大，取该区间的前一元素插入区间最后即可。

简单计算可知若区间内 0,1 个数差为 d，则权值增加量为 2\lfloor\frac{d}{2}\rfloor。分类讨论易证 2\lfloor\frac{d}{2}\rfloor 最优。

CODE

#include <bits/stdc++.h>
using namespace std;
const int INF=1e9+9;
int T,n,p,cnt[5000009],mn[5000009],mx,ans;
int main(){
    cin>>T;
    while(T--){
        scanf("%d",&n); cnt[0]=mn[0]=mx=ans=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&p);
            if((i+p)%2==0) cnt[i]=cnt[i-1]+1;
            else cnt[i]=cnt[i-1]-1,ans++;
        }
        for(int i=1;i<=n;i++) mn[i]=min(mn[i-1],cnt[i]);
        for(int i=1;i<=n;i++) mx=max(mx,cnt[i]-mn[i-1]); //求最大连续字段和
        ans+=mx/2*2; printf("%d\n",ans);
    }
    return 0;
}

（LATEX 新手，dalao 轻喷，求点赞支持 qwq）