109徐守佳

用户名：dotcpp0787174

访问量：1093

签　名：

想AC的我戴上了WA面具

等　　级
排　　名	884
经　　验	3544
参赛次数	3
文章发表	30
年　　龄	20
在职情况	学生
学　　校	内江师范学院
专　　业	虹夏虹夏虹

　　自我简介：

TA的其他文章

题可以贪心做，人要看准了爱.
浏览：57

[信息学奥赛一本通T1541-数列区间最大值] ST表
浏览：26

[信息学奥赛一本通T1545-Balanced Lineup] RMQ
浏览：22

你可能喜欢

C语言训练-8除不尽的数（C语言代码）暴力解法，答案只有一个，直接输出就好了

[CSP-J2020] 优秀的拆分--DFS+剪枝

　　作者: 109徐守佳　　　　发表时间：2024-09-22 23:39:00 浏览：45　|　评论：1　

原题链接：[CSP-J2020] 优秀的拆分

# 题解没有搜索解法所以写了个

###### 其实根本没必要，老老实实位运算不香嘛
#### tip-1: 1<<n 表示为 2的n次方
#### tip-2:等效冗余,选数的时候选择1 2 3 和 1 3 2 就是等效冗余

```cpp
#include<bits/stdc++.h>
#define ULL unsigned long long
#define LL long long
#define PII pair<int,int>
using namespace std;
const int N =  1e6 + 10,M = 2 * 1e3 + 10,inf = 0x3f3f3f3f;

int n,max_n=-1;
int path[N]; //记录选了哪些数
bool dfs(int sum,int cnt,int u) 
// sum - 当前凑出数的和,
//cnt-记录路径数组下标,
//u-当前处于哪个次幂(用于排除等效冗余,随便避免选同一个次幂);
{
 	if(sum > n) return false; 
	//可行性剪枝:--> 当前凑的数已经大于了n,没必要再继续下去
    if(sum==n) 
//凑出了n,从大到小输出选择的数,因为选数从大的开始选,直接正序输出
    {
        for(int i=0;i<cnt;i++) cout<<path[i]<<' ';
        cout<<endl;
        return true;
    }
    for(int i=u;i>0;i--) //排除等效冗余就从当前次幂开始
    {
        path[cnt] = 1<<i; //记录
        if(dfs(sum+(1<<i),cnt+1,i-1)) return true; 
        //用于dfs的连锁反应,i-1避免选择同一个次幂
    }
    return false;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=0;;i++) 
//计算出最大的小于n的二次幂的次数 比如比6小的最大二次幂是2,因为2^2<6
    {
        if((1<<i) > n) break;
        max_n++; 
    }
//最优性策略剪枝:-->从最大的的次幂开始选,优化搜索顺序,减少递归的分支
    if(!dfs(0,0,max_n)) cout<<"-1"<<endl; //都返回的false输出-1
    return 0;
}
```
# 位运算做法
```cpp
#include<bits/stdc++.h>
#define ULL unsigned long long
#define LL long long
#define PII pair<int,int>
using namespace std;
const int N =  1e6 + 10,M = 2 * 1e3 + 10,inf = 0x3f3f3f3f;

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    if(n&1) puts("-1"); //奇数二进制最后一位必是1,就有2^0,无法拆分
    else
    for(int i=24;i>0;i--) if((n>>i) & 1) cout<<(1<<i)<<' ';
	//(n>>i) & 1 用于判断该数右移i位后二进制最后一位数是否是1;
    return 0;
}
```

0.0分

2 人评分

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

　　评论区

yxy

%%% 纳西妲满昏！  Orz

2024-09-23 11:20:27

109徐守佳

TA的其他文章

你可能喜欢

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

C语言训练-8除不尽的数（C语言代码）暴力解法，答案只有一个，直接输出就好了

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

妹子杀手的故事（C语言代码）

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

[CSP-J2020] 优秀的拆分--DFS+剪枝

评论区

精彩推荐

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

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

C语言训练-亲密数（C语言代码）

C二级辅导-统计字符（C语言代码）

陈教主的三角形（C语言代码）

图形输出（C语言代码）

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

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

1199题解

1415题求解

109徐守佳

TA的其他文章

你可能喜欢

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

C语言训练-8除不尽的数 （C语言代码）暴力解法，答案只有一个，直接输出就好了

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

妹子杀手的故事 （C语言代码）

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

[CSP-J2020] 优秀的拆分--DFS+剪枝

评论区

精彩推荐

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

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

C语言训练-亲密数 （C语言代码）

C二级辅导-统计字符 （C语言代码）

陈教主的三角形 （C语言代码）

图形输出 （C语言代码）

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

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

1199题解

1415题求解

C语言训练-8除不尽的数（C语言代码）暴力解法，答案只有一个，直接输出就好了

妹子杀手的故事（C语言代码）

　　评论区

C语言训练-亲密数（C语言代码）

C二级辅导-统计字符（C语言代码）

陈教主的三角形（C语言代码）

图形输出（C语言代码）