A. 小W选数字

思路

直接套三阶段【算法基础训练】(sanjie)里的J30901. 排列数字代码即可。

代码

#include<bits/stdc++.h>
using namespace std;
int n,vis[60],r;
vector<int> path;
void bfs(int cnt){
	if(cnt==r){
		for(int i=0;i<r;i++) cout<<"  "<<path[i];
		cout<<endl;
		return ;
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]&&cnt==0||path.back()<i){
			vis[i]=1;
			path.push_back(i);
			bfs(cnt+1);
			path.pop_back();
			vis[i]=0;
		}
	}
}
int main(){
	freopen("xsz.in","r",stdin);
	freopen("xsz.out","w",stdout);
	cin>>n>>r;
	bfs(0);
	return 0;
}

这道题目我在写的时候将for(int i=0;i<r;i++) cout<<" "<<path[i];写成了for(int i=0;i<r;i++) cout<<path[i]<<" ";了，下一次一定要再再再再再................再细心一点。

B. 小W玩接龙1

思路

对于这道题目我们可以用一个标记数组来统计是否用了这个数，然后用一个变量来表示上一个合法字符串的字符，再来搜索就可以了。

代码

#include<bits/stdc++.h>
using namespace std;
char a[60],b[60];
bool c[60];
int ans,n;
void dfs(int d,char e){
	ans=max(ans,d);
	for(int i=2;i<=n;i++){
		if(c[i]==0&&e==a[i]){
	 		c[i]=1;
	 		dfs(++d,b[i]);
	 		d--;
	 		c[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]>>b[i];
	dfs(0,b[1]);
	cout<<ans+1;
    return 0;	
}

在考试的时候我以为只能往后接，没有考虑到往前接的情况，导致只得了30分。

C. 小W来分组

思路

如如果一个数c与ab互质，那么这个数一定分别与a和b互质。所以我们可以遍历数组，遇到一对互质的数(都不为零)，就求两个数的乘积存到一个数里，另外一个数字赋值为0，继续递归,最后输出不为0的数的个数即可。

代码

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int a[20],n,cnt;
int gcd(int a,int b){
	if(b==0) return a;
	else 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();
}
signed main(){
	freopen("fz.in","r",stdin);
	freopen("fz.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	dfs();
	for(int i=1;i<=n;i++) if(a[i]) cnt++;
	cout<<cnt;
    return 0;
}

这道题目完全没有思路，所以就放弃了，下一次不能轻易放弃。

D. 小W建围墙

思路

这道题目就是一道标准的洪水填充题。

代码

#include<bits/stdc++.h>
using namespace std;
char a[510][510];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1},n,m,ans;
void dfs(int x,int y){
	if(a[x][y]=='*') return ;
	a[x][y]='*';
	for(int i=0;i<4;i++){
		int rx=x+dx[i],ry=y+dy[i];
		if(rx<1||rx>n||ry<1||ry>m||a[rx][ry]=='*') continue;
		dfs(rx,ry);
	}
}	
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++) cin>>a[i][j];
	} 
	for(int i=1;i<=n;i++){
		if(a[i][1]=='0') dfs(i,1);
		if(a[i][m]=='0') dfs(i,m);
	}
	for(int i=1;i<=m;i++){
		if(a[1][i]=='0') dfs(1,i);
		if(a[n][i]=='0') dfs(n,i);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]=='0') ans++;
		}
	}
	cout<<ans;
    return 0;	
}

想到了是洪水填充，但不知道怎么写。