蓝桥杯历届题目及解析汇总（附思路及代码）【点击此进入】

---

蓝桥杯，ACM算法学习【文档】【视频】大放送【点击此进入】

---

第四题

标题： 数的分解（本题总分：10 分）

【问题描述】 把 2019 分解成 3 个各不相同的正整数之和，并且要求每个正整数都不包 含数字 2 和 4，一共有多少种不同的分解方法？ 注意交换 3 个整数的顺序被视为同一种方法，例如 1000+1001+18 和 1001+1000+18 被视为同一种。 【答案提交】 这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

解题思路：

暴力题，但是需要注意的是去重，题目说了不同顺序而数字相同的情况只能算一种，比赛的时候真的把这道题想简单了，以为只用一个标记数组就可以去重，不知道的是还有可能有这种情况：假设 a + b + c == 2019，然后再假设 d + e + f == 2019，如果这个时候 a + d + f == 2019，这其实可以算是一种新的情况，但是如果只采用一个标记数组的话会认为 a, d, f 这三个数字都出现过，即漏了这种情况。在这里我将 a b c 通过 10 进制运算的形式组成一个新的数字，然后放在 mark 标记数组里面，如果下一次有数字符合 a + b + c ==2019 ，则将他们也组成一个新的数字，然后在已有的 mark 数组里面找，如果找到了，则证明重合，否则就是新情况，放入 mark 数组中记录。 上面是之前的想法，把问题想复杂了，感谢评论区小伙伴的指正，我们可以让 3 个变量（假设为 a, b, c）从 1 开始枚举，即暴力，这样的出来的结果肯定会有重复，重复原因就是 a 可能和 b、c 重合，同样，b 也可能和 a、c 出现重合，c 也可能和 a、b 重合。即需要把结果除以 6 。 另一种更简单的想法则是在循环时就控制 a, b 和 c 的起始值，即 a 从 1 开始， b 从 a + 1 开始，c 从 b + 1 开始。这样 a, b 和 c 就不会相等，同时也不会出现重复，因为每一次循环得到的 a, b 和 c 和之前出现过的 a, b 和 c 中必定至少有一个数不同，这样得到的结果就是最终结果。从时间复杂度上将，第二种思路是比第一种思路快的。

代码：

#include <iostream> #include <cmath> #include <algorithm> using namespace std; // 判断某个数字位中是否包含 2 和 4 bool judge(int n) { int t; while (n) { if (((t = n % 10) == 2) || t == 4) { return true; } n /= 10; } return false; } bool check(int a, int b, int c) { // 有数字出现 2 和 4，或者出现重复数字，返回 0 if (judge(a) || judge(b) || judge(c) || a == b || a == c || b == c) { return false; } return true; } /** * 第一种思路：直接枚举后将结果 / 6 */ int main() { int res = 0; for (int i = 1; i < 2018; i++) { for (int j = 1; j < 2018; j++) { for (int k = 1; k < 2018; k++) { if (i + j + k == 2019) { res += check(i, j, k); } } } } cout << (res / 6) << endl; return 0; } /** * 第二种思路：循环的时候控制变量的起始值： */ int main() { int res = 0; for (int i = 1; i < 2018; i++) { for (int j = i + 1; j < 2018; j++) { for (int k = j + 1; k < 2018; k++) { if (i + j + k == 2019) { res += check(i, j, k); } } } } cout << res << endl; return 0; }

答案：40785

蓝桥杯，ACM算法进阶资料大放送