树（4） 图（2）

· · 算法·理论

P1229 遍历问题

思路

正常情况，我们都会想到暴力，那么暴力就是生成一个里面所有字母的全排列，假装这是中序，然后根据中序和后序求出先序，判断这个先序是否和给出先序相等，如果相等，则这个排列合法，否则不合法。

然而这种思路很容易就会超时，只适用于字符串长度 \le 10 的情况。

我们先来建一个树。

显而易见的，这棵树的 1 号节点可以随便摆动，并没有固定，而 2 号节点被固定了，不能摆动， 3 号节点也没有被固定。

这种没有被固定的节点，我们数一下有多少个节点，假设这种节点有 n 个，那么最终的答案为 2^n 。

Code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
string a,b;
signed main()
{
    cin>>a>>b;
    int ans=0;
    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]) ans++;
        }
    }
    ans=pow(2,ans);
    cout<<ans;
    return 0;
}

P1144 最短路计数

思路

我们先把双向图建好，然后跑一遍 BFS ，用来求最短路。

为了维护每个点的步数，我们还要建一个数组 dp （不是动态规划），来储存每个点的最短步数。

如果这个点是第一次走到，那么将这个点的时间储存下来，标记，塞入队列，如果这个点到达的时间比之前的更优，我们依然要更新答案，为了维护这个，还得建一个数组 sj 表示第一次走到这里的答案。

Code：

#include<bits/stdc++.h>
#define mod 100003
using namespace std;
const int N=1e6+5;
int n,m;
bool vis[N];
int sj[N],dp[N];
vector<int> g[N];
struct no{
    int x;
    int step;
};
void bfs()
{
    queue<no> q;
    dp[1]=1;
    q.push(no{1,0});
    sj[1]=0,vis[1]=1;
    while(!q.empty())
    {
        no tmp=q.front();
        q.pop();
        int u=tmp.x;
        for(int i=0;i<g[u].size();++i)
        {
            int v=g[u][i];
            if(!vis[v])
            {
                vis[v]=true;
                dp[v]=dp[u];
                sj[v]=tmp.step+1;
                q.push(no{v,tmp.step+1});
            }
            else if(tmp.step+1<=sj[v])
            {
                dp[v]+=dp[u];
                dp[v]%=mod;
            }
        }
    }
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    memset(sj,0x3f,sizeof(sj));
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    bfs();
    for(int i=1;i<=n;++i) cout<<dp[i]<<'\n';
    return 0;
}

The End.