Codeforces Round #598 (Div.3) 解析

我是 FSTer，打个 div.3 居然 $B$ 题就被卡。。。为什么不先做后面的题。。。

A. Payment Without Change

题意：给你 $a$ 个价值为 $n$ 和 $b$ 个价值为 $1$ 的硬币，问你能否正好凑成 $S$ 元。

解析：模拟即可，注意爆 long long，还有要分情况讨论。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int q;
long long a,b,n,s;
int main()
{
	scanf("%d",&q);
	while(q--)
	{
		scanf("%lld%lld%lld%lld",&a,&b,&n,&s);
		if(a*n+b<s)
		{
			printf("NO\n");
			continue;
		}
		long long r=s/n;
		if(r<=a)
		{
			if(b>=s%n)
				printf("YES\n");
			else
				printf("NO\n");
		}
		else
		{
			if(b>=s-a*n)
				printf("YES\n");
			else
				printf("NO\n");
		}
	}
	return 0;
}

B. Minimize the Permutation

题意：$q$ 个询问，每个询问给定 $n$ 和一个长度为 $n$ 的数字序列，你只能进行 $n-1$ 次操作，每次把第 $i$ 和第 $i+1$ 的数交换位置，操作顺序自定，问能得到的最小字典序的序列。

解析：暴力搜索，如果前面有比他大的就交换，同时标记，当所有的都被标记完或者已经是最小字典序时就结束循环，输出。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int t,q,n,sum;
int s[110];
int vis[110];
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			scanf("%d",&s[i]);
		memset(vis,0,sizeof(vis));
		bool flag=1;
		while(flag)
		{
			flag=0;
			for(int i=n-1;i>=1;i--)
				if(s[i]>s[i+1]&&vis[i]==0)
				{
					vis[i]=1;
					swap(s[i],s[i+1]);
					flag=1;
				}
		}
		for(int i=1;i<=n;i++)
			printf("%d ",s[i]);
		printf("\n");
	}
	return 0;
}

C. Platforms Jumping

题意：一条河流长度为 $n$，上面有 $m$ 块木板，每块长度为 $c_i$，你要从 $0$ 到 $n+1$ 处，你每次可以向前走 $[1,d]$ 个单位($d$ 给定)，且你只能走到木板上，问你能否到达对岸，如果能输出每块木板的坐标。

解析：贪心，尽量把木板往自己能走到，且在其能放到最后位置前面，尽量往后放，稍微处理一下即可。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,d;
int c[1010],ans[3010];
int sum[1010];
int main()
{
	scanf("%d%d%d",&n,&m,&d);
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&c[i]);
		sum[i]=sum[i-1]+c[i];
	}
	int now=0;
	for(int i=1;i<=m;i++)
	{
		for(int j=min(now+d,n-(sum[m]-sum[i])-c[i]+1);j<=min(now+d,n-(sum[m]-sum[i])-c[i]+1)+c[i]-1;j++)
			ans[j]=i;
		now=min(now+d,n-(sum[m]-sum[i])-c[i]+1)+c[i]-1;
	}
	if(now+d>=n+1)
	{
		printf("YES\n");
		for(int i=1;i<=n;i++)
			printf("%d ",ans[i]);
	}
	else
		printf("NO\n");
	return 0;
}

D. Binary String Minimizing

题意：给你 $n$ 和 $k$，和一个长度为 $n$ 的 $01$ 序列，你可以进行 $k$ 次交换，每次交换两个相邻的数，问能够达到的最小字典序的序列。

解析：很像 $\texttt{B}$ 题，但是由于是 $01$ 序列，我们还是贪心，把最前面的 $0$ 往最前移动，由于两个 $0$ 的中间一定全部是 $1$，我们不一步步交换，直接与要移动的位置交换即可。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
long long q,n,k;
char s[1010100];
int main()
{
	scanf("%lld",&q);
	while(q--)
	{
		memset(s,0,sizeof(s));
		scanf("%lld%lld",&n,&k);
		scanf("\n%s",s+1);
		int len=strlen(s+1);
		for(int i=1,pos=1;i<=len&&k!=0;i++)
			if(s[i]=='0')
			{
				if(i-pos<=k)
				{
					k-=(i-pos);
					swap(s[pos],s[i]);
					pos++;
				}
				else
				{
					pos=i-k;
					swap(s[pos],s[i]);
					k=0;
				}
			}
		printf("%s\n",s+1);
	}
	return 0;
}

E. Yet Another Division Into Teams

题意：给你 $n$ 和长度为 $n$ 的序列 $a_i$，把 $a_i$ 分成 $k$ 组，每组至少 $3$ 个元素，每组的贡献为 $\max\ a_i-\min\ a_i$，总贡献为每组贡献之和，现在要求总贡献最小，输出最小贡献和分组数 $k$，和每个元素所属的组的编号。

解析：DP。

设 $f[i]$ 为前 $i$ 个同学能达到的最小贡献，首先将 $a_i$ 排序，由于至少 $3$ 个同学一组，所以只有选择 $3\sim 5$ 个同学最佳，因为当 $6$ 个同学一组时，我们可以分成两组 $3$ 同学的组，明显更优。于是推出状态转移方程：

$$f[i+j]=min(f[i+j],f[i]+a[i+j-1]-a[i])\ (3\leq j\leq 5)$$

同时设立一个数组 $ans _i$ 记录上一组最后一个同学的坐标，然后可以通过倒推把每个同学所属组的编号得到。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
long long n;
long long ans[201010];
long long f[201010],num,k[201010];
struct node
{
	long long x;
	long long id;
}t[201010];
long long cmp(node a,node b)
{
	return a.x<b.x;
}
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&t[i].x);
		t[i].id=i;
	}
	sort(t+1,t+n+1,cmp);
	memset(f,0x3f,sizeof(f));
	f[1]=0;
	for(int i=1;i<=n;i++)
		for(int j=3;j<=5;j++)
			if(f[i]+t[i+j-1].x-t[i].x<f[i+j])
			{
				f[i+j]=f[i]+t[i+j-1].x-t[i].x;
				ans[i+j]=i;
			}
	long long p=n+1;
	while(ans[p])
	{
		num++;
		for(int i=ans[p];i<p;i++)
			k[t[i].id]=num;
		p=ans[p];
	}
	printf("%lld %lld\n",f[n+1],num);
	for(int i=1;i<=n;i++)
		printf("%lld ",k[i]);
	return 0;
}

F. Equalizing Two Strings

题意：给定两个长度均为 $n$ 的字符串 $s$ 和 $t$，每次可以任意选择 $s$ 和 $t$ 中一个长度为 $len\ (1\leq len\leq n)$ 的区间进行翻转，问能否使 $s$ 和 $t$ 相同。

解析：首先比较 $s$ 和 $t$ 每个字符的字符数，不同则肯定输出 NO；

然后如果 $s$ 中有大于等于两个相同的字符，那么一定可行，因为如果我们把这两个相同的字符反转到一起，然后每次 $s$ 反转这两个相同的字符，$t$ 中可以任意反转两个相邻的字符。

然后剩下的情况，和明显反转后，两个字符串的逆序对数量之差的奇偶性是不会变的，所以一开始统计好两个字符串的逆序对，然后判断逆序对数量之差是不是偶数，如果是就可行。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int q,n;
char s[201010],t[201010];
int a[101010],b[101010];
int sum1,sum2;
int main()
{
	scanf("%d",&q);
	while(q--)
	{
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		int flag=0,sum1=0,sum2=0;
		scanf("%d\n",&n);
		scanf("%s%s",s+1,t+1);
		for(int i=1;i<=n;i++)
		{
			a[s[i]-'a'+1]++;
			b[t[i]-'a'+1]++;
			for(int j=s[i]-'a'+1;j<=26;j++)
				sum1+=a[j];
			for(int j=t[i]-'a'+1;j<=26;j++)
				sum2+=b[j];
		}
		sort(s+1,s+n+1);
		sort(t+1,t+n+1);
		for(int i=1;i<=n;i++)
			if(s[i]!=t[i])
			{
				printf("NO\n");
				flag=1;
				break;
			}
		if(flag)
			continue;
		for(int i=2;i<=n;i++)
			if(s[i]==s[i-1])
			{
				printf("YES\n");
				flag=1;
				break;
			}
		if(flag)
			continue;
		if((sum1-sum2)&1)
			printf("NO\n");
		else
			printf("YES\n");
	}
	return 0;
}