提示：建议您在 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; }

转载于:https://www.cnblogs.com/liuzongxin/p/11349973.html