给你nnn 根火柴棍,你可以拼出多少个形如A+B=CA+B=CA+B=C 的等式?等式中的AAA、BBB、CCC 是用火柴棍拼出的整数(若该数非零,则最高位不能是000)。用火柴棍拼数字0∼90\sim90∼9 的拼法如图所示:
注意:
加号与等号各自需要两根火柴棍;如果 A ≠ B A\neq BA=B,则 A + B = C A+B=CA+B=C 与 B + A = C B+A=CB+A=C 视为不同的等式( A , B , C ≥ 0 A,B,C\geq0A,B,C≥0); n nn 根火柴棍必须全部用上。 输入格式一个整数n(1≤n≤24)n(1 \leq n\leq 24)n(1≤n≤24)。
输出格式一个整数,能拼成的不同等式的数目。
样例 #1 样例输入 #1 14 样例输出 #1 2 样例 #2 样例输入 #2 18 样例输出 #2 9 提示【输入输出样例 1 解释】
222 个等式为0+1=10+1=10+1=1 和1+0=11+0=11+0=1。
【输入输出样例 2 解释】
999 个等式为
0+4=40+4=40+4=4、0+11=110+11=110+11=11、1+10=111+10=111+10=11、2+2=42+2=42+2=4、2+7=92+7=92+7=9、4+0=44+0=44+0=4、7+2=97+2=97+2=9、10+1=1110+1=1110+1=11、11+0=1111+0=1111+0=11。
noip2008 提高第二题
思路1. 暴力枚举 2. 回溯法 参考大佬题解。具体见下方代码及其注释。
代码 1. 暴力枚举 #include#include#include#include#define endl '\n'using namespace std;int n;// 存储每个数字所需的火柴数// 只枚举到1000是因为1000 + () = ()就已经24根火柴了,n最大到24int a[1000] = { 6,2,5,5,4,5,6,3,7,6 };int main() {ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);cin >> n;// 计算出每个数字所需的火柴数for (int i = 10; i for (int j = 0; j continue;}if (a[i] + a[j] + a[i + j] + 4 == n) {// 用于debug//cout // 只需递归两层,枚举两个加数即可,和自动算出if (path.size() == 2) {int res = 0;res += a[path[0]];res += a[path[1]];res += a[path[0] + path[1]];if (res == n) {ans++;}return;}for (int i = 0; sum + i ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);cin >> n;n = n - 4;// 去掉加号和等号的4根火柴for (int i = 10; i