Codeforces Round #578 (Div. 2) 解析

A. Hotelier

题意：一个长度为 $10$ 的序列，编号为 $0\sim 9$ ，给定一个操作序列，包含三种操作方式：

使序列最左边为 $0$ 的位置变为 $1$ ；
使序列最右边为 $0$ 的位置变为 $1$ ；
指定一个位置，使其变为 $0$ 。

求操作后的序列。

输入：第一行一个整数， $n$ ，代表操作序列长度；第二行一个操作序列。

输出：操作后的序列。

解析：根据题意，模拟即可。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,a[10];
char s[101010];
int main()
{
	scanf("%d",&n);
	scanf("%s",s);
	for(int p=0;p<n;p++)
	{
		if(s[p]=='L')
		{
			for(int i=0;i<=9;i++)
				if(a[i]==0)
				{
					a[i]=1;
					break;
				}
		}
		else if(s[p]=='R')
		{
			for(int i=9;i>=0;i--)
				if(a[i]==0)
				{
					a[i]=1;
					break;
				}
		}
		else
			a[s[p]-'0']=0;
	}
	for(int i=0;i<=9;i++)
		printf("%d",a[i]);
	return 0;
}

B. Block Adventure

题意：给定一个长度为 $n$ 的序列，序列第 $i$ 个元素为 $h_i$ ，代表第 $i$ 列由 $h_i$ 个块累积成，一开始你在第 $1$ 列，你的包里有 $m$ 个块，对于每一列，你可以多次进行以下三种操作：

从当前列取出 $1$ 块，放进自己包里；
从包里取出 $1$ 块，放在当前列上，高度增加 $1$ 。
如果 $i<n$ 且 $|h_i-h_{i+1}|\leq k$ ，移动至下一行， $k$ 是开始给定的一个常数，这是唯一向后移动的途径。

前两种操作，你依然待在第 $i$ 列，只是高度变化，你的包可以装下无数个块。

回答你是否可以从第 $1$ 列岛第 $n$ 列。

输入：第一行一个数 $t$ ，代表有 $t$ 组数据；每个数据第一行三个数 $n,m,k$ ，表示列数，你的初始块数，向后移动的高度跨辐；第二行 $n$ 个数，表示第 $i$ 列的高度。

输出：是否可以到达， $YES$ 和 $NO$ 。

解析：贪心，分两种情况，如果 $h_{i+1}\leq k$ ，说明即使把第 $i$ 列取完都可以向后走，就把第 $i$ 列取完；如果 $h_{i+1}> k$ ，又分两种情况，如果 $h_i>h_{i+1}-k$ ，就把 $h_i$ 取到 $h_{i+1}-k$ ，否则就选择从包中取出块增加第 $i$ 列高度，判断块的数量能否使其到达下一列。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,k,t;
int h[110];
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		int flag=0;
		memset(h,0,sizeof(h));
		scanf("%d%d%d",&n,&m,&k);
		for(int i=1;i<=n;i++)
			scanf("%d",&h[i]);
		for(int i=1;i<n;i++)
		{
			if(h[i+1]<=k)
				m+=h[i];
			else
			{
				if(h[i]>h[i+1]-k)
				    m+=(h[i]-h[i+1]+k);
				else if(h[i]<h[i+1]-k)
				{
					int p=h[i+1]-k;
					if(h[i]+m<p)
					{
						flag=1;
						break;
					}
					else
						m-=(p-h[i]);
				}
			}
		}
		if(flag==1)
		    printf("NO\n");
		else
			printf("YES\n");
	}
	return 0;
}

C. Round Corridor

题意：一个圆形，外围分为内外两层，内层有 $n$ 个区域，外层有 $m$ 个区域，每层每个区域中间有隔板，使每一层每个区域不相通，但是内外两层相通。

内层从 $12$ 点方向，按照顺时针依次编号： $(1,1),(1,2),…,(1,n)$ ，外层也从 $12$ 点方向，按照顺时针依次编号： $(2,1),(2,2),…(2,m)$ 。

你有 $q$ 个问题，对于每个问题，回答你是否可以从一个区域到达另一个区域。

输入：第一行三个数， $n,m,q$ ；接下来 $q$ 行，每行四个数， $sx,sy,ex,ey$ ， $1\leq sx,ex\leq 2$ ，如果 $sx,ex=1$ ，代表内层，否则为外层，判断能否从 $(sx,sy)$ 到 $(ex,ey)$ 。

输出： $q$ 行， $YES$ 或 $NO$ 。

解析：很明显，内层和外层可以相通，对于一个位置 $x$ ，如果在 $(1,x)$ 和 $(2,x)$ 都有隔板，那么如果 $yx$ ，那么不能从 $y$ 移动到 $z$ 。

设 $g=gcd(n,m)$ ，那么我们可以分出 $g$ 组，对于每 $\frac{n}{g}$ 个内层区域，每 $\frac{m}{g}$ 个外层区域分为一组，每个组内的区域可以互通，我们对于每个问题求出区域的组号，如果在同一个组就可以互通。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
long long n,m,q;
long long sx,sy,ex,ey;
long long gcd(long long a,long long b)
{
	if(b==0)
		return a;
	return gcd(b,a%b);
}
int main()
{
	scanf("%lld%lld%lld",&n,&m,&q);
	long long num=gcd(n,m);
	long long num1=n/num,num2=m/num;
	for(int i=1;i<=q;i++)
	{
		scanf("%lld%lld%lld%lld",&sx,&sy,&ex,&ey);
		if(sx==1)
			sy=(sy-1)/num1;
		if(ex==1)
			ey=(ey-1)/num1;
		if(sx==2)
			sy=(sy-1)/num2;
		if(ex==2)
			ey=(ey-1)/num2;
		if(sy==ey)
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}