1998年NOIP普及组三连击问题解析与代码详解（洛谷P1008）

一、题目解读

1998年NOIP普及组三连击（洛谷P1008）要求寻找三个连续整数a、b、c（其中b=2a，c=3a），且这三个数的各位数字恰好组成1-9的排列（不重复且不包含0）。题目需输出符合条件的三连击组合，本质是数字组合与数位分析的典型问题。

二、解题思路

采用“枚举+验证”策略：

1. 范围枚举：从123开始至329（因3a≤999且需避免首位为0）遍历a；

2. 数位检查：定义isValid()筛除非100-999区间或含0的数字；

3. 唯一性验证：通过checkDigits()统计三数各位数字，确保1-9均出现一次。

核心逻辑利用数学关系简化计算，结合位运算提取数位，通过频次数组判断唯一性。

三、解题步骤

1. 初始化循环变量a，遍历[123,329]；

2. 跳过无效a（如超出范围或含0）；

3. 计算b=2a，c=3a并验证其有效性；

4. 调用checkDigits()检查三数各位数字是否覆盖1-9；

5. 满足条件则输出三连击组合。

步骤简洁高效，避免冗余计算。

四、代码与注释

#include <iostream>  
#include <cstring> // 用于memset函数  

using namespace std;  

// 检查数字是否在100-999且不含0  
bool isValid(int num) {  
    if (num < 100 || num > 999) return false;  
    while (num > 0) {  
        if (num % 10 == 0) return false;  
        num /= 10;  
    }  
    return true;  
}  

// 检查三数各位数字是否恰好为1-9各一次  
bool checkDigits(int a, int b, int c) {  
    int digits[10] = {0};  
    for (int num : {a, b, c}) {  
        while (num > 0) {  
            int digit = num % 10;  
            if (++digits[digit] > 1) return false;  
            num /= 10;  
        }  
    }  
    for (int i = 1; i <= 9; ++i) {  
        if (digits[i]!= 1) return false;  
    }  
    return true;  
}  

int main() {  
    for (int a = 123; a <= 329; ++a) {  
        if (!isValid(a)) continue;  
        int b = 2 * a;  
        int c = 3 * a;  
        if (isValid(b) && isValid(c) && checkDigits(a, b, c)) {  
            cout << a << " " << b << " " << c << endl;  
        }  
    }  
    return 0;  
}

五、总结

该解法巧妙利用数学关系减少搜索空间，结合数位分解与频次统计高效解题。代码简洁易读，适合算法竞赛新手学习枚举与数位处理的结合技巧。时间复杂度O(n)，n为枚举范围（约200次循环）。