题目链接
分数：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;
}