分数 25

dfs 图的遍历

将序列中的元素依次入队，使用深度优先搜索，从队列的第一个元素进行搜索。
如果当前节点能到达队列中下一个节点，则搜索下一个节点；
如果不能到达队列中的下一个节点：
a. 如果当前结点能够到达其他结点，则不是DFS序列；
b. 如果不能到达其他结点，则回溯，返回到上一个结点继续搜索。（WA代码由于未回溯至上一个节点而是回溯至底继续搜索队列里的下一个结点）

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include#define int long long
#define xx first
#define yy second
#define ump unordered_map
#define us unordered_set
#define pq priority_queue
#define rep(i, a, b) for(int i=a;i=b;--i)
using namespace std;
typedef pairPII;
const int N=10005, inf=0x3f3f3f3f3f3f3f3f, mod=1e9+7;
int n, m, k, g[1010][1010], vis[1010], flag=1;
vectorvec[1010];
queueq;
sets;
inline int rd(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void dfs(int x){
	if(flag==0||q.empty()){
		return;
	}
	vis[x]=1;
	while(!q.empty()){
		if(g[x][q.front()]==1){
			int y=q.front();
			q.pop();
			dfs(y);
		}
		else{
			rep(i, 0, vec[x].size()){
				if(!vis[vec[x][i]]){
					flag=0;
					return;
				}
			}
			return;
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	n=rd(), m=rd(), k=rd();
	while(m--){
		int x=rd(), y=rd();
		g[x][y]=1;
		vec[x].push_back(y);
	}
	while(k--){
		memset(vis,0,sizeof vis);
		flag=1;
		while(!q.empty()){
			q.pop();
		}
		s.clear();
		rep(i, 0, n){
			int x=rd();
			q.push(x);
			s.insert(x);
		}
		while(!q.empty()){
			int y=q.front();
			q.pop();
			dfs(y);
		}		
		if(flag==0||s.size()!=n){
			puts("no");	
		}
		else{
			puts("yes");	
		}
	}
	return 0;
}

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include#define int long long
#define xx first
#define yy second
#define ump unordered_map
#define us unordered_set
#define pq priority_queue
#define rep(i, a, b) for(int i=a;i=b;--i)
using namespace std;
typedef pairPII;
const int N=10005, inf=0x3f3f3f3f3f3f3f3f, mod=1e9+7;
const double Exp=1e-8;
//int t, n, m, cnt, ans;
int n, m, k; 
bool g[108][108];
bool st[N];
vectorq;
inline int rd(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
bool ch(){
	memset(st, 0, sizeof st);
	// 对每个结点，检查下一个结点是否合法
	rep(i, 0, q.size()-1){
		st[q[i]]=true;
		// 如果当前节点已访问，返回否
		if (st[q[i]]) return false; 
		if(st[q[i+1]]){
			return false;
		}
		// 下一个节点走过的话肯定false
		if(g[q[i]][q[i+1]]){
			continue;
		}else{// 如果下个节点联通
			rep(j, 1, n+1){// 如果序列的下一个结点不连通，并且存在一个已联通且未访问的结点
				if(g[q[i]][j]&&!st[j]){
					return false;
				}
			}
		}
	}
	return true;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	n=rd(), m=rd(), k=rd();
	memset(g, 0, sizeof g);
	while(m--){
		int a=rd(), b=rd();
		g[a][b]=true;
	}
	// resize函数  重定义容器大小
	q.resize(n);
	while(k--){
		rep(i, 0, n){
			q[i]=rd();
		}
		bool fl=ch();
		if(fl){
			puts("yes");
		}else{
			puts("no");
		}
	}
	return 0;
}

分数 30

树 dfs

使用深度优先搜索保存层序遍历，再根据 父节点编号 = (子结点编号 - 1) / 度数 得出结点到根节点的路径。

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include#define int long long
#define xx first
#define yy second
#define ump unordered_map
#define us unordered_set
#define pq priority_queue
#define rep(i, a, b) for(int i=a;i=b;--i)
using namespace std;
typedef pairPII;
const int N=55, inf=0x3f3f3f3f3f3f3f3f, mod=1e9+7;
const double Exp=1e-8;
//int t, n, m, cnt, ans;
// pre存储前序遍历序列 le存储层序遍历序列 n d k如题意 p前序遍历节点下标
int pre[N], le[N], n, d, k, p; 
inline int rd(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
void dfs(int u){
	if(u>=n){
		return;
	}
	le[u]=pre[p++];
	rep(i, 1, d+1){
		dfs(u*d+i);
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	n=rd(), d=rd();
	rep(i, 0, n){
		pre[i]=rd();
	}
	dfs(0);
	printf("%lld", le[0]);
	rep(i, 1, n){
		printf(" %lld", le[i]);
	}
	puts("");
	k=rd();
	while(k--){
		int x=rd();
		while(x){
			printf("%lld ", le[x]);
			x=(x-1)/d;
		}
		printf("%lld\n", le[0]);
	}
	return 0;
}

2022夏PAT甲级题解 by小柳2022.6.7

原创不易
转载请标明出处
如果对你有所帮助 别忘啦点赞支持哈

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧