题解 P1008 【三连击】用C++模板元编程得出答案
Alex_Cui
2019-03-08 22:31:54
粗翻了一下题解, 发现都是正常方法, 没人用元编程写, 那我就写一下元编程的题解.
**(在最后给出完整的代码)**
首先, 我们先确定思路:
从题目我们可以知道, 三个三位数 $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必须是非负数).
```cpp
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$ 的值了.
```cpp
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)$, 将所有的结果进行逻辑与运算. 代码如下:
```cpp
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```了:
```cpp
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语句), 那么我们就需要定义一个判断, 然后特化这个模板:
```cpp
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```是为了在编译时展开递归(注意元编程的递归是可展开为一个非递归非循环函数, 这和运行时的递归不同).
```cpp
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()```就可以输出了.
以下是完整的代码:
```cpp
#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;
}
```