吴易繁的博客
Complete Search with Recursion
吴易繁 LV5 化神期 LV 4 @ 2024-10-19 13:59:31

$171$ . 递归实现指数型枚举

这题实际上就是让我们枚举子集，对于每个数都进行选或不选的操作。

若到达边界，就直接输出，然后回溯。

#include<bits/stdc++.h>
using namespace std;
vector<int> a;
int n;
void dfs(int k){
	if(k>n){
		for(int i=0;i<a.size();i++) cout<<a[i]<<" ";
		cout<<endl;
		return ;
	}
	else{
		dfs(k+1);
		a.push_back(k);
		dfs(k+1);
		a.pop_back();
	}
}
int main(){
	cin>>n;
	dfs(1);
	return 0;
}

$173$ . 递归实现排列型枚举

这道题目实际上就是让我们生成全排列，我们可以选在每次搜索时选一次（遍历 $1$ ~ $n$ ），总共选 $n$ 次。

若到达边界，就直接输出，然后回溯。

#include<bits/stdc++.h>
using namespace std;
vector<int> a;
int n;
bool st[20];
void dfs(){
	if(a.size()==n){
		for(int i=0;i<a.size();i++) cout<<a[i]<<" ";
		cout<<endl;
		return ;
	}
	else{
		for(int i=1;i<=n;i++){
			if(st[i]) continue;
			st[i]=1;
			a.push_back(i);
			dfs();
			st[i]=0;
			a.pop_back();
		}
	}
}
int main(){
	cin>>n;
	dfs();
	return 0;
}

$172$ . 递归实现组合型枚举

这道题实际上跟 $173$ . 递归实现排列型枚举这道题差不多，只不过在将总共选 $n$ 次变成了总共选 $m$ 次。

代码也是差不多的，加一个

if(a.size()>m||a.size()+(n-k+1)<m) return;

的剪枝即可。

#include<bits/stdc++.h>
using namespace std;
vector<int> a;
int n,m;
void dfs(int k){
	if(a.size()>m||a.size()+(n-k+1)<m) return;
	if(k==n+1){
		for(int i=0;i<a.size();i++) cout<<a[i]<<" ";
		cout<<endl;
		return ;
	}
	else{
		a.push_back(k);
		dfs(k+1);
		a.pop_back();
		dfs(k+1);
	}
}
int main(){
	cin>>n>>m;
	dfs(1);
	return 0;
}

P $2960$ . Apple Division

这道题我们可以先算出总和，再对每个数都进行选或不选的操作。

若到达边界，就更新值，然后回溯。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,sum,a[30],ans=1e9,sum_2; 
void dfs(int k){
	if(k==n+1){
		ans=min(ans,abs((sum-sum_2)-sum_2));
		return ;
	}
	else{
		dfs(k+1);
		sum_2+=a[k];
		dfs(k+1);
		sum_2-=a[k];
	}
}
signed main(){
	freopen("apple.in","r",stdin);
	freopen("apple.out","w",stdout); 
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum+=a[i];
	}
	dfs(1);
	cout<<ans;
	return 0;
}

$163$ . Creating Strings

这道题实际上跟 $173$ . 递归实现排列型枚举这道题差不多，都是让我们生成全排列。

你可以直接写搜索，但我这里有一个更好的办法。

do
while(next_permutation(s.begin(),s.end()));

这个代码可以生成全排列，所以我们可以直接在这里面做操作。

#include<bits/stdc++.h>
using namespace std;
vector<char> a;
int main(){
	freopen("create.in","r",stdin);
	freopen("create.out","w",stdout); 
	string s;
	cin>>s;
	for(int i=0;i<s.size();i++) a.push_back(s[i]);
	int cnt=0;
	do cnt++;
	while(next_permutation(a.begin(),a.end()));
	cnt=0; 
	do cnt++;
	while(next_permutation(a.begin(),a.end()));
	cout<<cnt<<endl;
	do{ 
		cnt++;
		for(int i=0;i<a.size();i++) cout<<a[i];
		cout<<endl;
	}
	while(next_permutation(a.begin(),a.end()));
	return 0;
}

$165$ . Chessboard and Queens

对于这题我们可以枚举遍历每一个位置，看看能不能放，如果到了最后一行都有位置能放，计数器 $++$ 。

否则，回溯。

最后，输出计数器的值。

#include<bits/stdc++.h>
using namespace std;
char a[10][10];
int mp[25][25],col[25], lf[25], rt[25],cnt;
void dfs(int x){
	if(x==8+1){
		cnt++;
		return ;
	}
	for(int i=1;i<=8;i++){
		if(a[i][x]=='.'&&!col[i]&&!lf[x-i+8]&&!rt[x+i]){
			col[i]=lf[x-i+8]=rt[x+i]=mp[x][i]=1;
			dfs(x+1);
			mp[x][i]=col[i]=lf[x-i+8]=rt[x+i]=0;
		}
	}
}
int main(){
	freopen("queues.in","r",stdin);
	freopen("queues.out","w",stdout);
	for(int i=1;i<=8;i++) for(int j=1;j<=8;j++) cin>>a[i][j];
	dfs(1);
	cout<<cnt;
	return 0;
}

U $23$ B $02$ . Air Cownditioning II

因为M只有 $10$ ，所以暴力枚举不会超时。

我们可以暴力枚举所有空调的开关情况，然后在合法的情况中选择最小花费的情况。

我们可以枚举每个子集的所有位置，记录每个位置的降温情况，再检查是否满足所有牛的要求，如果合法则让 $ans$ 更新。

最后输出 $ans$ 的值即可。

#include<bits/stdc++.h>
using namespace std;
int f[110],a[30],b[30],p[30],m1[30],ans=1e9,wd[110],m;
bool st[20];
void dfs(int cnt){
	if(cnt>m){
		int jq=0;
		for(int i=1;i<=m;i++){
			if(st[i]){
				jq+=m1[i];
				for(int j=a[i];j<=b[i];j++) wd[j]+=p[i];
			}
		}
		bool flag=1;
		for(int i=1;i<=100;i++){
			if(wd[i]<f[i]) flag=0;
			wd[i]=0;
		}
		if(flag) ans=min(ans,jq);
		return ;
	}
	dfs(cnt+1);
	st[cnt]=1;
	dfs(cnt+1);
	st[cnt]=0;
}
int main(){
	freopen("air.in","r",stdin);
	freopen("air.out","w",stdout);
	int n;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int l,t,c;
		cin>>l>>t>>c;
		for(int j=l;j<=t;j++) f[j]=c;
	}
	for(int i=1;i<=m;i++) cin>>a[i]>>b[i]>>p[i]>>m1[i];
	dfs(1);
	cout<<ans;
	return 0;
}

U $18$ B $03$ D. Back and Forth

我们可以分情况讨论：

无效的：
- 拿一个桶去回。
- 拿一个桶去，拿一个桶回。
有效的：
- 拿两个桶去，拿两个桶回。

对于第三种情况我们可以求组合数。

#include<bits/stdc++.h>
using namespace std;
int a[20],b[20];
bool st[2010];
int main(){
	freopen("backforth.in","r",stdin);
	freopen("backforth.out","w",stdout);
	for(int i=1;i<=10;i++) cin>>a[i];
	for(int i=1;i<=10;i++) cin>>b[i];
	st[1000]=1;
	for(int i=1;i<=10;i++) for(int j=1;j<=10;j++) st[1000-a[i]+b[j]]=1;
	for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) for(int k=i+1;k<=10;k++) for(int t=j+1;t<=10;t++) st[1000-a[i]+b[j]-a[k]+b[t]]=1;
	int ans=0;
	for(int i=800;i<=1198;i++) if(st[i]) ans++;
	cout<<ans;
	return 0;
}

U $19$ B $03$ D. Livestock Lineup

对于这道题我们也可以像 $163$ . Creating Strings一样写

do
while(next_permutation(s.begin(),s.end()));

但是！

再 $do$ 里还要判断是否符合条件。

符合条件，输出。

不符合条件，就继续。

#include<bits/stdc++.h>
using namespace std;
vector<string> c,a,b; 
int n;
int find(string s){
	for(int i=0;i<8;i++) if(c[i]==s) return i;
	return -1;
}
bool tj(){
	for(int i=0;i<n;i++) if(abs(find(a[i])-find(b[i]))!=1) return 0;
	return 1;
}
int main(){
	freopen("lineup.in","r",stdin);
	freopen("lineup.out","w",stdout);
	c.push_back("Beatrice");
	c.push_back("Belinda");
	c.push_back("Bella");
	c.push_back("Bessie");
	c.push_back("Betsy");
	c.push_back("Blue");
	c.push_back("Buttercup");
	c.push_back("Sue");
    cin>>n;
    for(int i=1;i<=n;i++){
    	string a1,b1,t1,t2,t3,t4;
    	cin>>a1;
    	cin>>t1;
    	cin>>t2;
    	cin>>t3;
    	cin>>t4;
    	cin>>b1;
    	a.push_back(a1);
    	b.push_back(b1);
	}
	do{
		if(tj()){
			for(int i=0;i<8;i++) cout<<c[i]<<endl;
			break;
		}
	}
	while(next_permutation(c.begin(),c.end()));
	return 0;
}

$169$ . 谷仓的安保

要注意元音与辅音的数量计算。而且如果输出的数量大于 $25000$ ，直接 $exit（0）$ 。

#include <bits/stdc++.h>
using namespace std;
char a[510];
int vis[510];
int l,c,sum;
void dfs(int x,int cnt,int yy,int fy){
	if(x>l){
		if(fy>=2&&yy>=1){
			sum++;
			if(sum>25000) exit(0);
			for(int i=1;i<=c;i++) if(vis[a[i]]) cout<<a[i];
			cout<<endl;
		}
		return ;
	}
	for(int i=cnt+1;i<=c;i++){
		if(!vis[a[i]]){
			vis[a[i]]=1;
			if(a[i]=='a'||a[i]=='e'||a[i]=='i'||a[i]=='o'||a[i]=='u'){
				yy++;
				dfs(x+1,i,yy,fy);
				yy--;
			}
			else{
				fy++;
				dfs(x+1,i,yy,fy);
				fy--;
			}
			vis[a[i]]=0;
		}
	}
}
int main(){
	freopen("ss.in","r",stdin);
	freopen("ss.out","w",stdout);
	cin>>l>>c;
	for(int i=1;i<=c;i++) cin>>a[i];
	sort(a+1,a+c+1);
	dfs(1,0,0,0);
	return 0;
}

$170$ . 数迷

对于这道题目，我们可以从上往下，从左往右来搜索。

每次传入这个数的右边。

如果不是星号，再次搜索。

如果是星号，从1~n遍历每个数字。

如果合法，就赋值，并再次搜索，直到带到边界，计数器++。

注意：因为要注意边界范围所以要加上

if(y==n+1) x++,y=1;

#include<bits/stdc++.h>
using namespace std;
const int N=10;
char a[N][N];
int cnt=0,n;
bool check(int x,int y,char c){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==x&&j==y) continue;
			if(i==x||j==y||i+j==x+y||i-j==x-y){
				if(a[i][j]==c) return 0;
			}
		} 
	} 
	return 1;
}
void dfs(int x,int y){
	if(y==n+1) x++,y=1;
	if(x==n+1){
		cnt++;
	    return ;	
	}
	if(a[x][y]!='*') dfs(x,y+1);
	else{
		for(int i=1;i<=n;i++){
		    if(!check(x,y,i+'0')) continue;
		   	a[x][y]=i+'0';
		    dfs(x,y+1);
		    a[x][y]='*';
	    }
	}
}
int main(){
	freopen("sm.in","r",stdin);
	freopen("sm.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) cin>>a[i][j];
	}
	dfs(1,1);
	cout<<cnt;
    return 0;
}

Complete Search with Recursion

$171$ . 递归实现指数型枚举

$173$ . 递归实现排列型枚举

$172$ . 递归实现组合型枚举

P $2960$ . Apple Division

$163$ . Creating Strings

$165$ . Chessboard and Queens

U $23$ B $02$ . Air Cownditioning II

U $18$ B $03$ D. Back and Forth

U $19$ B $03$ D. Livestock Lineup

$169$ . 谷仓的安保

$170$ . 数迷

状态

开发

支持

关于

Complete Search with Recursion

171171171. 递归实现指数型枚举

173173173. 递归实现排列型枚举

172172172. 递归实现组合型枚举

P296029602960. Apple Division

163163163. Creating Strings

165165165. Chessboard and Queens

U232323B020202. Air Cownditioning II

U181818B030303D. Back and Forth

U191919B030303D. Livestock Lineup

169169169. 谷仓的安保

170170170. 数迷

状态

开发

支持

关于

登录

$171$ . 递归实现指数型枚举

$173$ . 递归实现排列型枚举

$172$ . 递归实现组合型枚举

P $2960$ . Apple Division

$163$ . Creating Strings

$165$ . Chessboard and Queens

U $23$ B $02$ . Air Cownditioning II

U $18$ B $03$ D. Back and Forth

U $19$ B $03$ D. Livestock Lineup

$169$ . 谷仓的安保

$170$ . 数迷