CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
[[https://codeforces.com/contest/1312|Educational Codeforces Round 83 (Rated for Div. 2)]]

====== A. Two Regular Polygons ======

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

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

<hidden><code cpp>
#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;
}
</code></hidden>
\\

====== B. Bogosort ======

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

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

<hidden><code cpp>
#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;
}
</code></hidden>
\\

====== C. Adding Powers ======

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

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

<hidden><code cpp>
#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;
}
</code></hidden>
\\

====== D. Count the Arrays ======

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

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

<hidden><code cpp>
#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;
}
</code></hidden>
\\

====== E. Array Shrinking ======

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

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

<hidden><code cpp>
#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;
}
</code></hidden>
\\
CVBB ACM Team

用户工具

站点工具

页面工具
