Moe's CF Life

喵~ 主人，欢迎来到我的题解小屋！今天我们要一起解决的是一道叫做 "3SUM" 的有趣问题，编号是 1692F。别看它叫 3SUM，其实比经典的那个要简单可爱多啦，嘿嘿~

让咱们一起来看看怎么轻松搞定它吧！

题目大意

这道题是这样哒，喵~：

我们会得到一个包含 n 个正整数的数组 a。我们需要判断一下，能不能从这个数组里找到三个不同位置的数 a[i], a[j], a[k]，使得它们的和 a[i] + a[j] + a[k] 的个位数字是 3。

如果能找到，就开心地输出 "YES"；如果找遍了都找不到，就只好遗憾地输出 "NO" 啦。

举个栗子：

数组是 [20, 22, 19, 84]。
我们可以选 20, 84, 19。它们的和是 20 + 84 + 19 = 123。
哇！个位数是 3 耶！所以答案就是 "YES"。

题解方法

主人，你有没有发现一个关键点呀？我们只关心三个数加起来的个位数字是不是 3。

根据我们小学就学过的加法知识（喵呜~），一个和的个位数字，只由加数们的个位数字决定！比如说，12 + 35 = 47，它的个位数 7 就是 2 + 5 的结果。如果和超过10，比如 18 + 29 = 47，它的个位数 7 也是 (8 + 9) % 10 = 17 % 10 = 7 的结果。

所以，a[i] + a[j] + a[k] 的个位数是 3，等价于 (a[i] % 10 + a[j] % 10 + a[k] % 10) % 10 的结果是 3。

这一下问题就变得简单多啦！我们根本不需要关心每个数字到底有多大，只需要关心它的个位数（也就是 a[i] % 10 的值）。

个位数只有 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 这十种可能。

那么，我们的任务就变成了：从一堆 0 到 9 的数字里，选出三个数（可以重复，比如选两个 1 和一个 1），让它们的和的个位数是 3。

但是，题目要求我们选的三个数的下标 i, j, k 是不同的。这意味着，如果我们想选三个个位数都是 1 的数，我们就必须确保原数组里至少有三个个位数是 1 的数（比如 1, 11, 21）。

考虑到这一点，我们想一想，对于每一种个位数（比如 7），我们需要保留多少个呢？

如果我们要选三个个位数都是 7 的数，那我们需要原数组里至少有三个数结尾是 7。
如果我们要选两个个位数是 7 的和一个是 9 的，那我们需要至少两个结尾是 7 的数和一个结尾是 9 的数。

可以发现，对于任何一种个位数 d（0 到 9），我们最多只需要用到 3 个。因为我们总共只选三个数，所以一种个位数最多也只会被选中三次。如果原数组里有超过三个数都以 d 结尾（比如 1, 11, 21, 31, 41），那多出来的 31 和 41 对于凑数来说是多余的，因为我们已经有 1, 11, 21 可以用了。

所以，我们的策略就是：

统计原数组中，所有数字的个位数分别是多少，以及每种个位数（0-9）出现了多少次。
创建一个新的、小小的列表。对于每一种个位数 d，如果它在原数组中出现了 c 次，我们就往新列表里添加 min(3, c) 个 d。
这样，我们的新列表最多只会有 10 * 3 = 30 个数字。
在这个小列表上，我们就可以用最简单粗暴的方法——三重循环暴力枚举所有三个不同数字的组合，检查它们的和的个位数是不是 3。因为列表非常小，所以就算暴力枚举也快得飞起，喵~

这个方法是不是很巧妙呀？我们把一个可能很大的问题，缩小到了一个规模非常小的问题上！

题解代码

这是C++的解法，让本喵来给你逐行讲解吧~

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

void solve() {
    int n;
    std::cin >> n;
    
    // 1. 统计每种个位数的出现次数
    // counts[d] 表示个位数为 d 的数字有多少个
    std::vector<int> counts(10, 0);
    for (int i = 0; i < n; ++i) {
        int a;
        std::cin >> a;
        counts[a % 10]++;
    }

    // 2. 创建一个只包含必要个位数的小列表 b
    std::vector<int> b;
    for (int d = 0; d < 10; ++d) {
        // 对于每种个位数 d，我们最多只需要3个。
        // std::min(3, counts[d]) 确保我们不会添加超过3个。
        for (int i = 0; i < std::min(3, counts[d]); ++i) {
            b.push_back(d);
        }
    }

    // 3. 在小列表 b 上进行暴力枚举
    int m = b.size();
    for (int i = 0; i < m; ++i) {
        for (int j = i + 1; j < m; ++j) {
            for (int k = j + 1; k < m; ++k) {
                // 检查三个不同位置的数的和的个位数
                if ((b[i] + b[j] + b[k]) % 10 == 3) {
                    std::cout << "YES\n";
                    return; // 找到啦，直接结束函数
                }
            }
        }
    }

    // 4. 如果所有组合都试过了还没找到，那就是没有咯
    std::cout << "NO\n";
}

int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

代码的逻辑和我们刚才分析的思路一模一样，对吧？先把大问题变小，再用简单的方法解决小问题，这可是算法竞赛里非常有用的思想哦！

知识点介绍

这道题虽然简单，但也藏着一些重要的知识点呢，喵~

模运算 (Modulo Operation) 模运算就是求余数，符号是 %。这道题的核心就是利用了模运算的一个重要性质：和的模等于模的和的模。公式是：(A + B) % C = ((A % C) + (B % C)) % C 推广到三个数也是一样：(A + B + C) % 10 = ((A % 10) + (B % 10) + (C % 10)) % 10 这个性质让我们能够放心地只处理数字的个位数，而不用管数字本身有多大。
暴力枚举与剪枝/状态压缩 (Brute-Force with Pruning / State Reduction) 最直接的想法可能是对原数组进行三重循环，复杂度是 O(N³)。当 N 达到 2 * 10⁵ 时，这绝对会超时。我们的解法实际上是一种聪明的“剪枝”或“状态压缩”。我们没有直接在原数据上操作，而是提取了问题的本质——个位数，并根据“最多只需要3个相同个位数”的观察，大大压缩了需要搜索的数据规模。把一个大集合的问题，转化为一个小集合的等价问题，是解决很多难题的钥匙！我们把 N 个数的问题，变成了最多 30 个数的问题。
鸽巢原理 (Pigeonhole Principle) 虽然代码里没有直接用，但这个思想有助于我们理解为什么可以压缩数据。可以把10个个位数（0-9）看作10个“鸽巢”，把数组中的 n 个数看作 n 只“鸽子”。每只鸽子根据它的个位数飞进对应的巢里。我们要从这些巢里选出3只鸽子。鸽巢原理告诉我们，如果鸽子数量远大于鸽巢，那么一定有巢里有很多鸽子。而我们的解法更进一步：我们发现每个巢里的小鸽子，我们最多只需要关心3只就够啦！其他的都是一样的，可以不用管。就像一窝小猫咪里，挑三只出来玩，哪三只都一样可爱，喵~

好啦，这次的题解就到这里啦！希望本喵的讲解对主人有帮助。如果还有什么问题，随时可以再来找我哦！拜拜，喵~ (ฅ'ω'ฅ)

题目大意 ​

题解方法 ​

题解代码 ​

知识点介绍 ​

题目大意

题解方法

题解代码

知识点介绍