专栏文章

3-30 图论小测总结

ccaizimo
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipp1t8h
此快照首次捕获于
2025/12/03 15:37
3 个月前
此快照最后确认于
2025/12/03 15:37
3 个月前
查看原文

考试情况

题目考试分数考试总分
T1【深基18.例3】查找文献0分\color{#E74C3C}0分160分160分
T2 [NOIP 2017 提高组] 奶酪40分\color{#FADB14}40分
T3 [NOIP 2015 提高组] 信息传递没交没交
T4 [USACO3.4] 美国血统 American Heritage100分{\color{#22AB22}100分{}}
T5 [NOIP 2004 普及组] FBI 树没交没交
T6 [蓝桥杯 2019 省 AB] 完全二叉树的权值20分\color{#E74C3C}20分

比赛传送门

题目总结

T1【深基18.例3】查找文献

错误原因

没有看见题目里说的“按顺序输出”，没有排序，所以得了0分

正确思路

一道基础的搜索，先DFS，再BFS，记得一定要排序！
代码如下：

AC Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=2e6+10;
int n,m,vis[N];
vector<int> g[N];
void dfs(int cur){
    if(vis[cur]==1) return ;
    vis[cur]=1;
	cout<<cur<<' ';
	for(auto nx : g[cur]){
		dfs(nx);
	}
	return;
}
void bfs(int cur){
	queue<int> q;
	q.push(cur);
	vis[cur]=1;
	while(q.size()){
		int x=q.front();
		q.pop();
		cout<<x<<' ';
		for(auto nx : g[x]){
			if(vis[nx]==0){
				vis[nx]=1;
				q.push(nx);
			}
		}
	}
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    	int x,y; cin>>x>>y;
    	g[x].push_back(y);
	}
	for(int i=1;i<=n;i++){
		sort(g[i].begin(),g[i].end());//一定要排序
	} 
	dfs(1);
	memset(vis,0,sizeof vis);
	cout<<endl;
	bfs(1);
    return 0;
}

T2 [NOIP 2017 提高组] 奶酪

错误原因

在开根号时，函数没有定义成浮点数，导致数据有误，丢了60分

正确思路

一道经典的并查集问题，代码很长。
题意是：现在有n+2个点，如果任意两个点之间距离不超过2r，就算可以通过，求能否从点0到点h。
思路是：运用并查集可以合并两个集合的特性，将每个点看做一个集合，如果可以通过就将两个点合并，最终检查是否每个点都在一个集合上面。

AC Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=2e6+10;
struct node{
	double x,y,z;
}a[N];
double n,h,r;
int fa[N];
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void unionn(int x,int y){
	x=find(x); y=find(y);
	if(x!=y){
		fa[x]=y;
	}
	return;
}
double check(int i,int j){
	double p1=abs(a[i].x-a[j].x)*abs(a[i].x-a[j].x);
	double p2=abs(a[i].y-a[j].y)*abs(a[i].y-a[j].y);
	double p3=abs(a[i].z-a[j].z)*abs(a[i].z-a[j].z);
	double q=sqrt(p1+p2+p3);
	return q;
}
void solve(){
	cin>>n>>h>>r;
	for(int i=0;i<=n+1;i++){
		fa[i]=i;
	}
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y>>a[i].z;
		if(a[i].z<=r){
			unionn(i,0);
		}
		if(a[i].z+r>=h){
			unionn(i,n+1);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(check(i,j)<=2*r){
				unionn(i,j);
			}
		}
	}
	if(find(0)==find(n+1)) cout<<"Yes\n";
	else cout<<"No\n";
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t; cin>>t;
	while(t--){
		solve();
	} 
    return 0;
}

T3 [NOIP 2015 提高组] 信息传递

正确思路

本场考试最难的一题。
思路：这道题看似很复杂，需要每次传递信息，还要实时更新信息，但我们可以把要传递的信息去掉，看做传递每个点，因为我们稍微一想就可以得知，如果要得到自己的信息，那么一定是自己把自己的信息传递出去，又传递回来，想到这里，我们就会想到图论中的环，从自己开始转了一圈，又回到自己，不就是环吗？那么现在我们就想到解法了——判环，我们可以利用并查集可以判断是否有环的特性，每次判断，如果自己有环，输出，如果没有环，那么就把自己的信息传递给下一个要传递的人，然后在判断下一个。

AC Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=2e5+10;
int cnt=0,ans=INT_MAX,fa[N];
int find(int x){
	cnt++;
	if(fa[x]==x) return x;
	return find(fa[x]);
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n; cin>>n;
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<=n;i++){
		int t; cin>>t;
		cnt=0;
		if(find(t)==i){
			ans=min(ans,cnt);
		}
		else fa[i]=t;
	}
	cout<<ans;
    return 0;
}

T4 [USACO3.4] 美国血统 American Heritage

正确思路

这题就很简单了，只需要利用二叉树的前、中序遍历，求出后序遍历，跟手推差不多，但是注意一个坑，此题是先输入中序，再输入后序（别问我怎么知道的，考试时卡了半个小时）。

AC Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=2e6+10;
void solve(string q,string z){
	if(q.size()<=0){
		return ;
	}
	char root=q[0];
	int pos=z.find(root);
	solve(q.substr(1,pos),z.substr(0,pos));
	solve(q.substr(pos+1),z.substr(pos+1));
	cout<<root;
	return;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	string q,z;
	cin>>z>>q;
	solve(q,z);
    return 0;
}

T5 [NOIP 2004 普及组] FBI 树

正确思路

考试时把题目想的太复杂了，没认真思考。
思路：这题其实也很简单，就是每次把s串分成左右子树，一直递归到≤1，接着按照规则输出‘F’、‘B’、‘I’。

AC Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=2e6+10;
char fbi(string s){
	int len=s.size();
	int cnt=0;
	for(int i=0;i<len;i++){
		if(s[i]=='0') cnt++;
	}
	if(cnt==0) return 'I';
	else if(cnt==len) return 'B';
	return 'F';
}
void dfs(string s){
	int len=s.size();
	if(len==1){
		cout<<fbi(s);
		return;
	}
	dfs(s.substr(0,len/2));
	dfs(s.substr(len/2));
	cout<<fbi(s);
	return;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n; string s;
	cin>>n>>s;
	dfs(s);
    return 0;
}

T6 [蓝桥杯 2019 省 AB] 完全二叉树的权值

错误原因

骗分代码，用pow函数计算点，在加起来比较（用pow其实可以，但我多算了一次pow）

正确思路

思路：每次输入把x加入ans，接着把本层点数加加，然后判断本层是否到了末尾，如果到了，就比较，接着清空本层点数和总值。

AC Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=2e6+10;
int k=1,maxn=-1,maxi,ans,sum;
int a[N];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n; cin>>n;
	for(int i=1;i<=n;i++){
        int x; cin>>x;
        ans+=x;
        sum++;
        if(sum==pow(2,k-1)||i==n){
            if(ans>maxn) maxn=ans,maxi=k;
            ans=sum=0;
            k++;
        }
    }
    cout<<maxi<<endl;
    return 0;
}

总结

这次发挥失误了，还是细节处理不到位，以后听课要更细心，做题要更仔细。

886

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...