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;
}