博客

Jzoj 函数与递归部分代码（共27题）

  • Post author:
  • Post category:其他



1302: 【入门】挛生素数

#include <bits/stdc++.h>
using namespace std;
int n;
//判断x是否为质数 
bool check(int x)
{
	for(int i=2; i<=sqrt(x); ++i){
		if(x%i==0){
			return false;
		}
	} 
	return true;
}
int main()
{
	scanf("%d", &n);
	for(int i=2; i<=n-2; ++i){
		if(check(i) && check(i+2)){
			printf("%d %d\n", i, i+2);
		}
	}
	return 0;
}


1087: 【入门】哥德巴赫猜想

#include <bits/stdc++.h>
using namespace std;
int n, total, prim[200];
//判断x是否为质数 
bool check(int x)
{
	for(int i=2; i<=sqrt(x); ++i){
		if(x%i==0){
			return false;
		}
	} 
	return true;
}
int main()
{
	scanf("%d", &n);
	for(int i=2; i<=n; ++i){
		if(check(i)){
			total++;
			prim[total]=i;
		}
	}
	for(int i=4; i<=n; i+=2){
		//将i分解为两个质数的和
		for(int j=1; j<=total; ++j){
			for(int k=j; k<=total; ++k){
				if(i==prim[j]+prim[k]){
					printf("%d=%d+%d\n", i, prim[j], prim[k]); 
				}
			}
		} 
	}
	return 0;
}


1100: 【入门】等差素数组

#include <bits/stdc++.h>
using namespace std;
int n, total, mid, prim[100];
bool vis[100];
//判断x是否为质数 
bool check(int x)
{
	for(int i=2; i<=sqrt(x); ++i){
		if(x%i==0){
			return false;
		}
	} 
	return true;
}
int main()
{
	//先求出100以内的质数 
	for(int i=2; i<=100; ++i){
		if(check(i)){
			total++;	//总共有total个质数 
			prim[total]=i;
			vis[i]=true;	//将质数标记为true 
		}
	}
	for(int i=1; i<total; ++i){	//枚举质数 
		for(int j=i+1; j<=total; ++j){	//枚举后面的质数 
			if((prim[i]+prim[j])%2){	//如果两个质数之和不是偶数, 直接跳过 
				continue;
			}
			mid=(prim[i]+prim[j])/2;	//计算平均值 
			if(vis[mid]){	//如果平均值也是质数, 则输出 
				printf("%d %d %d\n", prim[i], mid, prim[j]);
			}
		} 
	}
	return 0;
}


1097: 【入门】素数回文数

#include <bits/stdc++.h>
using namespace std;
//判断x是否为质数 
bool check(int x)
{
	for(int i=2; i<=sqrt(x); ++i){
		if(x%i==0){
			return false;
		}
	} 
	return true;
}
//判断一个数是否是回文数 
bool palindromic(int x)
{
	int length=0, num[4];	//length记得初始化 
	//数位分离, 将每一位保存在数组中 
	while(x){
		length++;
		num[length]=x%10;
		x/=10;
	} 
	for(int i=1; i<=length; ++i){
		if(num[i]!=num[length-i+1]){
			return false;
		}
	}
	return true;
}
int main()
{
	for(int i=10; i<=1000; ++i){
		if(check(i) && palindromic(i)){
			printf("%d\n", i);
		}
	}
	return 0;
}


1076: 【基础】机器人的逻辑

#include <bits/stdc++.h>
using namespace std;
int n, a[51];
bool flag;
int main()
{
	scanf("%d", &n);
	for(int i=1; i<=n; ++i){
		scanf("%d", &a[i]);
	}
	sort(a+1, a+n+1); 
	for(int i=a[1]; i>=1; --i){
		flag=true;
		for(int j=1; j<=n; ++j){
			if(a[j]%i!=0){
				flag=false;
				break;
			}
		}
		if(flag==true){
			printf("%d", i);
			return 0;
		}
	}
	return 0;
}


1140: 【基础】亲密数对

#include <bits/stdc++.h>
using namespace std;
int n;
//计算x的因子之和 
int sum(int x)
{
	int asd=0;
	for(int i=2; i<=sqrt(x); ++i){
		//如果i是x的因子 
		if(x%i==0){
			asd+=i;
			asd+=x/i;	
		}
		if(i*i==x){
			asd-=i;
		}
	} 
	return asd;
}
int main()
{
	scanf("%d", &n);
	for(int i=2; i<=n; ++i){
		int temp=sum(i);
		if(temp!=i && sum(temp)==i && temp<=n){
			printf("%d %d\n", i, temp);
		} 
	}
	return 0;
}


2000: 【基础】因子游戏

#include <bits/stdc++.h>
using namespace std;
int k, a[81];
//计算x的因子之和 
int sum(int x)
{
	int asd=0;
	for(int i=1; i<=sqrt(x); ++i){
		//如果i是x的因子 
		if(x%i==0){
			asd+=2;	
		}
		if(i*i==x){
			asd--;
		}
	} 
	return asd;
}
//输出x的约数 
void print(int x)
{
	printf("%d\n", x);
	for(int i=1; i<=x; ++i){
		//如果i是x的因子 
		if(x%i==0){
			printf("%d ", i);
		}
	} 
}
int main()
{
	scanf("%d", &k);
	for(int i=1; i<=20000; ++i){
		if(sum(i)==k){ 
			print(i);
			return 0; 
		} 
	}
	printf("NO SOLUTION");
	return 0;
}


1153: 【基础】经典递归问题——汉诺塔

#include <bits/stdc++.h>
using namespace std;
int n, cnt;
void asd(int n, char a, char b, char c)
{
	if(n==1){
		printf("%c To %c\n", a, c);
		cnt++;
	}
	else{
		asd(n-1, a, c, b);
		printf("%c To %c\n", a, c);
		cnt++;
		asd(n-1, b, a, c);
	}
}
int main()
{
	scanf("%d", &n);
	asd(n, 'A', 'B', 'C');
//	printf("最少步数为：%d", cnt);
	return 0;
}


2801: 【基础】聪明的海宝

#include <bits/stdc++.h>
using namespace std;
int n;
//计算第w个沙坑中的金币数 
int ans(int w)
{
	if(w==1){
		return 1;
	}
	//偶数 
	if(w%2==0){
		return ans(w/2)+w; 
	}
	else{	//奇数 
		return ans(3*w+1)+w; 
	}
}
int main()
{
	scanf("%d", &n);
	printf("%d", ans(n));
	return 0;
}


1844: 【USACO】Symmetry（对称）

#include <bits/stdc++.h>
using namespace std;
int n, m;
int solve(int x, int y)
{
	//有一个是偶数, 就没有中心格子了 
	if(x%2==0 || y%2==0){
		return 0; 
	}
	else{	//找到一个中心格子, 并继续划分 
		return 1+4*solve(x/2, y/2); 
	}
}
int main()
{
	scanf("%d %d", &n, &m);
	printf("%d", solve(n, m));
	return 0;
}


1571: 【NOIP98普及组】2的幂次方

方法一：递归

#include <bits/stdc++.h>
using namespace std;
int n;
void solve(int x)
{
	int flag=-1;
	int cnt=0, a[20];
	memset(a, 0, sizeof(a));
	//先对x进行二进制拆分
	//将十进制x转换为二进制
	while(x){
		a[cnt]=x%2; 	//从a[0]开始保存最低位 
		if(x%2!=0 && flag==-1){
			flag=cnt;	//flag表示二进制数非0的最低位
		}
		x>>=1;	//幂运算, 相当于x/=2; 
		cnt++;
	} 
	//从最高位开始, 对非0项进行递归输出 
	for(int i=cnt-1; i>=0; --i){
		if(a[i]==0){
			continue;
		} 
		else{
			if(i==0){	//已经到最低位了, 2的0次直接输出, 递归出口 
				printf("2(0)");
				return;
			}
			else if(i==1){	//2的1次, 题目要求直接输出2 
				printf("2");	//注意, 此时不能直接return, 有可能还有2的0次 
				if(i>flag){		//判断, 如果此时不是最低位, 则需要输出+ 
					printf("+");
				}
			}
			else{	//一路递归下去 
				printf("2(");  
				solve(i);	//递归函数要放在中间 
				printf(")");
				if(i>flag){		//判断, 如果此时不是最低位, 则需要输出+ 
					printf("+");
				}	
			} 
		}
	}
}
int main()
{
	scanf("%d", &n);
	solve(n);	
	return 0;
}

方法二：打表

#include <iostream>
using namespace std;
int n, a[100], length, cnt;
//打表 
string s[17]={"0", "", "2", "2+2(0)", "2(2)", "2(2)+2(0)", "2(2)+2", "2(2)+2+2(0)", "2(2+2(0))", "2(2+2(0))+2(0)", "2(2+2(0))+2",
			  "2(2+2(0))+2+2(0)", "2(2+2(0))+2(2)", "2(2+2(0))+2(2)+2(0)", "2(2+2(0))+2(2)+2", "2(2+2(0))+2(2)+2+2(0)", "2(2(2))"};
int main()
{
	cin >> n;
	//将十进制数n转换为二进制数，存在a数组中，a[0]存低位
	//length记录二进制有几位 
	while(n){
		a[length]=n%2;
		n/=2;
		length++;
	}
	//计算转换后的二进制中有多少个1，也就是最后的式子中有cnt-1个加号 
	for(int i=0; i<length; ++i){
		if(a[i]!=0){
			cnt++; 
		}
	}
	cnt--;
	//将二进制中位数为1的位输出 
	for(int i=length-1; i>=0; --i){
		//位数为1，并且不是2^1那一位 
		if(a[i]!=0 && i!=1){
			cout << "2(" << s[i] << ")";
			if(cnt!=0){	//如果这个式子后面还有式子,则输出一个加号 
				cout << "+";
				cnt--;
			}
		}
		else if(a[i]!=0 && i==1){ //位数为1，并且是2^1那一位 
			cout << "2";
			if(cnt!=0){	//如果这个式子后面还有式子,则输出一个加号
				cout << "+";
				cnt--;
			}
		}
	}

	return 0;
}


2342: 【提高】递归

#include <bits/stdc++.h>
using namespace std;
long long a, b, c, ans[21][21][21];
long long w(long long x, long long y, long long z)
{
	if(x<=20 && y<=20 && z<=20 && x>=0 && y>=0 && z>=0 && ans[x][y][z]){
		return ans[x][y][z];
	}
	if(x<=0 || y<=0 || z<=0){
		return 1;
	}
	else if(x>20 || y>20 || z>20){
		return w(20, 20, 20);
	}
	else if(x<y && y<z){
		return ans[x][y][z]=w(x,y,z-1)+w(x,y-1,z-1)-w(x,y-1,z);
	}
	else{
		return ans[x][y][z]=w(x-1,y,z)+w(x-1,y-1,z)+w(x-1,y,z-1)-w(x-1,y-1,z-1);
	}
}
int main()
{
	while(1){
		scanf("%lld %lld %lld", &a, &b, &c);
		if(a==-1 && b==-1 && c==-1){
			return 0;
		}
		memset(ans, 0, sizeof(ans));
		printf("w(%lld, %lld, %lld) = %lld\n", a, b, c, w(a, b, c));
	}
	return 0;
}


1091: 【提高】那些n位数

方法一：循环

//循环方法 
#include <bits/stdc++.h>
using namespace std;
int n, p;
int main()
{
	scanf("%d %d", &n, &p);
	if(n==1){
		for(int i=1; i<=p; ++i){
			printf("%d\n", i);
		}
	}
	else if(n==2){
		for(int i=1; i<=p; ++i){
			for(int j=1; j<=p; ++j){
				printf("%d%d\n", i, j);
			}
		}
	}
	else if(n==3){
		for(int i=1; i<=p; ++i){
			for(int j=1; j<=p; ++j){
				for(int k=1; k<=p; ++k){
					printf("%d%d%d\n", i, j, k);
				}
			}
		}
	}
	else if(n==4){
		for(int i=1; i<=p; ++i){
			for(int j=1; j<=p; ++j){
				for(int k=1; k<=p; ++k){
					for(int l=1; l<=p; ++l){
						printf("%d%d%d%d\n", i, j, k, l);
					}
				}
			}
		}	
	}
	else if(n==5){
		for(int i=1; i<=p; ++i){
			for(int j=1; j<=p; ++j){
				for(int k=1; k<=p; ++k){
					for(int l=1; l<=p; ++l){
						for(int m=1; m<=p; ++m){
							printf("%d%d%d%d%d\n", i, j, k, l, m);
						}
					}
				}
			}
		}
	}
	else if(n==6){
		for(int i=1; i<=p; ++i){
			for(int j=1; j<=p; ++j){
				for(int k=1; k<=p; ++k){
					for(int l=1; l<=p; ++l){
						for(int m=1; m<=p; ++m){
							for(int o=1; o<=p; ++o){
								printf("%d%d%d%d%d%d\n", i, j, k, l, m, o);
							}	
						}
					}
				}
			}
		}
	}
	else if(n==7){
		for(int i=1; i<=p; ++i){
			for(int j=1; j<=p; ++j){
				for(int k=1; k<=p; ++k){
					for(int l=1; l<=p; ++l){
						for(int m=1; m<=p; ++m){
							for(int o=1; o<=p; ++o){
								for(int q=1; q<=p; ++q){
									printf("%d%d%d%d%d%d%d\n", i, j, k, l, m, o, q);
								}
							}	
						}
					}
				}
			}
		}
	}
	else if(n==8){
		for(int i=1; i<=p; ++i){
			for(int j=1; j<=p; ++j){
				for(int k=1; k<=p; ++k){
					for(int l=1; l<=p; ++l){
						for(int m=1; m<=p; ++m){
							for(int o=1; o<=p; ++o){
								for(int q=1; q<=p; ++q){
									for(int r=1; r<=p; ++r){
										printf("%d%d%d%d%d%d%d%d\n", i, j, k, l, m, o, q, r);
									}
								}
							}	
						}
					}
				}
			}
		}
	}
	return 0;
}

方法二：递归

#include <bits/stdc++.h>
using namespace std;
int n, p, a[10];
void solve(int cnt)
{
	if(cnt==n+1){
		for(int i=1; i<=n; ++i){
			printf("%d", a[i]);
		}
		printf("\n");
		return;
	}
	for(int i=1; i<=p; ++i){
		a[cnt]=i;
		solve(cnt+1);
	}
}
int main()
{
	scanf("%d %d", &n, &p);
	solve(1);
	return 0;
}


2023: 【提高】那些n位数II

#include <bits/stdc++.h>
using namespace std;
int n, p, a[10];
bool vis[10];
void solve(int cnt)
{
	if(cnt==n+1){
		for(int i=1; i<=n; ++i){
			printf("%d", a[i]);
		}
		printf("\n");
		return;
	}
	for(int i=1; i<=p; ++i){
		if(vis[i]==false){
			a[cnt]=i;	
			vis[i]=true;
			solve(cnt+1);
			vis[i]=false;
		}
	}
}
int main()
{
	scanf("%d %d", &n, &p);
	solve(1);
	return 0;
}


2025: 【提高】生成组合

方法一：循环

//循环方法 
#include <bits/stdc++.h>
using namespace std;
int n, p;
int main()
{
	scanf("%d %d", &p, &n);
	if(n==1){
		for(int i=1; i<=p; ++i){
			printf("%d\n", i);
		}
	}
	else if(n==2){
		for(int i=1; i<=p; ++i){
			for(int j=i+1; j<=p; ++j){
				printf("%d%d\n", i, j);
			}
		}
	}
	else if(n==3){
		for(int i=1; i<=p; ++i){
			for(int j=i+1; j<=p; ++j){
				for(int k=j+1; k<=p; ++k){
					printf("%d%d%d\n", i, j, k);
				}
			}
		}
	}
	else if(n==4){
		for(int i=1; i<=p; ++i){
			for(int j=i+1; j<=p; ++j){
				for(int k=j+1; k<=p; ++k){
					for(int l=k+1; l<=p; ++l){
						printf("%d%d%d%d\n", i, j, k, l);
					}
				}
			}
		}	
	}
	else if(n==5){
		for(int i=1; i<=p; ++i){
			for(int j=i+1; j<=p; ++j){
				for(int k=j+1; k<=p; ++k){
					for(int l=k+1; l<=p; ++l){
						for(int m=l+1; m<=p; ++m){
							printf("%d%d%d%d%d\n", i, j, k, l, m);
						}
					}
				}
			}
		}
	}
	else if(n==6){
		for(int i=1; i<=p; ++i){
			for(int j=i+1; j<=p; ++j){
				for(int k=j+1; k<=p; ++k){
					for(int l=k+1; l<=p; ++l){
						for(int m=l+1; m<=p; ++m){
							for(int o=m+1; o<=p; ++o){
								printf("%d%d%d%d%d%d\n", i, j, k, l, m, o);
							}	
						}
					}
				}
			}
		}
	}
	else if(n==7){
		for(int i=1; i<=p; ++i){
			for(int j=i+1; j<=p; ++j){
				for(int k=j+1; k<=p; ++k){
					for(int l=k+1; l<=p; ++l){
						for(int m=l+1; m<=p; ++m){
							for(int o=m+1; o<=p; ++o){
								for(int q=o+1; q<=p; ++q){
									printf("%d%d%d%d%d%d%d\n", i, j, k, l, m, o, q);
								}
							}	
						}
					}
				}
			}
		}
	}
	else if(n==8){
		for(int i=1; i<=p; ++i){
			for(int j=i+1; j<=p; ++j){
				for(int k=j+1; k<=p; ++k){
					for(int l=k+1; l<=p; ++l){
						for(int m=l+1; m<=p; ++m){
							for(int o=m+1; o<=p; ++o){
								for(int q=o+1; q<=p; ++q){
									for(int r=q+1; r<=p; ++r){
										printf("%d%d%d%d%d%d%d%d\n", i, j, k, l, m, o, q, r);
									}
								}
							}	
						}
					}
				}
			}
		}
	}
	else if(n==9){
		for(int i=1; i<=p; ++i){
			for(int j=i+1; j<=p; ++j){
				for(int k=j+1; k<=p; ++k){
					for(int l=k+1; l<=p; ++l){
						for(int m=l+1; m<=p; ++m){
							for(int o=m+1; o<=p; ++o){
								for(int q=o+1; q<=p; ++q){
									for(int r=q+1; r<=p; ++r){
										for(int s=r+1; s<=p; ++s){
											printf("%d%d%d%d%d%d%d%d%d\n", i, j, k, l, m, o, q, r, s);
										}
									}
								}
							}	
						}
					}
				}
			}
		}
	}
	return 0;
}

方法二：递归

#include <iostream>
using namespace std;
int n, r;
int a[21];
void dfs(int cnt)
{
	if(cnt==r+1){
		for(int i=1; i<=r; i++)
			printf("%d", a[i]);
		printf("\n");
		return;
	}
	for(int i=a[cnt-1]+1; i<=n-r+cnt; i++){		//n-r+cnt写成n也可以 
		a[cnt]=i;	 
		dfs(cnt+1);
	}
}
int main()
{
	cin >> n >> r;
	dfs(1);
	return 0;
}


1648: 【提高】素数个数

#include <bits/stdc++.h>
using namespace std;
int n, r;
int num[21], a[21], sum, ans;
bool check(int x)
{
	if(x<2){
		return false;
	}
	for(int i=2; i<=sqrt(x); ++i){
		if(x%i==0){
			return false;
		}
	}
	return true;
}
void dfs(int cnt)
{
	if(cnt==r+1){
		sum=0;
		for(int i=1; i<=r; i++)
			sum+=num[a[i]];
		if(check(sum)){
			ans++;
		}
		return;
	}
	for(int i=a[cnt-1]+1; i<=n-r+cnt; i++){		//n-r+cnt写成n也可以 
		a[cnt]=i;	 
		dfs(cnt+1);
	}
}
int main()
{
	scanf("%d %d", &n, &r);
	for(int i=1; i<=n; ++i){
		scanf("%d", &num[i]);
	}
	dfs(1);
	printf("%d", ans);
	return 0;
}


2026: 【提高】自然数拆分

#include <bits/stdc++.h>
using namespace std;
int n, a[15], num;
struct node
{
	int asd[15];
	int tot;
	long long id;	
}ans[100];
bool cmp(node x, node y)
{
	return x.id>y.id; 
}
//将x分为total个整数, 当前准备分第cnt个整数 
void dfs(int x, int cnt, int total)
{
	//将x分为total个数, 现在准备安排第cnt个, 如果第cnt个等于total 
	if(cnt==total){	//如果要将x分为一个数, 直接赋值为x 
		if(x<a[cnt-1])	return;		//避免重复 
		a[cnt]=x;
		num++;
		ans[num].tot=total;
		for(int i=total; i>=1; --i){
			ans[num].asd[i]=a[i];
			ans[num].id+=a[i]*pow(10,n+i-total);
		}
	}
	else{
		//还没分完, 如果分的是第一个, 则从1开始枚举, 此时的a[cnt-1]为0
		//如果分的不是第一个, 则从前一个值开始枚举 
		for(int i=max(1, a[cnt-1]); i<=x; ++i){
			a[cnt]=i;
			dfs(x-i, cnt+1, total);
		}
	}
	
} 
int main()
{
	scanf("%d", &n);
	for(int i=1; i<=n; ++i){
		//将n分为i个整数之和, 当前准备分安排第一个 
		dfs(n, 1, i);	
	}
	sort(ans+1, ans+num+1, cmp);
	for(int i=1; i<=num; ++i){
		for(int j=ans[i].tot; j>=1; --j){
			printf("%3d", ans[i].asd[j]);
		} 
		printf("\n");
	}
	return 0;
}


2027: 【提高】自然数拆分II

#include <bits/stdc++.h>
using namespace std;
int n, a[15], num;
struct node
{
	int asd[15];
	int tot;
	long long id;	
}ans[100];
bool cmp(node x, node y)
{
	return x.id<y.id; 
}
//将x分为total个整数, 当前准备分第cnt个整数 
void dfs(int x, int cnt, int total)
{
	//将x分为total个数, 现在准备安排第cnt个, 如果第cnt个等于total 
	if(cnt==total){	//如果要将x分为一个数, 直接赋值为x 
		if(x<a[cnt-1])	return;		//避免重复 
		a[cnt]=x;
		num++;
		ans[num].tot=total;
		for(int i=1; i<=total; ++i){
			ans[num].asd[i]=a[i];
			ans[num].id+=a[i]*pow(10,n-i);
		}
	}
	else{
		//还没分完, 如果分的是第一个, 则从1开始枚举, 此时的a[cnt-1]为0
		//如果分的不是第一个, 则从前一个值开始枚举 
		for(int i=max(1, a[cnt-1]); i<=x; ++i){
			a[cnt]=i;
			dfs(x-i, cnt+1, total);
		}
	}
	
} 
int main()
{
	scanf("%d", &n);
	for(int i=2; i<=n; ++i){
		//将n分为i个整数之和, 当前准备分安排第一个 
		dfs(n, 1, i);	
	}
	sort(ans+1, ans+num+1, cmp);
	for(int i=1; i<=num; ++i){
		for(int j=1; j<=ans[i].tot; ++j){
			printf("%3d", ans[i].asd[j]);
		} 
		printf("\n");
	}
	return 0;
}


1494: 【USACO】”跳房子”

#include <bits/stdc++.h>
using namespace std;
int a[10][10], ans;
bool vis[1000000];
//跳到了x行y列, 当前是第cnt个数, 此前的和为cur 
void dfs(int x, int y, int cnt, int cur)
{
	//跳到界外 
	if(x<1 || y<1 || x>5 || y>5){
		return;
	}
	if(cnt==6){	//已经是第6个数了 
		//累加
		cur=cur*10+a[x][y];
		if(vis[cur]==false){
			ans++;
			vis[cur]=true;
		}
		return;
	} 
	else{	//还没跳够6个数 
		cur=cur*10+a[x][y]; 
		dfs(x-1, y, cnt+1, cur);
		dfs(x+1, y, cnt+1, cur);
		dfs(x, y-1, cnt+1, cur);
		dfs(x, y+1, cnt+1, cur);
	}
}
int main()
{
	for(int i=1; i<=5; ++i){
		for(int j=1; j<=5; ++j){
			scanf("%d", &a[i][j]);
		} 
	}
	for(int i=1; i<=5; ++i){
		for(int j=1; j<=5; ++j){
			dfs(i, j, 1, 0);
		} 
	}
	printf("%d", ans); 
	return 0;
}


1666: 【基础】发书

#include <bits/stdc++.h>
using namespace std;
int k, n, m, from, to;
//n<250，m<10000
//这道题数据范围有问题, 数组开到250会出错, 改为251就过了 
bool vis[251], flag;
bool know[251][251];
void dfs(int id)
{
	for(int i=1; i<=n; ++i){
		//如果id认识i, 并且还没给i发书 
		if(know[id][i] && !vis[i]){
			vis[i]=true;
			//让i去发书 
			dfs(i);
		}
	}
}
int main()
{
	//k代表star的学号，n代表人数，m代表关系数
	scanf("%d %d %d", &k, &n, &m);
	while(m--){
		scanf("%d %d", &from, &to);
		know[from][to]=true;
	}
	vis[k]=true;
	dfs(k);
	for(int i=1; i<=n; ++i){
		if(!vis[i]){
			printf("%d ", i);
			flag=true;
		}
	} 
	if(flag==false){
		printf("0");
	}
	return 0;
}


1168: 【提高】老鼠闯迷宫

#include <bits/stdc++.h>
using namespace std;
int m, n;
int a[20][20];	//1表示有障碍物 
int ans[200][3];	//ans[i][1]表示第i步的行, ans[i][2]表示第i步的列 
bool vis[20][20];	//标记是否走过 
int mx[9]={0, 1, 0, -1, -1, -1, 0, 1, 1};
int my[9]={0, 1, 1, 1, 0, -1, -1, -1, 0}; 
void dfs(int x, int y, int cnt)
{
	//出界 或者 有障碍物 
	if(x<1 || y<1 || x>m || y>n || a[x][y]==1){
		return;
	}
	//到达终点 
	if(x==m && y==n){
		//输出路径 
		ans[cnt][1]=x;
		ans[cnt][2]=y;
		for(int i=1; i<=cnt; ++i){
			printf("(%d,%d)", ans[i][1], ans[i][2]);
			if(i!=cnt){
				printf("-");
			}
		}
		exit(0);	//结束程序 
	}
	//还没到达终点
	ans[cnt][1]=x;
	ans[cnt][2]=y;
	//标记 
	vis[x][y]=true;
	for(int i=1; i<=8; ++i){
		int xx=x+mx[i];
		int yy=y+my[i];
		if(!vis[xx][yy]){
			dfs(xx, yy, cnt+1);
		}
	} 
	//回溯 
	vis[x][y]=false;
}
int main()
{
	//m行n列 
	scanf("%d %d", &m, &n);
	for(int i=1; i<=m; ++i){	//行 
		for(int j=1; j<=n; ++j){	//列 
			scanf("%d", &a[i][j]);	//1表示有障碍物 
		}
	}
	vis[1][1]=true;
	//从第一行第一列出发, 走了一个格子 
	dfs(1, 1, 1); 
	return 0;	
}


1167: 【提高】跳马

//这道题关于输出的描述有问题, 题目描述输出一条路径,
//实际需要输出所有的路径, 每行一条 
#include <bits/stdc++.h>
using namespace std;
int m, n;
int a[20][20];	//1表示有障碍物 
int ans[200][3];	//ans[i][1]表示第i步的行, ans[i][2]表示第i步的列 
bool vis[20][20];	//标记是否走过 
int mx[9]={0, 2, 1, -1, -2, -2, -1, 1, 2};
int my[9]={0, 1, 2, 2, 1, -1, -2, -2, -1}; 
void dfs(int x, int y, int cnt)
{
	//出界 或者 有障碍物 
	if(x<1 || y<1 || x>m || y>n || a[x][y]==1){
		return;
	}
	//到达终点 
	if(x==m && y==n){
		//输出路径 
		ans[cnt][1]=x;
		ans[cnt][2]=y;
		for(int i=1; i<=cnt; ++i){
			printf("(%d,%d)", ans[i][1], ans[i][2]);
			if(i!=cnt){
				printf("-");
			}
		}
		printf("\n");
//		exit(0);	//结束程序 
		return; 
	}
	//还没到达终点
	ans[cnt][1]=x;
	ans[cnt][2]=y;
	//标记 
	vis[x][y]=true;
	for(int i=1; i<=8; ++i){
		int xx=x+mx[i];
		int yy=y+my[i];
		if(!vis[xx][yy]){
			dfs(xx, yy, cnt+1);
		}
	} 
	//回溯 
	vis[x][y]=false;
}
int main()
{
	//m行n列 
	scanf("%d %d", &m, &n);
	for(int i=1; i<=m; ++i){	//行 
		for(int j=1; j<=n; ++j){	//列 
			scanf("%d", &a[i][j]);	//1表示有障碍物 
		}
	}
	vis[1][1]=true;
	//从第一行第一列出发, 走了一个格子 
	dfs(1, 1, 1); 
	return 0;	
}


1846: 【USACO】Space Exploration

#include <bits/stdc++.h>
using namespace std;
int n;
char a[1002][1002];
bool vis[1002][1002];
int ans;
void dfs(int x, int y)
{
	if(a[x+1][y]=='*' && !vis[x+1][y]){
		vis[x+1][y]=true;
		dfs(x+1, y);
	}
	if(a[x-1][y]=='*' && !vis[x-1][y]){
		vis[x-1][y]=true;
		dfs(x-1, y);
	}
	if(a[x][y+1]=='*' && !vis[x][y+1]){
		vis[x][y+1]=true;
		dfs(x, y+1);
	}
	if(a[x][y-1]=='*' && !vis[x][y-1]){
		vis[x][y-1]=true;
		dfs(x, y-1);
	}
}
int main()
{
	scanf("%d", &n);
	for(int i=1; i<=n; ++i){
		for(int j=1; j<=n; ++j){
			cin >> a[i][j];
		}
	}
	for(int i=1; i<=n; ++i){
		for(int j=1; j<=n; ++j){
			//i行j列为岛屿, 并且没被其他岛屿包含进去 
			if(a[i][j]=='*' && !vis[i][j]){
				ans++;
				dfs(i, j);
			} 
		}
	}
	printf("%d", ans);
	return 0;	
}


1495: 【USACO】卫星照片

#include <bits/stdc++.h>
using namespace std;
int w, h;
char a[1002][82];
bool vis[1002][82];
int cur, ans;
void dfs(int x, int y)
{
	if(a[x+1][y]=='*' && !vis[x+1][y]){
		vis[x+1][y]=true;
		cur++;
		dfs(x+1, y);
	}
	if(a[x-1][y]=='*' && !vis[x-1][y]){
		vis[x-1][y]=true;
		cur++;
		dfs(x-1, y);
	}
	if(a[x][y+1]=='*' && !vis[x][y+1]){
		vis[x][y+1]=true;
		cur++;
		dfs(x, y+1);
	}
	if(a[x][y-1]=='*' && !vis[x][y-1]){
		vis[x][y-1]=true;
		cur++;
		dfs(x, y-1);
	}
}
int main()
{
	scanf("%d %d", &w, &h);
	for(int i=1; i<=h; ++i){
		for(int j=1; j<=w; ++j){
			cin >> a[i][j];	//字符数组输入用cin 
		}
	}
	for(int i=1; i<=h; ++i){
		for(int j=1; j<=w; ++j){
			//i行j列为牧场, 并且没被其他牧场包含进去 
			if(a[i][j]=='*' && !vis[i][j]){
				vis[i][j]=true;
				//每次找牧场时初始化当前这片牧场的面积 
				cur=1;
				dfs(i, j);
				//找完与i行j列连续的牧场, 更新答案 
				ans=max(ans, cur);
			} 
		}
	}
	printf("%d", ans);
	return 0;	
}


2028: 【提高】8皇后问题


方法一
 

#include <bits/stdc++.h>
using namespace std;
//a[i]存的是第i行的棋子放的列，我们的目标就是把1-n分配给a[1]-a[n]，并且不能冲突 
//vis[i][j]=1表示第i行第j列放了棋子，为0表示没放棋子
//vis1[i]=1表示第i列有棋子了，为0表示第i列没有棋子 
int n, a[14], vis[14][14], vis1[14];
//在x行y列放会不会产生冲突 
bool ok(int x, int y)
{
	//定义临时遍历，不然x,y的值在一次while判断后就改变了，导致后面的判断失效 
	int tempx, tempy;	
	//判断同一行、同一列有没有冲突 
	//其实没有必要判断行(因为每行只安排一个数)，没有必要判断列(vis1[i]表示第i列有没有数字) 
	/*
	for(int i=1; i<=n; ++i){
		if(vis[x][i]==1 || vis[i][y]==1){
			return false;
		}
	}
	*/
	tempx=x;
	tempy=y;
	//判断左下角有没有冲突 
	while(tempx!=n && tempy!=1){
		tempx++;
		tempy--;
		if(vis[tempx][tempy]==1){
			return false;
		}
	}
	tempx=x;
	tempy=y;
	//判断右上角有没有冲突 
	while(tempx!=1 && tempy!=n){
		tempx--;
		tempy++;
		if(vis[tempx][tempy]==1){
			return false;
		}
	} 
	tempx=x;
	tempy=y;
	//判断左上角有没有冲突 
	while(tempx!=1 && tempy!=1){
		tempx--;
		tempy--;
		if(vis[tempx][tempy]==1){
			return false;
		}
	}
	tempx=x;
	tempy=y;
	//判断右下角有没有冲突 
	while(tempx!=n && tempy!=n){
		tempx++;
		tempy++;
		if(vis[tempx][tempy]==1){
			return false;
		}
	}  
	return true;
}
void dfs(int cnt)
{
	if(cnt==n+1){
		for(int i=1; i<=n; ++i){
			cout << a[i] << " ";
		}
		cout << endl;	
	}
	//看第cnt行要放在第几列，i遍历列 
	for(int i=1; i<=n; ++i){
		//如果第cnt行第i列没有放棋子，并且第i列没有放棋子
		//并且在cnt行i列放棋子不会产生冲突，才可以放 
		if(vis[cnt][i]==0 && vis1[i]==0 && ok(cnt, i)){	
			vis[cnt][i]=1;
			vis1[i]=1;
			a[cnt]=i;	
			dfs(cnt+1);
			vis[cnt][i]=0;	
			vis1[i]=0;			
		}
	}
}
int main()
{
	n=8;
	dfs(1);
	return 0;
}


方法二


1154: 【基础】N皇后问题

#include <bits/stdc++.h>
using namespace std;
//a[i]存的是第i行的棋子放的列，我们的目标就是把1-n分配给a[1]-a[n]，并且不能冲突 
//vis[i][j]=1表示第i行第j列放了棋子，为0表示没放棋子
//vis1[i]=1表示第i列有棋子了，为0表示第i列没有棋子 
int n, a[14], vis[14][14], vis1[14];
//在x行y列放会不会产生冲突 
bool ok(int x, int y)
{
	//定义临时遍历，不然x,y的值在一次while判断后就改变了，导致后面的判断失效 
	int tempx, tempy;	
	//判断同一行、同一列有没有冲突 
	//其实没有必要判断行(因为每行只安排一个数)，没有必要判断列(vis1[i]表示第i列有没有数字) 
	/*
	for(int i=1; i<=n; ++i){
		if(vis[x][i]==1 || vis[i][y]==1){
			return false;
		}
	}
	*/
	tempx=x;
	tempy=y;
	//判断左下角有没有冲突 
	while(tempx!=n && tempy!=1){
		tempx++;
		tempy--;
		if(vis[tempx][tempy]==1){
			return false;
		}
	}
	tempx=x;
	tempy=y;
	//判断右上角有没有冲突 
	while(tempx!=1 && tempy!=n){
		tempx--;
		tempy++;
		if(vis[tempx][tempy]==1){
			return false;
		}
	} 
	tempx=x;
	tempy=y;
	//判断左上角有没有冲突 
	while(tempx!=1 && tempy!=1){
		tempx--;
		tempy--;
		if(vis[tempx][tempy]==1){
			return false;
		}
	}
	tempx=x;
	tempy=y;
	//判断右下角有没有冲突 
	while(tempx!=n && tempy!=n){
		tempx++;
		tempy++;
		if(vis[tempx][tempy]==1){
			return false;
		}
	}  
	return true;
}
void dfs(int cnt)
{
	if(cnt==n+1){
		for(int i=1; i<=n; ++i){
			for(int j=0; j<=n; ++j){
				if(j==a[i]){
					cout << " Q";
				}
				else if(j==0){
					printf("%2d", n-i+1); 
				}
				else{
					cout << "  ";
				}
			}
			cout << endl;
		}
		printf("   a");	
		for(int i=1; i<=n-1; ++i){
			printf("%2c", 'a'+i);
		}
		cout<<endl<<endl;
	}
	//看第cnt行要放在第几列，i遍历列 
	for(int i=1; i<=n; ++i){
		//如果第cnt行第i列没有放棋子，并且第i列没有放棋子
		//并且在cnt行i列放棋子不会产生冲突，才可以放 
		if(vis[cnt][i]==0 && vis1[i]==0 && ok(cnt, i)){	
			vis[cnt][i]=1;
			vis1[i]=1;
			a[cnt]=i;	
			dfs(cnt+1);
			vis[cnt][i]=0;	
			vis1[i]=0;			
		}
	}
}
int main()
{
	cin >> n;
	dfs(1);
	return 0;
}


1313: 【USACO】城堡


版权声明：本文为u013313909原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。