二叉树遍历+最短路

xuanxiao2024 · 2024-08-14 17:04:02 · 个人记录

扩展二叉树

由于把空节点用 . 来表示，就意味着碰到 . 这个子树就结束了。
直接 DFS

Code

#include <iostream> 
#include <cstdio> 
#include <algorithm> 
#include <cmath>
#include <string>
using namespace std;
typedef long long ll;
string a;
ll w = 0;

void dfs_mid(){
    char c = a[w];
    if(a[w++] == '.') return ;
    dfs_mid();
    cout << c;
    dfs_mid();
    return ;
}

void dfs_end(){
    char c = a[w];
    if(a[w++] == '.') return ;
    dfs_end();
    dfs_end();
    cout << c;
    return ;
}

int main(){
    cin >> a;
    w = 0;
    dfs_mid();
    cout << "\n";
    w = 0;
    dfs_end();
    return 0;
} 

遍历问题

首先如果一个点只有一条边， 那么他就能摇摆(海草海草随风飘摇)，答案就会乘二


怎样才能判断只有一条边？当一个节点和另一个在前序中相邻的节点，前序和中序遍历反过来的时候！

样例分析

abc                           
cba

在这一串里面，有两个相互颠倒的，答案就是 2 ^ {2} 。

Code

由于先序和后序遍历不太一样，所以要用两个for循环来找相反的

#include <iostream> 
#include <cstdio> 
#include <algorithm> 
#include <cmath>
#include <string>
using namespace std;
typedef long long ll;
ll cnt = 0;

int main(){
    string a,b;
    cin >> a >> b;
    for(int i = 0;i < a.size() - 1;i++){
        for(int j = 1;j < b.size();j++){
            if(a[i] == b[j] && a[i + 1] == b[j - 1]) cnt++;
        }
    }
    cout << (1ll << (cnt));
    return 0;
} 

P1144 最短路计数 - 洛谷 | 计算机科学教育新生态

这一题可以借鉴 \text{DP} 的思想
还记得我们写过的过河卒，我们每次从相邻的地方获取答案(当然是走过的)。
这题也可以这么干。

从 1 跑到其他点，每次路过时:

• 如果自己是最优的且第一个到达，那么记录答案，放入队列，将这里的 dp_{i} 设为走到这里来的点。
• 如果自己是最优的但不是第一个到达，那么记录答案，就不放入队列了，浪费空间
• 如果自己不是最优的，直接 \text{Good\,bye}

样例分析

从1开始，到1，只有一种方法(显然)。
到2，最短只能从 1 来，所以只有一种
到3，最短只能从 1 来，所以只有一种
到4，最短既可以从2来，也可以从三来，所以有两种。
到5，最短只能从 4 来，由于有重边，从任意一条走都行，所以有4种

Code

#include <iostream> 
#include <cstdio> 
#include <algorithm> 
#include <cmath>
#include <queue>
#include <string>
#include <vector>//火车头
using namespace std;
typedef long long ll;
struct node{
    ll x,step;
};
vector<ll> G[1000005];
ll n,m,ans[1000005],mn[1000005];

void add_edge(ll s,ll e){
    if(s == e) return ;
    G[s].push_back(e);
    G[e].push_back(s);
    return ;
}

void bfs(){
    queue<node> q;
    q.push({1,0});
    mn[1] = 0;
    ans[1] = 1;
    while(q.size() > 0){
        node x = q.front();
//      cout << x.x << " " << x.step << " " << mn[x.x] << " " << ans[x.x] << "\n";
        q.pop();
        for(int i = 0;i < G[x.x].size();i++){
            ll nx = G[x.x][i];
            if(mn[nx] > x.step + 1){
                mn[nx] = x.step + 1;
                ans[nx] = ans[x.x] % 100003;
                q.push({nx,x.step + 1});
            }else if(mn[nx] == x.step + 1){
                ans[nx] += ans[x.x] % 100003;
            }
            ans[nx] %= 100003;
        }
    }
    return ;
}

int main(){
    cin >> n >> m;
    for(int i = 1;i <= m;i++){
        ll s,e;
        cin >> s >> e;
        add_edge(s,e);
    }
    for(int i = 1;i <= n;i++){
        mn[i] = 1e18;
    }
    bfs();
    for(int i = 1;i <= n;i++){
        cout << ans[i] << "\n";
    }
    return 0;
}