CF1714E Add Modulo 10

题目传送门

代码一遍AC真的很爽，样例都是一遍过

题意

每个测试点含多组测试数据。

对于每组测试数据

第1行 一个整数 $n$ ，表示该数据个数

第2行 $n$ 个整数，你需要判断是否符合题意的数据

对每组数据，你可以对其作若干次（可以为零）如下操作：

选取数据中的一个数 $a_i$ 将其替换为 $a_i + (a_i \bmod 10)$

问经过若干次变换后，该组数据能否全部相同

思路

首先让我们写段代码来枚举10个个位数在进行$a_i+(a_i \bmod 10)$后的情况

将其相同的数字对齐得到：

 0: [0 for ever]
 1: 2 4 8 16 22 24 28 36 42 44 48 56 62 64 68 76 82 84 88 96 102 
 2:   4 8 16 22 24 28 36 42 44 48 56 62 64 68 76 82 84 88 96 102 
 3:        6 12 14 18 26 32 34 38 46 52 54 58 66 72 74 78 86 92 94 98 106 
 4:     8 16 22 24 28 36 42 44 48 56 62 64 68 76 82 84 88 96 102 
 5: 10 
 6:          12 14 18 26 32 34 38 46 52 54 58 66 72 74 78 86 92 94 98 106 
 7:             14 18 26 32 34 38 46 52 54 58 66 72 74 78 86 92 94 98 106 
 9:                18 26 32 34 38 46 52 54 58 66 72 74 78 86 92 94 98 106 

我们会发现，一些数字进行若干次操作后会变得相同，所以将其归类：

 3: 6 12 14 18 26 32 34 38 46 52 54 58 66 72 74 78 86 92 94 98 106 
 6:   12 14 18 26 32 34 38 46 52 54 58 66 72 74 78 86 92 94 98 106 
 7:      14 18 26 32 34 38 46 52 54 58 66 72 74 78 86 92 94 98 106 
 9:         18 26 32 34 38 46 52 54 58 66 72 74 78 86 92 94 98 106 

 0: [ 0 for ever]
 5: [10 for ever]

 1: 2 4 8 16 22 24 28 36 42 44 48 56 62 64 68 76 82 84 88 96 102
 2:   4 8 16 22 24 28 36 42 44 48 56 62 64 68 76 82 84 88 96 102 
 4:     8 16 22 24 28 36 42 44 48 56 62 64 68 76 82 84 88 96 102 
 8:       16 22 24 28 36 42 44 48 56 62 64 68 76 82 84 88 96 102 

我们可以发现，同一个类别内的数一定可以通过若干次操作变得相等，但是不同类别的数字就不行

那，该怎么判断类别呢？

通过观察，可以发现第一类中，当十位为奇数，那么只要个位不是6的偶数就一定存在；而当十位为偶数，则只有个位为6的数存在

相对的，在第三类，十位为偶数时，只要个位不是6的偶数就一定存在；十位为奇数时，只存在末尾是6的偶数

可是，这样只能判断偶数属于哪一类，对奇数没用，该怎么办呢？

不难发现，奇数操作一次后一定是偶数，所以只需要再判断奇数操作后变为的偶数存在于哪一类即可

最终，只需要统计出三类对应的数对应的出现次数就好

代码

如果有两个及以上的类别都出现了，那么说明是变不成的

需要注意，即使只出现了第二类，但是它们不管怎么变，最多只能$+5$，所以需要再进行一下特判

#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+10;
int a[maxn];
int n;
int kind1,kind2,kind3;

void run()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i]+=(a[i]%2==0?0:a[i]%10);
        if(a[i]%10==0) kind2++;
        else if(((a[i]%100)/10)%2==1) 
        {
            if(a[i]%10==6) kind3++;
            else kind1++;
        }else
        {
            if(a[i]%10==6) kind1++;
            else kind3++;
        }
    }
    
    int l=(kind1>0)+(kind2>0)+(kind3>0);
    if(l==2 || l==3) cout<<"NO";
    else
    {
        if(kind1>0 || kind3>0) cout<<"YES";
        else
        {
            int num=a[1],find=1;
            for(int i=1;i<=n;i++)
            {
                if(a[i]!=num)
                {
                    find=0;
                    break;
                }
            }
            cout<<(find?"YES":"NO");
        }
    }
    cout<<endl;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        kind1=kind2=kind3=0;
        run();
    }
    return 0;
}