day1：学习seach和回溯，初步了解。

day2：深度优化搜索

T1

洛谷P157：https://www.luogu.com.cn/problem/P1157

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

现要求你输出所有组合。

例如n=5,r=3n=5,r=3n=5,r=3，所有组合为：

123,124,125,134,135,145,234,235,245,34512 3 , 1 2 4 , 1 2 5 , 1 3 4 ,1 3 5 , 1 4 5 , 2 3 4 , 2 3 5 , 2 4 5 , 3 4 5123,124,125,134,135,145,234,235,245,345

一行两个自然数n,r(1<n<21,0≤r≤n)n,r(1<n<21,0 \le r \le n)n,r(1<n<21,0≤r≤n)。

所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。

day1用search写的，今天换成dfs

#include
using namespace std;
int a[25];
int N,R;
void dfs(int k){
if(k>R){
for(int i=1;i<=R;i++){ printf("%3d",a[i]); } printf("\n"); return; } for(int i=a[k-1]+1;i<=N;i++){ a[k]=i; dfs(k+1); } } int main(){ cin>>N>>R;
dfs(1);
return 0;
}

dfs给我的第一印象就是和search没有太大区别，我个人觉得dfs比较好写（doge

————————————————————————————————————————

T3

题目描述

在浙江师范大学 ACM 集训队，队员平时集训脑力劳动力比较重。为了劳逸结合，我们敬爱的韩老师准备了一场拔河比赛，让队员放松心情。

为了拔河比赛的公正性，韩老师提出以下要求：
1、 拔河比赛两边人数最多不能相差 1 1 1 。
2、每个队员都有体重，我们要使两边比赛的人体重和相差最小。

现在有 N N N 个队员，韩老师想你帮忙分配，并且把分配后两边体重和之差最小值输出。
输入格式

首先输入 T T T ，表示有 T T T 组样例。

每个样例：

首先输入人数 N N N，占一行。

后面跟着 N N N 个数，表示 N N N个人的体重 W 1 − W n W_1 - W_n W1​−Wn​。
输出格式

对于每个样例输出一行，一个整数表示两边体重之差的绝对值。

解析：

我们只需要构造一组，它的体重越接近全体体重和的一半越好，这组成员的选择，我们可以遍历每个人，要么取要么不取，并且人数为一半，就构成一种方案，在所有方案中找到最小的差值，就是答案。用dfs搜索，需要传递（当前第几个人，已经选取几个人，已经选取体重的总和。）

void dfs(int x,int y,int z){
if(x>n)
return;
if(y==n/2){
res=min(res,abs(z*2-sum)); return;

}  
dfs(x+1,y,z);  
dfs(x+1,y+1,z+a\[x\]);  

}
int main(){
int t;
cin>>t;
while(t--){
cin>>n;
sum+=0;
for(int i=1;i<=n;i++){ cin>>a[i];
sum+=a[i];
}
res=1000000;
dfs(1,0,0);
cout<<res;

}  
return 0;  

}

————————————————————————————————————————