[数据结构与算法]Codeforces Round #759 div. 2 A-D题解

A: Life of a Flower

题意

有一朵初始高度为 $1$ 的花，它第 $i$ 天的成长状态如下:

1. 如果第 $i$ 与 $i?1$ 连续两天都没有浇水，它会枯死
2. 如果第 $i$ 天浇水(但是第 $i?1$ 天未浇水)，它会长高 $1cm$
3. 如果第 $i$ 与 $i?1$ 连续两天都浇水，它会长高 $5cm$
4. 如果第 $i$ 天没有浇水，它不会成长

现给出 $n$ 天的浇水状况，求花的最终高度，若中途枯死则输出 $?1$

题解

根据题意模拟即可

参考代码

#include<bits/stdc++.h>
using namespace std;
 
template<class T>inline void read(T&x){
	x=0;
	char c=getchar(),last=' ';
	while(!isdigit(c))last=c,c=getchar();
	while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
	if(last=='-')x=-x;
}
 
const int MAXN=1e2+5;
int n;
int a[MAXN];
 
int main()
{
	int T;read(T);
	while(T--){
		read(n);
		int ans=1;
		for(int i=1;i<=n;i++){
			read(a[i]);
			if(ans==-1)continue;
			if(a[i]){
				if(a[i-1])ans+=5;
				else ans++;
			}
			else{
				if(i>1&&a[i-1]==0)ans=-1;
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}

B: Array Eversion

题意

给出一个长度为 $n$ 的数组 $a$，定义一种操作如下:

1. 令 $x=a_n$
2. 将数组分类为两个部分，左部分包含 $a_i\le x$ 的元素，右部分包含 $a_i>x$ 的元素，各部分内元素顺序与原数组顺序一致
3. 将左右部分合并，即为操作后的新数组

可以证明在有限次操作后，数组将不会变化(即再进行操作得到的新数组不变)
求可以使得数组变为不变状态的最小操作次数

题解

Lemma1:当 $a_n\ge a_i(1\le i\le n)$ ，即 $a_n$ 为数组中最大元素时，数组不会被操作改变

Lemma2:一次操作后， $i$ 最大的 $a_i>x(a_n)$ 会成为新的 $a_n$

从 $n$ ~ $1$ 扫描一次数组，每次扫到一个 $a_i>a_n$ 时将 $a_i$ 替换为新的 $a_n$ ，操作数+1即可

参考代码

#include<bits/stdc++.h>
using namespace std;

template<class T>inline void read(T&x){
	x=0;
	char c=getchar(),last=' ';
	while(!isdigit(c))last=c,c=getchar();
	while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
	if(last=='-')x=-x;
}

const int MAXN=2e5+5;
int n;
int a[MAXN];

int main()
{
	int T;read(T);
	while(T--){
		read(n);
		for(int i=1;i<=n;i++)read(a[i]);
		int ans=0;
		for(int i=n-1,last=a[n];i>=1;i--){
			if(a[i]>last){
				ans++;
				last=a[i];
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}

C: Minimize Distance

题意

在数轴上有 $n$ 个仓库，第 $i$ 个仓库位于 $x_i$ 处
在原点上有 $n$ 件货物(没有货物时要回原点拿)，一位商人从原点出发，他同时最多可以带 $k$ 件货物，当他经过一个仓库时，他就可以将一件带着的货物放入仓库中
求将 $n$ 件货物放入 $n$ 个仓库中，商人所需行走的最短路程(注意最终完成任务时商人不必回到原点)

题解

首先我们将正负数分开处理(因为在原点的不同方向上)
对于同一方向上的任务，我们采用贪心，每次送最远的 $k$ 个仓库（若不足则将该方向上全部送完），代价是所送仓库中 $max(|x_i|)\times 2$ (因为要走来回所以要乘 $2$ )
最后减去所有仓库中 $max(|x_i|)$ 即可(显然最后停留在这个点不回原点可以减少最多的代价)

参考代码

#include<bits/stdc++.h>
using namespace std;

template<class T>inline void read(T&x){
	x=0;
	char c=getchar(),last=' ';
	while(!isdigit(c))last=c,c=getchar();
	while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
	if(last=='-')x=-x;
}

const int MAXN=2e5+5;
int n,k;
int ca,cb;
long long a[MAXN],b[MAXN];
long long ans;

int main()
{
	int T;read(T);
	while(T--){
		read(n),read(k);
		ca=cb=1;
		for(int i=1,x;i<=n;i++){
			read(x);
			if(x>0)a[ca++]=x;
			else b[cb++]=x;
		}ca--,cb--;
		sort(a+1,a+ca+1);
		sort(b+1,b+cb+1,greater<int>());
		ans=-max(a[ca],-b[cb]);
		for(int i=ca;i>=1;i-=k)ans+=2*a[i];
		for(int i=cb;i>=1;i-=k)ans-=2*b[i];
		cout<<ans<<'\n';
	}
	return 0;
}

D: Yet Another Sorting Problem

题意

给定一个长度为 $n$ 的数组 $a$ ，我们有以下交换规则:

1. 选定 $3$ 个互不相同的位置 $i,j,k$
2. 将 $a_i,a_j,a_k$ 分别变为 $a_j,a_k,a_i$

问只使用这种交换方式，能否使得整个数组变为不降的

题解

Lemma1:(参考样例 $3$ )如果有两个元素相同，我们定然可以排序使得整个数组不降
证明:
令四个元素为 $a,a,x,y$
先交换前 $3$ 个元素，得 $a,x,a,y$
再交换后 $3$ 个元素，得 $a,a,y,x$
显然，我们在不调整其他元素的条件下实现了 $x,y$ 两个元素的互换
既然可以实现任意两个元素的交换，那么排序显然可行

Lemma2:如果整个数组是一个排列(即:没有元素相同)，那么可以排序的充要条件是:原排列为偶排列
略证:
设在目标排列中有3个元素 $a_i,a_j,a_k(i<j<k,a_i<a_j<a_k)$
那么此时，对于这三个元素而言，逆序数为 $0$(偶)
对这 $3$ 个元素使用一次交换，得到的结果只会是 $a_j,a_k,a_i$ (逆序数为 $2$ (偶) ，分别是 $a_j,a_i$ 和 $a_k,a_i$ )或 $a_k,a_i,a_j$ (逆序数为 $2$ (偶) ，分别是 $a_k,a_i$ 和 $a_k,a_j$ )
(考虑上其他元素，排列的奇偶性也不会改变，但是我懒得写了XD)
所以该种交换不会改变排列的奇偶性，那么若原排列的奇偶性与目标排列相同(目标排列的逆序数为 $0$ ，因此原排列应为偶排列)，那么我们一定可以通过某种方式交换得到目标排列

我们先判是否有重复元素，有则直接输出 $YES$ ，否则检查排列奇偶性即可(我使用了归并排序来求逆序数)

参考代码

#include<bits/stdc++.h>
using namespace std;

template<class T>inline void read(T&x){
	x=0;
	char c=getchar(),last=' ';
	while(!isdigit(c))last=c,c=getchar();
	while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
	if(last=='-')x=-x;
}

const int MAXN=5e5+5;
int n;
int a[MAXN],tmp[MAXN];
bitset<MAXN>vis;

long long merge_sort(int l,int r){
	if(l>=r)return 0;
	int mid=l+r>>1;
	long long ret=merge_sort(l,mid)+merge_sort(mid+1,r);
	int i=l,j=mid+1,k=l;
	while(i<=mid&&j<=r){
		if(a[i]<=a[j])tmp[k++]=a[i++];
		else{
			ret+=mid-i+1;
			tmp[k++]=a[j++];
		}
	}
	while(i<=mid)tmp[k++]=a[i++];
	while(j<=r)tmp[k++]=a[j++];
	for(int i=l;i<=r;i++)a[i]=tmp[i];
	return ret;
}


int main()
{
	int T;read(T);
	while(T--){
		read(n);
		for(int i=1;i<=n;i++)read(a[i]);
		vis.reset();
		int ok=0;
		for(int i=1;i<=n;i++){
			if(vis[a[i]])ok=1;
			vis[a[i]]=1;
		}
		if(ok)puts("YES");
		else puts(merge_sort(1,n)&1?"NO":"YES");
	}
	return 0;
}