A - Circle of Students
题意：判断是否是1,2,3...n的排列或者n,n-1...2,1的排列
思路1：分类讨论，如果是递增的，ai-i的值固定，如果递减，ai+i的值固定
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=b;i>=a;i--) using namespace std; #define ll long long const int N=3e5+5; const int mod = 998244353; int T,n,a[101010],flag; ll rd() { ll x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } int main() { T=rd(); while(T--) { n=rd(); flag=1; rep(i,1,n) a[i]=rd(); rep(i,2,n) { if((a[i]-a[1]+n)%n!=(i-1)) flag=0; } if(flag) { printf("YES\n"); continue; } flag=1; rep(i,2,n) { if((a[i]+i)%n!=(a[1]+1)%n) flag=0; } if(!flag) printf("NO\n"); else printf("YES\n"); } }
思路2：直接做
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=b;i>=a;i--) using namespace std; #define ll long long const int N=3e5+5; const int mod = 998244353; int T,n,a[101010],flag; ll rd() { ll x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } int main() { T=rd(); while(T--) { n=rd(); flag=1; rep(i,1,n) a[i]=rd(); rep(i,2,n) { if(a[i]-1==a[i-1]) continue; else if(a[i]==1&& a[i-1]==n) continue; flag=0; } if(flag) { printf("YES\n"); continue; } flag=1; rep(i,2,n) { if(a[i]+1==a[i-1]) continue; else if(a[i]==n&& a[i-1]==1) continue; flag=0; } if(!flag) printf("NO\n"); else printf("YES\n"); } }
B - Equal Rectangles
题意：给你4*n个木棍，问你是否能组成n个面积相等的矩形
思路：按照边长排序，每次取头上的两根和尾巴的两根进行判断。
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=b;i>=a;i--) using namespace std; #define ll long long const int N=3e5+5; const int mod = 998244353; int T,n,a[101010],flag; ll rd() { ll x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } int main() { T=rd(); while(T--) { n=rd();n=4*n; int ans=0; rep(i,1,n) a[i]=rd(); sort(a+1,a+1+n); flag=1; for(int i=1;i<=n/2;i+=2) { if(a[i]!=a[i+1]||a[n-i]!=a[n-i+1]) flag=0; if(ans==0) ans=a[i]*a[n-i]; else if(ans!=a[i]*a[n-i]) flag=0; } if(flag) printf("YES\n"); else printf("NO\n"); } }
C - Common Divisors
题意：求n个数的gcd的因子个数
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=b;i>=a;i--) using namespace std; #define ll long long const int N=3e5+5; const int mod = 998244353; int T,n,a[101010],flag; ll x,ans; ll rd() { ll x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } ll gcd(ll a,ll b ) { if(a==0) return b; return gcd(b%a,a); } int main() { while(~scanf("%d",&n)) { rep(i,1,n) { x=rd(); if(i==1) { ans=x; } else { ans=gcd(x,ans); } } int an=0; rep(i,1,sqrt(ans)) if(ans%i==0) { if(ans%i==0) an++; if(ans/i!=i) an++; } printf("%d\n",an); } }
Codeforces Round #579 (Div. 3)
原文：https://www.cnblogs.com/The-Pines-of-Star/p/11355608.html
