很好的思维题。

主要思路

我们只关心

\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$ 的情形类似），则 $$p:(p_1,\cdots,p_{j-1},p_j,p_{j+1},\cdots,p_k,p_{k+1},\cdots,p_n)\rightarrow(p_1,\cdots,p_{j-1},p_{j+1},\cdots,p_k,p_j,p_{k+1},\cdots,p_n)$$， $$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 ```cpp #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~~）

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

文章操作

主要思路

相关推荐

评论

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