哈喽，各位主人！今天由我，你们最贴心的小猫娘，来给大家讲解一道来自 Codeforces 的有趣问题喵~ 准备好跟着我的思路，一起解开这道题的谜题了吗？嘿嘿，那我们开始吧！

C. Divisibility by Eight (整除 8)

题目大意

这道题是这样的喵：给你一个很大的非负整数 n（最多有 100 位数字哦），它没有前导零。你的任务是从这个数里删除一些数字（也可以一个都不删），让剩下的数字按原来的顺序组成一个新数。

这个新数需要满足几个条件：

1. 至少要有一位数字。
2. 不能有前导零（除非这个数本身就是 0）。
3. 最最重要的一点：它必须能被 8 整除！

如果能找到这样的数，你就输出 "YES"，然后在下一行打印出这个数。如果找不到，那就只好输出 "NO" 啦。

举个栗子： 如果输入的数是 3454，我们可以删掉一个 5，剩下 344。因为 344 可以被 8 整除（344 = 8 * 43），所以这是一个合法的答案。

听起来是不是有点像在长长的毛线里找一段能打成漂亮蝴蝶结的线段呢？喵~

解题思路

一看到“被 8 整除”，聪明的你是不是立刻想到了什么数学小知识呀？对啦！就是一个数能否被 8 整除的判断方法！

一个整数能被 8 整除，当且仅当它最后三位数字组成的数能被 8 整除。

为什么呢？因为 1000 = 125 * 8，所以任何一个大于 999 的数 N 都可以写成 1000 * k + xyz 的形式，其中 xyz 是它的末三位数。因为 1000 * k 总是 8 的倍数，所以 N 能不能被 8 整除，就完全取决于 xyz 能不能被 8 整除啦。

这个性质对我们解题超级有帮助！

如果我们能从原数 n 中通过删除数字得到一个能被 8 整除的长长的数 S，那么 S 的末三位数（或者末两位、末一位）也一定是一个能被 8 整除的数，并且它也同样可以从原数 n 中通过删除得到！

这说明什么呢？我们根本不需要去寻找所有可能构成的长数字，我们只需要检查一下，能不能从原数 n 中找到一个长度不超过 3 并且能被 8 整除的子序列就足够了！

所以，我们的策略就变得非常简单清晰了喵：

1. 我们把所有小于 1000 的、能被 8 整除的数都找出来（也就是 0, 8, 16, 24, ..., 992）。
2. 然后，我们一个个地检查这些数，看它们是不是原数字字符串 n 的子序列。
3. 只要我们找到了第一个符合条件的数，它就是我们的答案！直接输出 "YES" 和这个数，然后开心地结束程序。
4. 如果找遍了从 0 到 999 所有的 8 的倍数，都没有在 n 中找到对应的子序列，那就说明真的没办法啦，只好遗憾地输出 "NO"。

这个方法是不是很直接呀？就像猫咪找玩具一样，直接扑向最可能的目标就好了，不用满屋子乱转，嘿嘿。

题解代码

这是 C++ 的实现代码，我已经加上了可爱的注释，方便主人理解哦~

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

// 这个函数是用来检查 t 是不是 s 的子序列的喵
// 它用两个指针在两个字符串上移动
// 如果字符匹配，t 的指针就前进一步
// s 的指针每次都会前进
// 如果 t 的指针能走到头，说明 t 的所有字符都在 s 中按顺序找到了
bool isSubsequence(const std::string& s, const std::string& t) {
    int s_ptr = 0; // 指向原字符串 s 的指针
    int t_ptr = 0; // 指向目标子序列 t 的指针
    while (s_ptr < s.length() && t_ptr < t.length()) {
        if (s[s_ptr] == t[t_ptr]) {
            t_ptr++; // 找到一个匹配的字符，目标指针前进！
        }
        s_ptr++; // 不管匹不匹配，原字符串指针都要前进
    }
    // 如果 t_ptr 等于 t 的长度，说明 t 的所有字符都被找到了
    return t_ptr == t.length();
}

int main() {
    // 加速输入输出，让程序跑得像小猫一样快~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::string n_str;
    std.cin >> n_str;

    // 我们来遍历所有小于 1000 的 8 的倍数
    // 从 0 开始，每次加 8
    for (int i = 0; i < 1000; i += 8) {
        // 把数字 i 转换成字符串
        std::string multiple_str = std::to_string(i);
        // 检查这个 8 的倍数是不是原数字字符串的子序列
        if (isSubsequence(n_str, multiple_str)) {
            // 找到啦！太棒了！
            std::cout << "YES\n";
            std::cout << multiple_str << "\n";
            return 0; // 找到一个就够了，收工回家~
        }
    }

    // 如果循环跑完了还没找到，说明真的没有答案了
    std::cout << "NO\n";

    return 0;
}

知识点介绍

这道题主要涉及到了两个小知识点，我们来复习一下吧！

1. 整除 8 的性质 (Divisibility by 8)

   • 规则：一个正整数能被 8 整除，当且仅当其末三位数字所组成的数能被 8 整除。对于位数小于 3 的数，直接判断其本身能否被 8 整除。
   • 原理：1000 = 8 × 125。任何一个数 N 都可以表示为 N = 1000 × a + b，其中 b 是 N 的末三位数。因为 1000 × a 必然是 8 的倍数，所以 N 是否能被 8 整除，完全取决于 b 是否能被 8 整除。
   • 这个性质对于处理大数问题非常有用哦！

2. 子序列 (Subsequence)

   • 定义：子序列是指从一个序列中删除零个或多个元素后，剩下的元素保持原有相对顺序所形成的新序列。
   • 举例：比如字符串 s = "banana"，那么 "bana", "bnn", "aa" 都是它的子序列。但是 "bnaa" 就不是，因为两个 a 的相对顺序改变了。
   • 在我们的题目里，就是从输入的数字串里按顺序挑出几个数字，组成一个新的数。就像从一长串猫爪印里 🐾🐾🐾🐾 挑出第 1 个和第 3 个 🐾 🐾 来看，它们就构成了一个子序列喵~

好啦，今天的讲解就到这里啦！希望主人能够喜欢。如果还有其他问题，随时都可以来找我哦！喵~ (ฅ'ω'ฅ)