题解 P1008 【三连击】用C++模板元编程得出答案

评论

粗翻了一下题解, 发现都是正常方法, 没人用元编程写, 那我就写一下元编程的题解.

(在最后给出完整的代码)

首先, 我们先确定思路:

从题目我们可以知道, 三个三位数 $A,B,C$ 必须满足
$$ A:B:C=1:2:3$$
也就是可以得到
$$B=2×A$$
$$C=3×A$$
也就是说, 我们只需要知道 $A$ 的值就可以知道 $B, C$的值, 然后判断 $A,B,C$ 各数位是否重复或者等于 $0$ 即可.

而且我们知道 $A,B,C$ 都是三位数, 于是
$$99<A<B<C<1000$$

那么 $C$ 的最大取值为 $999$, 于是 $A$ 的最大取值为 $333$

即, $A$ 的百位最大为3, 也就是百位的遍历范围为 $[1, 3]$.

然后分别遍历十位和个位, 范围为 $[1, 9]$

为了确保遍历时是从小到大, 所以遍历的顺序是 百位$\rightarrow$十位$\rightarrow$个位.

先来编写获取传入的整数a的第n位(0表示个位, 1表示十位, 以此类推). 为了得到某一位上的值, 可以使用公式
$$(\frac{a}{10^n})\mod10$$
因为是元编程, 没有cmath库的pow函数用, 所以得先编写计算 $10^n$ 的值. 注意, 元编程没有for等循环语句, 所以我们使用递归代替循环, 注意要特化Pow10<0>防止无限递归(但是n必须是非负数).

1
2
3
4
5
6
7
8
template<int n>
struct Pow10 {
    static const int result = 10 * Pow10<n - 1>::result;
};
template<>
struct Pow10<0> {
    static const int result = 1;
}

然后我们就可以使用Pow10<n>::result来获取 $10^n$ 的值了.

1
2
3
4
template<int a, int n>
struct GetDigit {
    static const int result = (a / Pow10<n>::result) % 10;
};

然后我们需要开始编写判断部分, 假设传入三个整数a, b, c, 然后我们把a, b, c组成整数并得到三个整数:
$$A=100a+10b+c$$
$$B=2A$$
$$C=3A$$
接下来, 我们获取三个整数的每一位然后去比较. 那么我们就需要编写比较9个数字(3个3位数)的值是否有重复且不等于0.

需要对9个数字两两组合比较, 假设数字a, b, c, d, 那么我们就从$a$开始, 首先比较$(a,b)$, 保证$a\not=b$且$a\not=0$, 然后比较$(a,c)$, $(a,d)$, 这一步单独定义为将$a$依次和之后的数字比较, 然后从$b$比较$(b,c)$, $(b,d)$, 最后比较$(c,d)$, 将所有的结果进行逻辑与运算. 代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template<int first, int second, int ...other>
struct CheckDigit {
    static const bool result = CheckDigit<first, second>::result && CheckDigit<first, other...>::result;
};

template<int first, int second>
struct CheckDigit<first, second> {
    static const bool result = (first != second && first != 0);
};

template<int first, int second, int ...other>
struct CheckDigitAll {
    static const bool result = CheckDigit<first, second, other...>::result && CheckDigitAll<second, other...>::result;
};

template<int first, int second>
struct CheckDigitAll<first, second> {
    static const bool result = CheckDigit<first, second>::result;
};

然后我们就可以开始判断传入的a, b, c了:

1
2
3
4
5
6
7
template<int a, int b, int c>
struct Check {
    static const int v0 = a * 100 + b * 10 + c, v1 = v0 * 2, v2 = v0 * 3;
    static const bool result = CheckDigitAll<GetDigit<v0, 2>::result, GetDigit<v0, 1>::result, GetDigit<v0, 0>::result,
        GetDigit<v1, 2>::result, GetDigit<v1, 1>::result, GetDigit<v1, 0>::result,
        GetDigit<v2, 2>::result, GetDigit<v2, 1>::result, GetDigit<v2, 0>::result>::result;
};

到此为止, 所有的判断过程结束, 开始遍历过程, 在遍历过程中, 我们要确定一个print函数, 然后在运行的时候调用它, 如果经判断后成立, 那么就输出A, B, C, 否则就不输出. 因为是元编程, 所有没有if语句(C++17可以使用constexpr if语句), 那么我们就需要定义一个判断, 然后特化这个模板:

1
2
3
4
5
6
7
8
9
10
11
12
template<bool a, int v>
struct IfPrint {};

template<int v>
struct IfPrint<true, v> {
    static void print() { std::cout << v << " " << v * 2 << " " << v * 3 << std::endl; }
};

template<int v>
struct IfPrint<false, v> {
    static void print() {}
};

接下来我们就开始遍历, NumberEach1, NumberEach2, NumberEach3分别表示遍历百位, 十位, 个位的过程, 确保结果是从大到小的, 所以这里必须使用深度优先搜索, 同根节点从小到大, 注意特化百位的NumberEach1<3>, 以及十位和个位的NumberEach2<a, 9>, NumberEach3<a, b, 9>以防止无限递归, 函数定义为inline是为了在编译时展开递归(注意元编程的递归是可展开为一个非递归非循环函数, 这和运行时的递归不同).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
template<int a, int b, int c>
struct NumberEach3 {
    static inline void print() {
        IfPrint<Check<a, b, c>::result, a * 100 + b * 10 + c>::print();
        NumberEach3<a, b, c + 1>::print();
    }
};

template<int a, int b>
struct NumberEach3<a, b, 9> {
    static inline void print() {
        IfPrint<Check<a, b, 9>::result, a * 100 + b * 10 + 9>::print();
    }
};

template<int a, int b>
struct NumberEach2 {
    static inline void print() {
        NumberEach3<a, b, 1>::print();
        NumberEach2<a, b + 1>::print();
    }
};

template<int a>
struct NumberEach2<a, 9> {
    static inline void print() {
        NumberEach3<a, 9, 1>::print();
    }
};

template<int a>
struct NumberEach1 {
    static inline void print() {
        NumberEach2<a, 1>::print();
        NumberEach1<a + 1>::print();
    }
};

template<>
struct NumberEach1<3> {
    static inline void print() {
        NumberEach2<3, 1>::print();
    }
};

好的, 到此为止, 一切结束, 调用NumberEach1<1>::print()就可以输出了.

以下是完整的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>

template<int n>
struct Pow10 {
    static const int result = 10 * Pow10<n - 1>::result;
};

template<>
struct Pow10<0> {
    static const int result = 1;
};

template<bool a, int v>
struct IfPrint {};

template<int v>
struct IfPrint<true, v> {
    static void print() { std::cout << v << " " << v * 2 << " " << v * 3 << std::endl; }
};

template<int v>
struct IfPrint<false, v> {
    static void print() {}
};

template<int a, int n>
struct GetDigit {
    static const int result = (a / Pow10<n>::result) % 10;
};

template<int first, int second, int ...other>
struct CheckDigit {
    static const bool result = CheckDigit<first, second>::result && CheckDigit<first, other...>::result;
};

template<int first, int second>
struct CheckDigit<first, second> {
    static const bool result = (first != second && first != 0);
};

template<int first, int second, int ...other>
struct CheckDigitAll {
    static const bool result = CheckDigit<first, second, other...>::result && CheckDigitAll<second, other...>::result;
};

template<int first, int second>
struct CheckDigitAll<first, second> {
    static const bool result = CheckDigit<first, second>::result;
};

template<int a, int b, int c>
struct Check {
    static const int v0 = a * 100 + b * 10 + c, v1 = v0 * 2, v2 = v0 * 3;
    static const bool result = CheckDigitAll<GetDigit<v0, 2>::result, GetDigit<v0, 1>::result, GetDigit<v0, 0>::result,
        GetDigit<v1, 2>::result, GetDigit<v1, 1>::result, GetDigit<v1, 0>::result,
        GetDigit<v2, 2>::result, GetDigit<v2, 1>::result, GetDigit<v2, 0>::result>::result;
};

template<int a, int b, int c>
struct NumberEach3 {
    static inline void print() {
        IfPrint<Check<a, b, c>::result, a * 100 + b * 10 + c>::print();
        NumberEach3<a, b, c + 1>::print();
    }
};

template<int a, int b>
struct NumberEach3<a, b, 9> {
    static inline void print() {
        IfPrint<Check<a, b, 9>::result, a * 100 + b * 10 + 9>::print();
    }
};

template<int a, int b>
struct NumberEach2 {
    static inline void print() {
        NumberEach3<a, b, 1>::print();
        NumberEach2<a, b + 1>::print();
    }
};

template<int a>
struct NumberEach2<a, 9> {
    static inline void print() {
        NumberEach3<a, 9, 1>::print();
    }
};

template<int a>
struct NumberEach1 {
    static inline void print() {
        NumberEach2<a, 1>::print();
        NumberEach1<a + 1>::print();
    }
};

template<>
struct NumberEach1<3> {
    static inline void print() {
        NumberEach2<3, 1>::print();
    }
};

int main() {
    NumberEach1<1>::print();
    return 0;
}

Alex CuiSH退役OIer

岭上星空, 月下却无人