假期集训 1.23

1.组合的输出 深搜dfs

排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r≤n)r，我们可以简单地将n个元素理解为自然数1,2,…,n，从中任取r个数。

现要求你输出所有组合。

 就是一个简单的组合，选够数了就输出

#include
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48 ; ch=getchar();}
	return x*f;
}
int n,r;
int a[100],vis[100];
void pr(){
	for(register int i(1) ; i<=r ; i=-~i) printf("%3d",a[i]);
	printf("n");
}
void dfs(int x,int cnt){
	if(cnt > r){  // 全选完了
		pr();
		return;
	}
	for(register int i(x) ; i<=n ; i=-~i){
		if(!vis[i]){
			a[cnt] = i;
			vis[i] = 1;
			dfs(i+1,cnt+1);  //接着往下搜索
			vis[i] = 0; //注意回溯
		}
	}
}
int main(){
	n=read();r=read();
	dfs(1,1);		
	return 0;
}

2.数的拆分  dfs和回溯

任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。现在给你一个自然数n，要求你求出n的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列，其中字典序小的序列需要优先输出。

如果这个数不比前一个数小，并且加上后不超，就可以加进数组，将数组长度增加，最后正好等于那个数的话就可以输出

#include
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48 ; ch=getchar();}
	return x*f;
}
int n;
int a[100]={1};
void dfs(int st,int sum,int len){ //深搜
	if(sum > n) return;
	if(sum == n){
		for(register int i(1) ; i 
 
3.拔河比赛
 
 
 
为了拔河比赛的公正性，韩老师提出以下要求：
 1.拔河比赛两边人数最多不能相差1。
 
 
2.每个队员都有体重，我们要使两边比赛的人体重和相差最小。
 
 
现在有N个队员，韩老师想你帮忙分配，并且把分配后两边体重和之差最小值输出。
 
 
可以考虑一共选一半的人，选到了就更新一下最小值
 
分成两组，然后考虑当前这个人，可以加进这一组或者不加，分两种情况接着往下搜索
 
#include
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48 ; ch=getchar();}
	return x*f;
}
int n;
int sum,ans=1e9;
int a[110];
void dfs(int x,int cnt,int he){
	if(cnt == n/2){
		ans = min(ans,abs(sum-2*he));
		return;
	}
	if(x > n) return;
	dfs(x+1,cnt+1,he+a[x]);  //这个人放在这组
	dfs(x+1,cnt,he);  //这个人不放在这组
}
int main(){
	int t;
	t=read();
	while(t--){
		sum = 0;ans = 1e9;
		n=read();
		for(register int i(1) ; i<=n ; i=-~i){
			a[i] = read();
			sum += a[i];
		}
		dfs(1,0,0);
		printf("%dn",ans);
	}
	return 0;
}
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5710651.html