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

Alex_Cui · 2019-03-08 22:31:54 · Solution

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

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

首先, 我们先确定思路:

从题目我们可以知道, 三个三位数 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必须是非负数).

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 的值了.

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), 将所有的结果进行逻辑与运算. 代码如下:

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了:

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语句), 那么我们就需要定义一个判断, 然后特化这个模板:

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是为了在编译时展开递归(注意元编程的递归是可展开为一个非递归非循环函数, 这和运行时的递归不同).

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()就可以输出了.

以下是完整的代码:

#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;
}