题目链接
分数:1400
题目描述
输入 $T(≤1e4)$ 表示$T$组数据。所有数据的$n$之和$≤2e5$。每组数据输入$n(1≤n≤2e5)$和长为$n$的数组$a(0<a[i]<1e9)$。每次操作你可以把$a[i]+=a[i]\%10$。你可以操作任意次,相同$a[i]$也可以操作多次。能否使所有$a[i]$都相等?输出$Yes/No$。
样例
输入样例1
10
2
6 11
3
2 18 22
5
5 10 5 10 5
4
1 2 4 8
2
4 5
3
93 96 102
2
40 6
2
50 30
2
22 44
2
1 5
输出样例1
Yes
No
Yes
Yes
No
Yes
No
No
Yes
No
算法
(暴力) $O(n)$
这道题直接找规律暴力枚举就好了。我们发现个位数是$0$或者是$5$时,只需要做一次操作就行,并且之后都是不能改变的了(因为个位数变成了$0$)。而其他的数字,都会在有限次操作内变成$2$,我们只需要将所有数的个位都变成$2$,那么当前的$2$需要再通过$4$次操作变成$2$,前面的数会增加$2$,所以只需要判断所有的数将个位数去掉后是不是都相差$2$.
C++ 代码
代码链接
#include<bits/stdc++.h>
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
const int N = 2e5+10, M = N * 2, INF = 0x3f3f3f3f, mod = 1e9 + 7;
int n, m;
int w[N];
void solve()
{
cin>>n;
bool flag = false;
for(int i=0;i<n;i++) cin>>w[i];
for(int i=0;i<n;i++){
if(w[i]%10==0 || w[i]%10==5){
flag = true;
w[i]+=w[i]%10;
}else{
while(w[i]%10!=2){
w[i]+=w[i]%10;
}
}
}
if(flag){
for(int i=0;i<n;i++)
if(w[i]%10!=0 || w[i]!=w[0]){
cout<<"No"<<endl;
return ;
}
cout<<"Yes"<<endl;
return ;
}
sort(w,w+n);
for(int i=0;i<n;i++){
int tmp = w[i] / 10 - w[0] / 10;
if(tmp%2){
cout<<"No"<<endl;
return ;
}
}
cout<<"Yes"<<endl;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}