提示：建议您在 Codeforces 官网 （codeforces.com & codeforc.es）查看题目后再来看这篇题解，以获得更加体验。

Problem A

题意

有一个长度为 \(n\) 的数组 \(a\)，是 \(1\)~\(n\) 的一个排列。问这个排列满不满足

\[a_k=1(1\leq k \leq n),a_i+1=a_{i+1}(1 \leq i \leq k-2),a_j+1=a_{j+1}(k \leq j \leq n-1) \]

或

\[a_k=1(1\leq k \leq n),a_i-1={a_i+1}(1\leq i \leq k-1),a_j-1=a_{j+1}(k+1\leq j \leq n-1)$$。 多组数据。数据组数 $\leq 200$，$1 \leq n \leq 200$。 ### 思路 直接模拟即可。 ### 代码 ``` # include <bits/stdc++.h> # define rr register const int N=210; int T; int n; int a[N]; inline bool check1(void){ int id; for(rr int i=1;i<=n;++i){ if(a[i]==1){ id=i; break; } } for(rr int i=2;i<id;++i){ if(a[i]-a[i-1]!=1){ return false; } } for(rr int i=id+1;i<=n;++i){ if(a[i]-a[i-1]!=1){ return false; } } return true; } inline bool check2(void){ int id; for(rr int i=1;i<=n;++i){ if(a[i]==1){ id=i; break; } } for(rr int i=2;i<=id;++i){ if(a[i-1]-a[i]!=1){ return false; } } for(rr int i=id+2;i<=n;++i){ if(a[i-1]-a[i]!=1){ return false; } } return true; } int main(void){ scanf("%d",&T); while(T--){ scanf("%d",&n); for(rr int i=1;i<=n;++i){ scanf("%d",&a[i]); } if(check1()||check2()){ puts("YES"); }else{ puts("NO"); } } return 0; } ``` ## Problem B ### 题意 给你 $4n$ 根木棍，问能否恰好拼成 $n$ 个面积相同的矩形。不能砍断木棍，不能用两根棍子拼接。 ### 思路 首先，一个矩形必须要用 $4$ 根木棍拼成。而且这 $4$ 根木棍可以分为 $2$ 组，且每组的长度相等。 那么，拼成 $n$ 个矩形就需要把 $4n$ 根木棍分成 $2n$ 组。显然，如果分组失败，那么一定不能拼成。 如果分组成功呢？ 我们来看，如果有 $4$ 组木棍，长度是 $1,2,5,10$。它们是可以拼成的—— $1\times 10 = 2\times 5$。 如果有 $8$ 组木棍，长度是 $1,2,3,6,9,18$，它们也是可以拼成的—— $1\times 18 = 2 \times 9 = 3 \times 6$。 如果有 $3$ 组木棍，长度是 $1,2,3,4$ 呢？他们是不可以的。 于是试了几组数据之后，我们得到了一个宝贵~~没啥卵用~~的性质：设每组如果所有 $a_i \times a_{n-i+1}$ 都是相等的，那么可以拼成，否则不可以。 ``` # include <bits/stdc++.h> # define rr register const int N=410; int a[N]; int n; int T; int len[N],m; int sum[10010]; int main(void){ scanf("%d",&T); while(T--){ m=0; memset(sum,0,sizeof(sum)); memset(len,0,sizeof(len)); scanf("%d",&n); n*=4; for(rr int i=1;i<=n;++i){ scanf("%d",&a[i]); ++sum[a[i]]; } int l,r,base; for(rr int i=1;i<=n;++i){ if(!sum[a[i]]) continue; if(sum[a[i]]%2){ goto BadEnd; } for(rr int j=1;j<=sum[a[i]]/2;++j) len[++m]=a[i]; sum[a[i]]=0; } std::sort(len+1,len+1+m); l=2,r=m-1; base=len[1]*len[m]; while(l<=r){ if(len[l]*len[r]!=base){ goto BadEnd; } ++l,--r; } puts("YES"); continue; BadEnd:puts("NO"); } return 0; } ``` ## Problem C ### 题意 给你一个长度为 $n$ 的数组 $a$，求 $\gcd(a)$ 有多少个因数。 $n\leq 10^5 a_i \leq 10^{12}$ ### 思路 求出整个数组的 $\gcd$ 很简单。重点在于如何求出 $\gcd(a)$ 有多少个因数。 有这样一条定理： $$n= \Pi_{i=1}^{m} p_i^{k_i}\]

\(n\) 为 \(>1\) 的正整数，\(p_i\) 是质数，\(k_i\) 是正整数。

那么 \(n\) 的因数个数则为 \(\Pi_{i=1}^{m}(k_i+1)\)。

于是问题就解决了。

# include <bits/stdc++.h>
# define rr register
# define int long long
const int N=400010;
int a[N];
int n;
int ans=1;
inline void DoPrimes(int k){
	for(rr int i=2;i*i<=k;++i){
		if(k%i)
			continue;
		int sum=0;
		while(k%i==0){
			++sum;
			k/=i;
		}
		ans*=(sum+1);
	}
	if(k!=1)
		ans*=2;
	return;	
}
signed main(void){
	scanf("%I64d",&n);
	for(rr int i=1;i<=n;++i){
		scanf("%I64d",&a[i]);
	}
	int GCD=std::__gcd(a[1],a[2]);
	if(n==1){
		GCD=a[1];
		goto AHAK;
	}
	for(rr int i=2;i<n;++i){
		GCD=std::__gcd(GCD,a[i+1]);
	}
	AHAK:
	if(GCD==1){
		printf("1");
		return 0;
	}	
	DoPrimes(GCD);
	printf("%I64d",ans);	
	return 0;
}

Problem D

没做出来 T^T

Problem E

题意

给你一个可能有重复元素的数组 \(a\)，元素都是正整数，长度为 \(n\)。你可以修改数组中的每一个元素，每个元素只能修改一次，可以令其 \(+1\) 或 \(-1\)，不能修改为
\(0\)。问在最优操作下这个数组可以有多少种不同的数。

思路

sb 题。

对于 \(a_i (1\leq a_i \leq n)\)，如果当前数组中没有 \(a_i - 1\)，则修改为 \(a_i - 1\)，这里的 \(a_i\) 不能为 \(1\)。否则继续判断数组中是否存在 \(a_i,a_i+1\)。

# include <bits/stdc++.h>
# define rr register
const int N=150010;
int a[N];
int sum[N];
bool use[N];
int ans;
int n;
int main(void){
	scanf("%d",&n);
	for(rr int i=1;i<=n;++i)
		scanf("%d",&a[i]),++sum[a[i]];
	for(rr int i=1;i<=150000;++i){
		if(sum[i]&&i-1>0&&!use[i-1]){
			++ans,use[i-1]=true,--sum[i];
		}	
		if(sum[i]&&!use[i]){
			++ans,use[i]=true,--sum[i];
		}
		if(sum[i]&&!use[i+1]){
			++ans,use[i+1]=true,--sum[i];
		}
	}
	printf("%d",ans);
	return 0;
}