1.24 模拟赛

1.24 模拟赛

1.子集合问题

在给定集合中是否能找到一个子集，等于给定的数

很经典的问题，一道深搜题，考虑该元素，选还是不选，分两种情况接着往下搜索

选得话加上这个数，不选直接跳过这个数

#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;
}
long long n,c;
long long a[1000100];
long long ans[1000100];
long long jia;
void dfs(long long x,long long sum,long long len){
	if(x > n+1) return; //剪枝
	if(sum == c){
		for(register int i(1) ; i c) return; //优化，要不是会超时
	ans[len] = a[x];
	dfs(x+1,sum+a[x],len+1); //这个数选
	dfs(x+1,sum,len); //不选
}
int main(){
	n=read();c=read();
	for(register int i(1) ; i<=n ; i=-~i){
		a[i] = read();
		jia += a[i];
	} //一个剪枝
	if(jia < c){
		printf("No Solution!");
		return 0;
	}
	dfs(1,0,1);	
	printf("No Solution!");
	return 0;
}

2.工作分配问题

n个工作分配给n个人，给定每一个人的所需费用，求最少费用

也是一道深搜题，考虑这一个工作和这一个人，是否这个人做这个工作，做的话加上费用接着搜索，不做的话看下一个工作和下一个人

#include
using namespace std;
int n;
bool vis[1100];
int a[110][110];
int ans = 1e9;
void dfs(int x,int sum){ //第x个人
	if(sum > ans) return;
	if(x == n+1){
		ans = min(ans,sum); //记录答案的最小值
		return;
	}
	for(register int i(1) ; i<=n ; i=-~i){ //第i个工作
		if(!vis[i]){
			vis[i] = 1;
			dfs(x+1,sum+a[x][i]); //这个人做这个工作
			vis[i] = 0;
		}
	}
}
int main(){
	scanf("%d",&n);
	for(register int i(1) ; i<=n ; i=-~i){
		for(register int j(1) ; j<=n ; j=-~j){
			scanf("%d",&a[i][j]);
		}
	}
	dfs(1,0);
	printf("%d",ans);
	return 0;
}

3.装载问题

有一批共n个集装箱，装载量为c的货轮，求最多能装多少货物

首先这可以是一个01背包，但搜索也能过。也是看这个货物装还是不装，两种情况接着往下搜索，如果选的超过了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,c;
int a[1100];
int ans;
void dfs(int x,int sum){
	if(sum == c){
		printf("%d",c);
		exit(0);
	}
	if(sum > c) return;
	if(x > n){
		ans = max(sum,ans);
		return;
	}
	dfs(x+1,sum+a[x]); //选
	dfs(x+1,sum); // 不选
}
int main(){
	n=read();c=read();
	for(register int i(1) ; i<=n ; i=-~i) a[i] = read();
	dfs(1,0);
	printf("%d",ans);
	return 0;
}

4.字符序列

 从三个元素的集合中选取元素生成一个N个字符的序列，使得相邻的两个子序列（长度为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 a[20];
int ans;
void dfs(int x){
	if(x == n+1){
		ans++;
		return;
	}
	for(register int i(1) ; i<=3 ; i=-~i){
		if(i == a[x-2] && a[x-1] == a[x-3]) continue; //如果重复
		a[x] = i;
		dfs(x+1);
	}
}
int main(){
	n=read();
	dfs(1);
	printf("%d",ans);
	return 0;
}