这把感觉质量很高。

\(E\)

\(E\)比较简单所以先写个\(E\),考虑就一个置换操作来说改变的只有两端的值。

考虑\(|a_i - a_{i - 1}|\)变成区间，则我们考虑分类讨论，发现只有当\(a_{i + 1} > a_{i}\)且\(a_r > a_{r + 1}\)还有\(a_{i + 1} < a_{i}\)且\(a_r < a_{r + 1}\)时，交换操作会带来一些贡献，这个贡献是两倍交集。两种情况可以反转序列来做。、（注意单独考虑\(1\)和\(n\)）的情况。

#include<iostream>

#include<cstdio>

#include<algorithm>

#define ll long long

#define N 400005

ll n,a[N],sum,ans;

struct P{ll l,r;}b[N];

inline bool operator < (P a,P b){return a.l < b.l;}

inline ll abs(ll a){return a >= 0? a : -a;}

int main(){

	scanf("%lld",&n);

	for(int i = 1;i <= n;++i)

	scanf("%lld",&a[i]);

//	for(int i = 1;i <= n;++i)

//	std::cout<<a[i]<<" ";

	for(int i = 2;i <= n;++i)

	sum += abs(a[i] - a[i - 1]);

	ans = sum;

//	std::cout<<sum<<std::endl;

	for(int i = 2;i <= n - 1;++i)

	ans = std::min(ans,sum - abs(a[i + 1] - a[i]) + abs(a[i + 1] - a[1]));

	for(int i = 2;i <= n - 1;++i)

	ans = std::min(ans,sum - abs(a[i - 1] - a[i]) + abs(a[i - 1] - a[n]));

	//(al,al + 1) (ar,ar + 1)

	ll cnt = 0;

	for(int i = 1;i <= n - 1;++i)

	if(a[i] < a[i + 1])

	b[++cnt].l = a[i],b[cnt].r = a[i + 1];

	std::sort(b + 1,b + cnt + 1);

	ll maxr = b[1].r;

	for(int i = 2;i <= cnt;++i){

//		std::cout<<b[i].l<<" "<<b[i].r<<std::endl;

		ans = std::min(ans,sum - 2 * (std::min(maxr,b[i].r) - b[i].l));

		maxr = std::max(b[i].r,maxr);

	}

	std::reverse(a + 1, a + n + 1);

	cnt = 0;

	for(int i = 1;i <= n - 1;++i)

	if(a[i] < a[i + 1])

	b[++cnt].l = a[i],b[cnt].r = a[i + 1];

	std::sort(b + 1,b + cnt + 1);

	maxr = b[1].r;

	for(int i = 2;i <= cnt;++i){

		ans = std::min(ans,sum - 2 * (std::min(maxr,b[i].r) - b[i].l));

		maxr = std::max(b[i].r,maxr);

	}

	std::cout<<ans<<std::endl;

}

D#

大概是一个经典套路。

对于一种操作把整行整列都进行操作的话，考虑把每行每列都缩成点。

那么一个\((i,j)\)的红点相当于把行和列连上边。

选择一边清空则相当于把一个点和其他所有点的连边都去掉，相当删掉这个点。

这是一个二分图，要求最小化最后两边的乘积，考虑把一个联通块从叶子开始删，那么发现只能保留根。

根据二次函数，则把这些跟全部留在原本孤立点小的那边就好了。

巴特西

ARC 119 补题记录

D#

最新文章

热门文章