Codeforces Round #579 (Div. 3) 解析

A. Circle of Students

题意：有 $n$ 个学生围成一圈，他们各自的编号不同，从 $1\sim n$ ，只有当他们的编号从小到大顺时针或逆时针围成一个圈时，他们才能开始舞会。

给出学生的排列顺序，判断他们能否立即开始舞会。

输入：第一行一个数，$q$，代表问题个数；对于每一个问题，第一行一个数，$n$，代表学生个数；第二行 $n$ 个数，代表学生的排列顺序。

输出：$YES$ 或 $NO$。

解析：模拟即可，枚举每个位置为起点，绕一圈判断是否为从小到大或从大到小。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,q,p[210],a[210],b[210];
int cmp(int a,int b)
{
	return a>b;
}
int main()
{
	scanf("%d",&q);
	while(q--)
	{
		int flag=0;
		memset(p,0,sizeof(p));
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&p[i]);
			a[i]=p[i];
			b[i]=p[i];
		}
		sort(a+1,a+n+1);
		sort(b+1,b+n+1,cmp);
		for(int i=1;i<=n;i++)//起点
		{
			int flag1=1;
			int tot1=1;
			for(int j=i;j<=i+n-1;j++)
				if(p[(j-1)%n+1]!=a[tot1++])
				{
					flag1=0;
					break;
				}
			if(flag1==1)
			{
				flag=1;
				break;
			}
			int flag2=1;
			int tot2=1;
			for(int j=i;j<=i+n-1;j++)
				if(p[(j-1)%n+1]!=b[tot2++])
				{
					flag2=0;
					break;
				}
			if(flag2==1)
			{
				flag=1;
				break;
			}
		}
		if(flag)
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}

B. Equal Rectangles

题意：给你 $4n$ 根棍子，第 $i$ 根棍子的长度为 $a_i$。你需要构成 $n$ 个矩形，构成矩形的 $4$ 根棍子长度在给出的棍子中挑选，你需要判断能否构成 $n$ 个矩形，且每个矩形面积均相等。

输入：第一行一个数，$q$，代表问题个数；对于每一个问题，第一行一个数，$n$，代表矩形个数；第二行 $4n$ 个数，代表棍子长度。

输出：$YES$ 或 $NO$。

解析：构成矩形，则每个长度至少有两根棍子，从小到大排序，最小和最大的乘积就是矩形面积，次小和次大的乘积一样…，以此类推，每次判断是否有两根棍子和乘积是否相同即可。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
long long q,n,a[410];
int main()
{
	scanf("%lld",&q);
	while(q--)
	{
		int flag=0;
		memset(a,0,sizeof(a));
		scanf("%lld",&n);
		for(int i=1;i<=4*n;i++)
			scanf("%lld",&a[i]);
		sort(a+1,a+4*n+1);
  		long long num=a[1]*a[4*n];
		for(int i=1;i<=2*n;i+=2)
			if(a[i]*a[4*n-i+1]!=num||a[i]!=a[i+1]||a[4*n-i+1]!=a[4*n-i])
			{
				flag=1;
				break;
			}
		if(flag)
			printf("NO\n");
		else
			printf("YES\n");
	}
	return 0;
}

C. Common Divisors

题意：给你一个序列 $a$，有 $n$ 个数，你需要找出序列中所有数的约数个数，即这个约数能被序列中所有数整除。

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

输出：一个数，代表约数个数。

解析：大水题，求所有数的最大公约数的约数个数，注意一定要给所有变量开 $long\ long$ ！！

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
long long n;
long long a[401010],num,ans;
long long gcd(long long a,long long b)
{
 	if(b==0)
		return a;
	return gcd(b,a%b);
}
int main()
{
 	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
  		scanf("%lld",&a[i]);
	num=gcd(a[1],a[2]);
	for(long long i=3;i<=n;i++)
	{
		num=gcd(num,a[i]);
		if(num==1)
			break;
	}
	for(long long i=1;i*i<=num;i++)
		if(num%i==0)
		{
			ans++;
			long long j=num/i;
			if(i!=j)
				ans++;
		}
	printf("%lld",ans);
	return 0;
}

D. Remove the Substring

题意：给你两个字符串 $s$ 和 $t$，问你最多从 $s$ 中连续删除多少个字符，使得 $t$ 是 $s$ 的子序列。

输入：第一行一个字符串 $s$，第二行一个字符串 $t$。

输出：一个数，表示最多删除的连续字符数。

解析：开两个数组 $p$ 和 $q$，$p$ 存放从前往后扫时字符串 $t$ 中的字母在字符串 $s$ 中出现的位置，$q$ 存放从后往前扫时字符串 $t$ 中的字母在字符串 $s$ 中出现的位置，即得到的 $p$ 数组字符串 $t$ 中的每个字母在字符串 $s$ 中最早出现的下标，$q$ 数组同理，得到的是最晚出现的下标，用一个 $ans$ 求出开头，末尾，两字符之间的字符数的最大值，即时答案。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
char a[201010],b[201010];
int len1,len2,ans;
int p[201010],q[201010];
int main()
{
	scanf("%s\n%s",a,b);
	len1=strlen(a);
	len2=strlen(b);
	int tot=0;
	for(int i=0;tot<len2;i++)
		if(a[i]==b[tot])
			p[tot++]=i;// p存放从前往后扫时字符串b中的字母在字符串a中出现的位置
	ans=max(ans,len1-1-p[tot-1]);//长度减去b中最后一个字符在a中出现最早的位置，即求末尾那一截
	tot=len2;
	for(int i=len1;i--;)
		if(a[i]==b[tot-1])
			q[--tot]=i;// q存放从后往前扫时字符串b中字母在字符串a中出现的位置
	ans=max(ans,q[0]);//求开头那一截
	// 这样得到的p数组是字符串t中的每个字母在字符串s中最早出现的下标
    // q数组同理，得到的是最晚出现的下标
    for(int i=0;i<len2-1;i++)
		ans=max(ans,q[i+1]-p[i]-1);//求两个字符中间隔得长度
	printf("%d\n",ans);
	return 0;
}

E. Boxers

题意：给你一个 $n$ 个数的序列，你可以使序列中任意一个数加 $1$ 或减 $1$，询问经过这样操作后的序列最多有多少个不同的数。

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

输出：一个数，经过这样操作后的序列最多有多少个不同的数。

解析：用一个桶，先把序列排序，对于序列中每一个数 $x$，判断桶中 $x-1,x,x+1$ 是否已经有值，如果没有，就 $ans++$，标记这个值。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
using namespace std;
int a[150005],vis[150005],n;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		if(vis[a[i]-1]==0&&a[i]>1)
		{
			ans++;
			vis[a[i]-1]=1;
		}
		else if(vis[a[i]]==0)
		{
			ans++;
			vis[a[i]]=1;
		}
		else if(vis[a[i]+1]==0)
		{
			ans++;
			vis[a[i]+1]=1;
		}
	}
	printf("%d\n",ans);
	return 0;
}