3-30 图论小测总结

· · 个人记录

考试情况

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

比赛传送门

题目总结

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

错误原因

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

正确思路

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

AC Code

#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

#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

#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

#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

#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

#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