028赖张禾

###看到有多少种方案，基本上不是爆搜就是DP,很显然这道题爆搜很好解决（~~其实就是不会DP,看不出来，哈哈哈~~）
###### 爆搜都是一颗搜索树，基本搜索过程就是这样：
![](/image_editor_upload/20240930/20240930115627_17896.jpg)
#### 爆搜：只靠爆搜的话本题有一个数据超时
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    int n,res;
    void dfs(int number, int f) {
    	if (f == n) {
    		res++;
    		return;
    	}
    	if (f > n) return;
    	for (int i = number; i <= n / 2; ++i) {
    		f *= i;
    	    dfs(i, f);
    		f /= i;//回溯
    	}
    }
    int main(void) {
    	ios::sync_with_stdio(false);
    	cin.tie(0); cout.tie(0);
    	int t;
    	cin >> t;
    	while (t--) {
            cin >> n;
    		res = 0;
    		dfs(2, 1);
    		cout << res + 1 << endl;
    	}
    	return 0;
    }
####剪枝（对于任意一个数，只有连续该数是因子相乘才能得到此数）：
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    int n,res;
    void dfs(int number, int f) {
    	if (f == n) {
    		res++;
    		return;
    	}
    	if (f > n) return;
    	for (int i = number; i <= n / 2; ++i) {
    		f *= i;
    		if (n % f == 0) {//剪枝过程；
               dfs(i, f);
    		}
    		f /= i;
    	}
    }
    int main(void) {
    	ios::sync_with_stdio(false);
    	cin.tie(0); cout.tie(0);
    	int t;
    	cin >> t;
    	while (t--) {
            cin >> n;
    		res = 0;
    		dfs(2, 1);
    		cout << res + 1 << endl;
    	}
    	return 0;
    }

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

028赖张禾

TA的其他文章

你可能喜欢

【回文数(二)】（C语言代码）

C语言训练-求PI* （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）from DQM

dfs(深搜)+剪枝优化

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题12.1 （C语言代码）

字符串的修改（C语言代码）

1063题初学者，求帮忙看下,不知道哪错了

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

Manchester-汽水瓶问题

【亲和数】（C++代码）

1196题解

平方和与立方和（C语言代码）

028赖张禾

TA的其他文章

你可能喜欢

【回文数(二)】 （C语言代码）

C语言训练-求PI* （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）from DQM

dfs(深搜)+剪枝优化

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题12.1 （C语言代码）

字符串的修改 （C语言代码）

1063题 初学者，求帮忙看下,不知道哪错了

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数 （C语言代码）

Manchester-汽水瓶问题

【亲和数】 （C++代码）

1196题解

平方和与立方和 （C语言代码）

【回文数(二)】（C语言代码）

　　评论区

字符串的修改（C语言代码）

1063题初学者，求帮忙看下,不知道哪错了

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

【亲和数】（C++代码）

平方和与立方和（C语言代码）