[NOIP2008 提高组] 火柴棒等式

2023-12-21 19:33:24

[NOIP2008 提高组] 火柴棒等式

题目描述

给你 n n n 根火柴棍,你可以拼出多少个形如 A + B = C A+B=C A+B=C 的等式?等式中的 A A A B B B C C C 是用火柴棍拼出的整数(若该数非零,则最高位不能是 0 0 0)。用火柴棍拼数字 0 ~ 9 0\sim9 09 的拼法如图所示:

注意:

  1. 加号与等号各自需要两根火柴棍;
  2. 如果 A ≠ B A\neq B A=B,则 A + B = C A+B=C A+B=C B + A = C B+A=C B+A=C 视为不同的等式( A , B , C ≥ 0 A,B,C\geq0 A,B,C0);
  3. n n n 根火柴棍必须全部用上。

输入格式

一个整数 n ( 1 ≤ n ≤ 24 ) n(1 \leq n\leq 24) n(1n24)

输出格式

一个整数,能拼成的不同等式的数目。

样例 #1

样例输入 #1

14

样例输出 #1

2

样例 #2

样例输入 #2

18

样例输出 #2

9

提示

【输入输出样例 1 解释】

2 2 2 个等式为 0 + 1 = 1 0+1=1 0+1=1 1 + 0 = 1 1+0=1 1+0=1

【输入输出样例 2 解释】

9 9 9 个等式为

0 + 4 = 4 0+4=4 0+4=4 0 + 11 = 11 0+11=11 0+11=11 1 + 10 = 11 1+10=11 1+10=11 2 + 2 = 4 2+2=4 2+2=4 2 + 7 = 9 2+7=9 2+7=9 4 + 0 = 4 4+0=4 4+0=4 7 + 2 = 9 7+2=9 7+2=9 10 + 1 = 11 10+1=11 10+1=11 11 + 0 = 11 11+0=11 11+0=11

noip2008 提高第二题

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1010;
int path[N]; // 存储路径
int n;
int sums[N] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; // 存储火柴数

int res; // 方案数

void dfs(int x, int sum){
    if(sum > n) return ; // 剪枝
    
    
    if (x > 3){
        if ((path[1] + path[2] == path[3]) && sum == n){
            // for (int i = 1; i <= 3; i ++)
            //     printf("%d ", path[i]);
            // puts("");
            res ++;
        }
        
        return ;
    }
    
    for (int i = 0; i <= N; i ++){
        path[x] = i;
        dfs(x + 1, sum + sums[i]);
        
        // 回溯
        path[x] = 0;
    }
}

int main(){
    scanf("%d", &n);
    n -= 4; // 去掉=号和+号所用的四根火柴
    
    // 预处理每个数所需要的火柴数
    for (int i = 10; i <= N; i ++){
        sums[i] = sums[i % 10] + sums[i / 10];
    }
    
    dfs(1, 0);
    
    printf("%d\n", res);
    
    return 0;
}

文章来源:https://blog.csdn.net/qq_49821869/article/details/135138083
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。