A. Two Regular Polygons

顶点数$n,m$的正多边形，问是否可以使得顶点少的那个所有顶点与多的那个重合。

题解：能够整除即可以重合。

点击以显示 ⇲

点击以隐藏 ⇱

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		if(n%m)puts("NO");
		else puts("YES");
	}
	return 0;
}

B. Bogosort

给数组$a$重新排序使得对于所有$i\neq j, j - a_j\neq i - a_i$。

题解：从大到小输出即可。

点击以显示 ⇲

点击以隐藏 ⇱

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[105];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		sort(a+1,a+1+n);
		for(int i=n;i;i--)printf("%d ",a[i]);
		puts("");
	}
	return 0;
}

C. Adding Powers

长度$n$的数组$v$初始为$0$，第$i$步操作可以选择一个位置使得增加$k^i$，问是否可以到达给定局面。

题解：所有数字表示成$k$进制时，每一位最多为$1$即可。

点击以显示 ⇲

点击以隐藏 ⇱

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
typedef long long LL;
LL a[44];
bool hav[105];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		memset(hav,0,sizeof(hav));
		int n,k;
		scanf("%d%d",&n,&k);
		for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
		bool ok=1;
		for(int i=1;i<=n;i++)
		{
			int cnt=0;
			while(a[i])
			{
				if(a[i]%k>1){ok=0;break;}
				else if(a[i]%k)
				{
					if(hav[cnt]){ok=0;break;}
					else hav[cnt]=1;
				}
				cnt++,a[i]/=k;
			}
			if(!ok)break;
		}
		if(ok)puts("YES");
		else puts("NO");
	}
	return 0;
}

D. Count the Arrays

计数题。问长度为$n$、由数字$1$到$m$构成、有一个下标$i$在此之前严格上升此后严格下降、有且只有一对相同元素的数组有多少。

题解：有一对相同元素所以要选$n-1$个不同数字，之后最大的数字自动成为峰值，再从剩余$n-2$个数字中选一个作为重复数字，其余$n-3$个都有放左边和放右边两种选择。答案是$\binom{m}{n-1}\times(n-2)\times2^{n-3}$

点击以显示 ⇲

点击以隐藏 ⇱

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
typedef long long LL;
const LL P=998244353;
const int N=2e5+10;
LL inv[N],fac[N];
void init()
{
    fac[0]=1,inv[1]=1;
    for(int i=1;i<N;i++)
    fac[i]=fac[i-1]*i%P;
    for(int i=2;i<N;i++)
    inv[i]=inv[P%i]*(P-P/i)%P;
    inv[0]=1;
    for(int i=1;i<=N;i++)
    inv[i]=inv[i-1]*inv[i]%P;
}
LL C(LL x,LL y)
{
    if(x<y)return 0;
    return ((fac[x]*inv[y])%P*inv[x-y])%P;
}
int main()
{
	int n,m;
	init();
	scanf("%d%d",&n,&m);
	LL ans=C(m,n-1)*(n-2)%P;
	for(int i=1;i<=n-3;i++)ans=2*ans%P;
	printf("%lld\n",ans);
	return 0;
}

E. Array Shrinking

给出长度$n$的数组$a$。如果$a_i=a_{i+1}$可以用$a_i+1$取代他们。问任意多少次操作后数组的最短长度。

题解：区间dp。$dp[i][j]$为区间$[i,j]$的最短长度，用$a[i][j]$表示当该区间可以缩短为$1$时成为的数值。

点击以显示 ⇲

点击以隐藏 ⇱

#include<bits/stdc++.h>
using namespace std;
int n,a[505][505],dp[505][505];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i][i]),dp[i][i]=1;
	for(int len=2;len<=n;len++)
	{
		for(int i=1;i+len-1<=n;i++)
		{
			int j=i+len-1;
			dp[i][j]=len;
			for(int k=i;k<j;k++)
			{
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
				if(dp[i][k]==1&&dp[k+1][j]==1&&a[i][k]==a[k+1][j])
				a[i][j]=a[i][k]+1,dp[i][j]=1;
			}
		}
	}
	printf("%d\n",dp[1][n]);
	return 0;
}

CVBB ACM Team

目录

A. Two Regular Polygons

B. Bogosort

C. Adding Powers

D. Count the Arrays

E. Array Shrinking

CVBB ACM Team

用户工具

站点工具

目录

A. Two Regular Polygons

B. Bogosort

C. Adding Powers

D. Count the Arrays

E. Array Shrinking

页面工具