题目描述

难度分:$1300$

输入$T(\leq 10^3)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(3 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

判断是否存在$3$个下标不同的数$a[i],a[j],a[k]$，使得$a[i] + a[j] + a[k]$的个位数是$3$。

输出YES或NO。

输入样例

6
4
20 22 19 84
4
1 11 1 2022
4
1100 1100 1100 1111
5
12 34 56 78 90
4
1 9 8 4
6
16 38 94 25 18 99

输出样例

YES
YES
NO
NO
YES
YES

算法

枚举

比较容易发现的是这$3$个数具体长什么样并不需要知道，只需要知道所有元素的个位数是什么就可以了，因此在读入原始数组的时候就可以把每个元素$a[i]$模上$10$存到一个频数数组$cnt$中，$cnt[i]$表示个位为$i$的元素有多少个。

然后三重循环枚举三元组$(i,j,k)$的个位数字，只要满足$cnt[i],cnt[j],cnt[k]$都大于零，且$i+j+k$的个位数为$3$就行了。需要注意的是：如果三个数字的个位都不一样是绝对可以的。但如果其中有两个数字的个位$d$一样，就要保证有至少两个元素，它们的个位都是$d$。如果三个数字的个位都一样（都是$1$），那就要保证个位为$1$的元素至少有$3$个。

复杂度分析

时间复杂度

三重循环枚举三个元素的各位数，可以看成是一个常数比较大的算法，大概是$O(10^3)$。

空间复杂度

开辟了一个长度为$10$的频数数组$cnt$，$cnt[i]$表示个位为$i$的元素有多少个。可以看成是常数空间，为$O(1)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 200010;
int a[N];
int cnt[10] = {0};

int main() {
    int T, n;
    scanf("%d", &T);
    for(int index = 1; index <= T; index++) {
        scanf("%d", &n);
        memset(cnt, 0, sizeof cnt);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            cnt[a[i] % 10]++;
        }
        bool flag = false;
        for(int i = 0; i <= 9; i++) {
            for(int j = 0; j <= 9; j++) {
                for(int k = 0; k <= 9; k++) {
                    if(cnt[i] > 0 && cnt[j] > 0 && cnt[k] > 0 && (i + j + k) % 10 == 3) {
                        if(i == j && j == k && cnt[i] >= 3) {
                            flag = true;
                            break;
                        }else if(i == j && j != k && cnt[i] >= 2) {
                            flag = true;
                            break;
                        }else if(j == k && i != j && cnt[k] >= 2) {
                            flag = true;
                            break;
                        }else if(i == k && i != j && cnt[i] >= 2) {
                            flag = true;
                            break;
                        }else if(i != k && i != j && j != k) {
                            flag = true;
                            break;
                        }
                    }
                }
                if(flag) break;
            }
            if(flag) break;
        }
        if(flag) {
            puts("YES");
        }else {
            puts("NO");
        }
    }
    return 0;
}