【题解】CF1714E Add Modulo 10

· · 题解

E.Add Modulo 10

题目描述：

原题面

题目分析：

我们通过打表可以发现，数可以分为两类：

因为这两类数内部可以相互转化，但是不能跨类别转化，所以当同时存在两类数就判负。

考虑以 0 或 5 结尾的数：显然只有以 5 结尾的数的改变有意义，而且只可以改变一次，所以就对这些数全部更改一次，然后判断整个序列是否相等就好了。

考虑另一类数：我们发现他们的结尾数字是有规律的 2 - 4 - 8 - 6。而且我们也会发现一个事实，当两个数仅最后一位不一样时，这两个数无论如何变化都不能相等。

所以这也就启发我们：他们最后变成的相等的数一定是最大值，并且时最大值将最后一位变成 2 - 4 - 8 - 6 中的某一个。

那么就每个数判一下能不能变成最大值就好了。

代码详解：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e5+5;
int fx[10] = {2,4,6,8};
int a[MAXN];
signed main(){
    int t;
    scanf("%lld",&t);
    while(t--){
        int n;
        scanf("%lld",&n);
        int mx = 0; 
        bool flag_1 = false,flag_5 = false;
        for(int i=1; i<=n; i++){
            scanf("%lld",&a[i]);
            int h = a[i] % 10;  
            if(h == 5 || h == 0)    flag_5 = true;
            else{
                if(h != 2 && h != 4 && h != 8 && h != 6)  //把这些数都变成 2 - 4 - 8 - 6 结尾的数 
                    a[i] += h;
                flag_1 = true;
            }
            mx = max(mx,a[i]);
        }
        if(flag_5 && flag_1){
            printf("NO\n");
            continue;
        }
        else if(flag_5){  //只有 0,5 结尾的数，直接暴力改 
            bool flag = false;
            for(int i=1; i<=n; i++){
                a[i] += (a[i] % 10);
            }
            for(int i=2; i<=n; i++){
                if(a[i] != a[1]){
                    flag = true;
                    break;
                }
            }
            if(!flag)   printf("YES\n");
            else    printf("NO\n");
            continue;
        }
        bool flag = false;
        for(int i=1; i<=n; i++){
            if(a[i] < mx){  //判断 a[i] 是否可以变成 mx 
                int pos = (a[i] % 10) / 2 - 1;   //将最后一位变成 2 
                while(pos != 1 && a[i] < mx){
                    a[i] += (a[i] % 10);
                    pos = (pos + 1) % 4;
                }
                if(a[i] > mx){
                    printf("NO\n");
                    flag = true;
                    break;
                }
                a[i] = a[i] + (mx - a[i])/20 * 20;  //变一轮是加 20，所以直接变 
                pos = (a[i] % 10) / 2 - 1;   //让 a[i] 尽可能变大，使得它不超过 mx 
                while(a[i] < mx){
                    a[i] += (a[i] % 10);
                    pos = (pos + 1) % 4;
                }
                if(a[i] > mx){
                    printf("NO\n");
                    flag = true;
                    break;
                }
            }
        }
        if(!flag)
            printf("YES\n");
    }
    return 0;
}