028赖张禾

用户名：dotcpp0694537

访问量：259

签　名：

想AC的心达到了顶峰

等　　级
排　　名	1958
经　　验	2509
参赛次数	0
文章发表	8
年　　龄	19
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2024年第十五届决赛真题-最小字符串
浏览：33

单调栈(可做模板)
浏览：15

筛素数最全模板
浏览：19

你可能喜欢

dfs(深搜)+剪枝优化

　　作者: 028赖张禾　　　　发表时间：2024-10-01 00:04:54 浏览：16　|　评论：0　

原题链接：分解因数

###看到有多少种方案，基本上不是爆搜就是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分

1 人评分

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

028赖张禾

TA的其他文章

你可能喜欢

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

简单的a+b （C语言代码）

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

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

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

dfs(深搜)+剪枝优化

评论区

精彩推荐

A+B for Input-Output Practice (IV) （C++代码）

不容易系列2 （C语言代码）

成绩转换（C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

1050题解（结构体数组与结构体指针的使用）

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

震宇大神的杀毒软件（C语言代码）

JAM计数法（C语言代码）

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

028赖张禾

TA的其他文章

你可能喜欢

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

简单的a+b （C语言代码）

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

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

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

dfs(深搜)+剪枝优化

评论区

精彩推荐

A+B for Input-Output Practice (IV) （C++代码）

不容易系列2 （C语言代码）

成绩转换 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

1050题解（结构体数组与结构体指针的使用）

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

震宇大神的杀毒软件 （C语言代码）

JAM计数法 （C语言代码）

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

　　评论区

成绩转换（C语言代码）

震宇大神的杀毒软件（C语言代码）

JAM计数法（C语言代码）