Codeforces Round #768 （div1）（A~D）

这场因为明早有事就没更新，赛中过了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 
#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 
B. Range and Partition（摸你+贪心）
 
我们发现对于[l,r]中的元素>=在[l,r]的元素+k，便一定能满足答案，因此我们可以得出在[l,r]中的元素至少有(n+k+1)/2个，因此将元素排序后贪心得出最优的[l,r]，并进行分配即可。
 
#include 
#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]=le&&b[i]<=re)
				w++;
			else
				w--;
			if (w>=1)
			{
				cnt++;
				printf("%lld %lldn",pre,i);
				pre=i+1,w=0;
			}
		}
		printf("%lld %lldn",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 
#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  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("%lldn",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 
#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  a[Ma];
ll tot[Ma];
ll d[Ma],b[Ma];

ll sol(ll x)
{
	ll ans=0;
	for (ll i=0;i 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5714786.html