2019年蓝桥杯省赛-数的分解

题目

题目链接

题解

DFS。

一定看清要求。

1. 3 个
2. 不同
3. 正整数
4. 正整数中不能包括2和4
5. 满足加法交换律的算式属于一种情况

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 2019; 
int ans = 0;

bool check (int x) {
	while (x) {
		if (x % 10 == 2 || x % 10 == 4) return false;
		x /= 10;
	}
	return true;
}

void dfs (int x, int rest, int num) { // x表示当前的这个数是多少， rest表示还剩多少凑出N 
	if (num == 0) { // 这个放在rest == 0外面剪枝剪的多
		if (rest == 0) ans ++;
		return ;
	}
	
	if (rest < x) return ; // 如果放在num==0前面，会出现当rest=0时，x必然比rest大，所以ans始终为0 
	
	if (check (x)) dfs (x + 1, rest - x, num - 1); // 注意是不同的正整数 // 如果没要求必须不同，则dfs (x, rest-x, num-1) 
	dfs (x + 1, rest, num);
	
} 

int main()
{
	dfs (1, N, 3);
	
	cout << ans << endl;

	return 0;
}