小W选数字（dfs深搜）

思路没想到的原因

没有看清楚题目，要在数字前面加两个空格！！！

思路

全排列模板题，只需把排列换成组合即可。

代码

#include <bits/stdc++.h>
using namespace std;

int a[110];
int dis[110];
int n,r;

void dfs(int x,int cnt){
	if(x>n){
		if(cnt==r){
			for(int i=1;i<r;i++){
				cout <<"  "<<a[i];
			}
			cout <<endl;
		}
		return ;
	}
	a[cnt]=x;
    if(dis[cnt+1]==0){
        dis[cnt+1]=1;
        dfs(x+1,cnt+1);
        dis[cnt+1]=0;
    }
	dfs(x+1,cnt);
}

int main(){
    freopen("xsz.in","r",stdin);
    freopen("xsz.out","w",stdout);
	cin >>n>>r;
	r++; 
	dfs(1,1);
	return 0;
}

小W玩接龙1（dfs深搜）

思路没想到的原因

又没有清楚题目，题目约定第1个单词为龙头。以后看清题！！！

思路

只要满足$dis[i]==0$与$a[i][0]==z$，那么$dis[i]=1$，$dfs(x+1,a[i][1])$完后，$dis[i]=0$。

代码

#include <bits/stdc++.h>
using namespace std;

const int tt=60;
int dis[tt];
char a[tt][tt];
int ans=0;
int n;

void dfs(int x,char z){
    ans=max(ans,x);
	for(int i=1;i<=n;i++){
        if(dis[i]==0&&a[i][0]==z){
            dis[i]=1;
	        dfs(x+1,a[i][1]);
    	    dis[i]=0;
        }
    }
}

int main(){
	freopen("JL.in","r",stdin);
	freopen("JL.out","w",stdout);
    cin >>n;
	for(int i=1;i<=n;i++){
		cin >>a[i][0];
		cin >>a[i][1];
	}
	dis[1]=1;
	dfs(1,a[1][1]);
	cout <<ans;
	return 0;
}

小W来分组（dfs深搜）

思路没想到的原因

没有想到互质定律（具体见思路），要认真来推公式。

思路

如果满足$a[k]$与$a[i]$与$a[j]$的乘积互质，那么$a[k]$会和$a[i]$或$a[j]$互质。

遍历数组，遇到一对互质的数(都不为零)，就求两个数的乘积存到一个数里，另外一个数字赋值为$0$，继续递归。

输出不为$0$的数的个数。

代码

#include <bits/stdc++.h>
using namespace std;

long long a[20];
long long n;

int gcd(int a,int b){
	if(a%b==0){
		return b;
	}else{
		return (gcd(b,a%b));
	}
}int gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}

void dfs(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(gcd(a[i],a[j])==1&&a[i]!=0&&a[j]!=0){
				a[i]*=a[j];
				a[j]=0;
				dfs();
			}
		}
	}
}

int main(){
	freopen("fz.in","r",stdin);
	freopen("fz.out","w",stdout);
	cin >>n;
	for(int i=1;i<=n;i++){
		cin >>a[i];
	}
	dfs();
	int ans=0;
	for(int i=1;i<=n;i++){
		if(a[i]) ans++;
	}
	cout <<ans;
	return 0;
}

小W建围墙（dfs深搜）

思路没想到的原因

用的暴搜，只骗了$20$分。以后要想想优化的方法。

思路

把外围的数字都看做$0$，再判断这个数上下左右是不是都是$*$，是的话$cnt++$。输出$cnt$。

代码

#include <bits/stdc++.h>
using namespace std;

int dis[510][510];
int a[510][510];
int m,n;
int dx[]={0,0,1,-1},dy[]={-1,1,0,0};

void dfs(int x,int y){
	for(int i=0;i<4;i++){
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx>=0&&nx<=n+1&&ny>=0&&ny<=m+1){
			if(a[nx][ny]==0){
				a[nx][ny]=-1;
				dfs(nx,ny);
			}
		}
	}
}

int main(){
	freopen("cd.in","r",stdin);
	freopen("cd.out","w",stdout);
	cin >>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char z;
			cin >>z;
			if(z=='*'){
				a[i][j]=1;
			}else{
				a[i][j]=0;
			}
		}
	}
	dfs(0,0);
	int cnt=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]==0){
				cnt++;
			}
		}
	} 
	cout <<cnt;
	return 0;
}

小W的密码（dfs深搜）

思路没想到的原因

当时没有想到思路。但是想到了想第一题差不多的组合问题。

思路

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

代码

#include <bits/stdc++.h>
using namespace std;

char a[510];
int vis[510];
int l,c;
int y=0,f=0;
int flag=0;

void dfs(int x,int cnt,int y,int f){
	if(x>l){
		if(f>=2&&y>=1){
			flag++;
			if(flag>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'){
				y++;
				dfs(x+1,i,y,f);
				y--;
			}else{
				f++;
				dfs(x+1,i,y,f);
				f--;
			}
			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;
}

小W玩接龙2（dfs深搜）

待更新……

谢谢