Codeforces Round #768 （div1）（A~D）_codeforces round 768 (div. 1)

这场因为明早有事就没更新，赛中过了A~C，D来不及写了，赛后5分钟码好提交2wa。。

A. And Matching（思维+分类讨论）

开局想到的就是优先将 i~n-i-1 匹配，答案为0，之后以一次交换得出贡献值，喜提一发wa，之后想了20多分钟才发现还有特判情况。。

首先对于k！=n-1时候，我们将之前的匹配进行一次换位，即n-1~k，0~n-k-1，其余不变即可

而对于k=n-1&&n>4的情况，我们发现将1与2两点交换可以得出3的贡献，因此变为n-3与0的交换

而k=n-1&&n=4的情况输出-1即可

#include <bits/stdc++.h>
#define ll long long
#define ls p<<1
#define rs p<<1|1
#define Ma 2<<20
#define mod 1000000007
using namespace std;
 
struct node
{
	ll l,r;
}t[Ma];
 
int main()
{
	ll tt;
	scanf("%lld",&tt);
	while (tt--)
	{
		ll n,k;
		scanf("%lld%lld",&n,&k);
		for (ll i=0;i<n/2;i++)
			t[i].l=i,t[i].r=n-i-1;
		if (n==k+1&&n==4)
			printf("-1\n");
		else if (n==k+1)
		{
			swap(t[1].l,t[2].l);
			swap(t[3].l,t[0].r);
			ll ans=0;
			for (ll i=0;i<n/2;i++)
				printf("%lld %lld\n",t[i].l,t[i].r),ans+=t[i].l&t[i].r;
		}
		else
		{
			if (k<n/2)
				swap(t[0].r,t[k].r);
			else
				swap(t[0].r,t[n-k-1].l);
			for (ll i=0;i<n/2;i++)
				printf("%lld %lld\n",t[i].l,t[i].r);
		}
	}
	return 0;
}

B. Range and Partition（摸你+贪心）

我们发现对于[l,r]中的元素>=在[l,r]的元素+k，便一定能满足答案，因此我们可以得出在[l,r]中的元素至少有(n+k+1)/2个，因此将元素排序后贪心得出最优的[l,r]，并进行分配即可。

#include <bits/stdc++.h>
#define ll long long
#define ls p<<1
#define rs p<<1|1
#define Ma 1000005
#define mod 1000000007
using namespace std;
ll a[Ma],b[Ma];
 
int main()
{
	ll tt;
	scanf("%lld",&tt);
	while (tt--)
	{
		ll n,m;
		scanf("%lld%lld",&n,&m);
		for (ll i=1;i<=n;i++)
			scanf("%lld",&a[i]),b[i]=a[i];
		sort(a+1,a+n+1);
		ll le=0,re=mod,add=(n+m+1)/2;
		for (ll i=1;i+add-1<=n;i++)
			if (a[i+add-1]-a[i]<re-le)
				le=a[i],re=a[i+add-1];
		printf("%lld %Lld\n",le,re);
		ll pre=1,w=0,cnt=1;
		for (ll i=1;i<=n&&cnt<m;i++)
		{
			if (b[i]>=le&&b[i]<=re)
				w++;
			else
				w--;
			if (w>=1)
			{
				cnt++;
				printf("%lld %lld\n",pre,i);
				pre=i+1,w=0;
			}
		}
		printf("%lld %lld\n",pre,n);
		//printf("\n");
	}
	return 0;
}

C. Paint the Middle（贪心+dp+区间优化）

假设有这样的一串1......1.....1....1，最优取法一定是头与尾，因此我们可以认为[l,r](a[l]==a[r])

的区间进行筛选，对于r来说无关紧要，因此我们所使用的区间为[l,r-1]，贡献为r-l-1。

假设有这样的k个区间，我们可以n~1的进行他的头优化

最后进行dp维护即可。

#include <bits/stdc++.h>
#define ll long long
#define ls p<<1
#define rs p<<1|1
#define Ma 1000005
#define mod 1000000007
using namespace std;
ll dp[Ma];
ll pre[Ma];
vector <ll> a[Ma];
 
ll tot=0;
 
 
int main()
{
	ll n;
	scanf("%lld",&n);
	for (ll i=1;i<=n;i++)
		pre[i]=i;
	for (ll i=1;i<=n;i++)
	{
		ll x;
		scanf("%lld",&x);
		a[x].push_back(i);
	}
	for (ll i=1;i<=n;i++)
		if (a[i].size()>=2)
			pre[a[i][a[i].size()-1]-1]=a[i][0];
	ll l=n;
	for (ll i=n;i>=1;i--)
	{
		l=min(l,pre[i]);
		pre[i]=l;
	}
	for (ll i=1;i<=n;i++)
		dp[i]=max(dp[i-1],dp[pre[i]-1]+i-pre[i]);
	printf("%lld\n",dp[n]);
	return 0;
}

D. Flipping Range（分类+数学）

首先我们要得到一个操作，我们先假设操作长度为k，那么我们得到两个操作。

1.进行[l,l+k-1]操作，得到的效果为[l,l+k-1]变号

2.进行[l,l+k-1]操作与[l+1,l+k]操作，得到的效果为l与l+k变号

通过这一步我们可以发现对于i%k的点中会有奇数/偶数个变号，因此我们可以分类得出答案。

下面就是如何找到这个k了。对于b的区间长度操作，我们可以发现我们可以得出的最小区间操作为

gcd（b），因此这道题便解决了（doge）。

#include <bits/stdc++.h>
#define ll long long
#define ls p<<1
#define rs p<<1|1
#define Ma 1000005
#define mod 1000000007
using namespace std;
ll n,k,m;
vector <ll> a[Ma];
ll tot[Ma];
ll d[Ma],b[Ma];
 
ll sol(ll x)
{
	ll ans=0;
	for (ll i=0;i<m;i++)
	{
		ll j=0;
		if (x==1)
			ans+=-a[i][j],j++;
		for (;j+1<a[i].size();j+=2)
			ans+=abs(a[i][j]+a[i][j+1]);
		for (;j<a[i].size();j++)
			ans+=a[i][j];
	}
	return ans;
}
 
 
int main()
{
	ll tt;
	scanf("%lld",&tt);
	while (tt--)
	{
		m=0;
		scanf("%lld%lld",&n,&k);
		for (ll i=0;i<n;i++)
			scanf("%lld",&d[i]);
		for (ll i=0;i<k;i++)
		{
			ll x;
			scanf("%lld",&x);
			m=__gcd(x,m);
		}
		for (ll i=0;i<m;i++)
			a[i].clear(),tot[i]=0;
		for (ll i=0;i<n;i++)
			a[i%m].push_back(d[i]);
		for (ll i=0;i<m;i++)
			sort(a[i].begin(),a[i].end());
		printf("%lld\n",max(sol(0),sol(1)));
	}
	return 0;
}