火柴棒等式

player-none

我只能想出以下代码，问号部分思路断了

1. #include <iostream>
   
2. 
   
3. using namespace std;
   
4. 
   
5. int main()
   
6. {
   
7.     int hcb={6,2,5,5,4,5,6,3,7,6};
   
8.     int n;
   
9.     cin>>n;
   
10.     n-=4;
    
11.     int t=n;
    
12.     while(n){
    
13.         ???
    
14.         for(int i=0;???;++i){
    
15.             n-=hcb[i];
    
16.         }
    
17.         ???
    
18.     }
    
19.     return 0;
    
20. }

复制代码

题：



链接：https://code.xueersi.com/codeup/topic/list?tidan_id=27&problem_code=T0301710&package_name=CSP-J%E7%AE%97%E6%B3%95%E8%BF%9B%E9%98%B6

不二如是

题目文字黏过来~

player-none

不二如是 发表于 2025-4-19 17:01
题目文字黏过来~

题目描述
给你n根火柴棍，你可以拼出多少个形如A+B=C的等式？等式中的ABC是用火柴棍评出来的整数（若该数非零，则最高位不能为0）。用火柴棍拼数字0~9的拼法如图所示：

注意：

1、加号与等号各自取两根火柴棍

2、如果A≠B，则A+B=C与B+A=C视为不同的等式（A,B,C≥0）

3、n根火柴棍必须全部用上

Clipboard Image.png
输入描述
一个整数n（1≤n≤24）
输出描述
一个整数，能拼成的不同等式的数目
样例1
输入
14
输出
2
样例2
输入
18
输出
9
提示

琅琊王朝

player-none 发表于 2025-4-19 17:48
题目描述
给你n根火柴棍，你可以拼出多少个形如A+B=C的等式？等式中的ABC是用火柴棍评出来的整数（若该 ...

@Fishc

FishC

琅琊王朝 发表于 2025-04-22 20:27
player-none 发表于 2025-4-19 17:48
题目描述
给你 ...

根据题意，我们需要找出所有满足A+B=C的火柴棍等式。以下是详细步骤和代码实现：

思路分析
1. 火柴棍数量预处理：每个数字0-9对应的火柴棍数已知。
2. 生成合法数字：用BFS生成所有可能的合法数字（无前导零），并记录每个数字的火柴棍数量。
3. 枚举所有组合：遍历所有A和B的组合，计算C=A+B，检查是否满足等式条件。

1. 
   
2. # 每个数字0-9需要的火柴棍数量
   
3. match_counts = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
   
4. 
   
5. def generate_valid_numbers(max_total):
   
6.     from collections import deque
   
7.     valid = {}
   
8.     # 添加0
   
9.     if match_counts[0] <= max_total:
   
10.         valid[0] = match_counts[0]
    
11.     queue = deque()
    
12.     # 初始化1-9
    
13.     for digit in range(1, 10):
    
14.         cnt = match_counts[digit]
    
15.         if cnt <= max_total:
    
16.             valid[digit] = cnt
    
17.             queue.append((digit, cnt))
    
18.     # BFS生成所有合法数字
    
19.     while queue:
    
20.         num, curr_cnt = queue.popleft()
    
21.         for d in range(10):
    
22.             new_num = num * 10 + d
    
23.             add_cnt = match_counts[d]
    
24.             new_total = curr_cnt + add_cnt
    
25.             if new_total > max_total:
    
26.                 continue
    
27.             if new_num not in valid:
    
28.                 valid[new_num] = new_total
    
29.                 queue.append((new_num, new_total))
    
30.     return valid
    
31. 
    
32. n = int(input())
    
33. if n < 4 + 2*3:  # 最小情况：A=1, B=1, C=2，总火柴2+2+5+4=13
    
34.     print(0)
    
35. else:
    
36.     max_total = n - 4  # 总火柴数（A+B+C）
    
37.     valid = generate_valid_numbers(max_total)
    
38.     count = 0
    
39.     numbers = list(valid.keys())
    
40.     for a in numbers:
    
41.         a_cnt = valid[a]
    
42.         for b in numbers:
    
43.             b_cnt = valid[b]
    
44.             c = a + b
    
45.             if c not in valid:
    
46.                 continue
    
47.             total = a_cnt + b_cnt + valid[c]
    
48.             if total + 4 <= n:
    
49.                 count += 1
    
50.     print(count)
    

复制代码

代码说明
1. generate_valid_numbers函数：用BFS生成所有可能的合法数字，避免前导零。
2. 主逻辑：输入n后，先处理边界情况，再生成合法数字列表，最后枚举所有组合统计符合条件的等式数量。

提示：代码时间复杂度为O(M^2)，M为合法数字数量，适用于n较小的情况。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

FishC

琅琊王朝 发表于 2025-04-22 20:27
player-none 发表于 2025-4-19 17:48
题目描述
给你 ...

1. 
   
2. def count_matches(x):
   
3.     # 每个数字对应的火柴棍数量
   
4.     digit_matches = [6,2,5,5,4,5,6,3,7,6]
   
5.     if x == 0:
   
6.         return digit_matches[0]
   
7.     s = str(x)
   
8.     # 检查前导零
   
9.     if len(s) > 1 and s[0] == '0':
   
10.         return -1
    
11.     total = 0
    
12.     for c in s:
    
13.         total += digit_matches[int(c)]
    
14.     return total
    
15. 
    
16. def count_equations(n):
    
17.     m = n - 4  # A+B+C的火柴总数
    
18.     if m < 0:
    
19.         return 0
    
20.    
    
21.     # 预生成有效数字及其火柴数
    
22.     max_num = 20000  # 经验值，覆盖大部分情况
    
23.     valid_numbers = []
    
24.     count_map = {}
    
25.     for x in range(0, max_num + 1):
    
26.         cnt = count_matches(x)
    
27.         if cnt != -1:
    
28.             valid_numbers.append(x)
    
29.             count_map[x] = cnt
    
30.    
    
31.     res = 0
    
32.     for A in valid_numbers:
    
33.         cnt_a = count_map[A]
    
34.         if cnt_a > m:
    
35.             continue
    
36.         for B in valid_numbers:
    
37.             cnt_b = count_map[B]
    
38.             if cnt_a + cnt_b > m:
    
39.                 continue
    
40.             C = A + B
    
41.             if C not in count_map:
    
42.                 continue
    
43.             cnt_c = count_map[C]
    
44.             if cnt_a + cnt_b + cnt_c == m:
    
45.                 res += 1
    
46.     return res
    
47. 
    
48. # 示例输入输出测试
    
49. n = int(input())
    
50. print(count_equations(n))
    

复制代码

思路解析

1. 火柴数映射：每个数字0-9对应的火柴棍数量预先定义，例如1用2根，7用3根。
2. 前导零处理：若数字非零且以0开头（如01），则视为无效。
3. 预处理有效数字：生成所有可能的有效数字（0到20000），并记录它们的火柴棍数量。
4. 双层循环遍历：遍历所有可能的A和B组合，计算C=A+B，检查：
   - A、B、C是否均为有效数字
   - 火柴棍总数是否等于n-4
5. 时间复杂度优化：通过预计算和范围剪枝（如提前跳过超过火柴总数的组合）提升效率。

关键点
- 加号和等号固定消耗4根火柴，因此A+B+C的总火柴数为n-4。
- 数字非零时不能有前导零，例如01非法，但0合法。
- 暴力枚举时需合理设定数字上限（如20000），避免超时。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。