c++ - ACM问题，，ACM高手快来看下啊！

问题描述

问 题

题目链接在此

http://bailian.openjudge.cn/p...

从网上找到了解释：

思路：刚开始想的是构造一个二叉树，后来想想并不需要，了解树转二叉树的原理，便可以发现转换后某点的深度为父节点的深度加上它是父节点的第几个子节点，所以直接从根节点按以上规律搜索一遍即可

#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
#include <queue>  
#include <functional>  
#include <cctype>  
#include <cmath>  
using namespace std;  
  
const int N = 100100;  
char s[N];  
int res1, res2;  
void dfs(int &i, int dep1, int dep2)  
{  
    res1 = max(res1, dep1);  
    res2 = max(res2, dep2);  
    int cnt  = 1;  
    while(true && s[i])  
    {  
        if(s[i] == 'd')  
            dfs(++i, dep1 + 1, dep2 + cnt), cnt++;  
        else  
        {  
            i++;  
            return;  
        }  
    }  
}  
int main()  
{  
    while(~ scanf(" %s", s))  
    {  
        int i = 0;  
        res1 = res2 = -1;  
        dfs(i, 0, 0);  
        printf("%d => %d\n", res1, res2);  
    }  
    return 0;  
}  

但是并没有看懂，(；′⌒`)，希望高手能详细解释解释，不胜感激！！

解决方案

这个其实不难，我修改了下代码，写了点注释，你可以看看。
加了点输出语句，显示下搜索计算的过程

> ./a.out               
dudduduudu
0 --d-> 1 [T(0),BT(0),son_nu(1)]
0 <-u-- 1 
0 --d-> 2 [T(1),BT(1),son_nu(2)]
        2 --d-> 3 [T(1),BT(2),son_nu(1)]
        2 <-u-- 3 
        2 --d-> 4 [T(2),BT(3),son_nu(2)]
        2 <-u-- 4 
0 <-u-- 2 
0 --d-> 5 [T(2),BT(4),son_nu(3)]
0 <-u-- 5 
2 => 4

修改的代码如下

#include <cstdio>  
#include <algorithm>  
#include <cmath>
#include <vector>
using namespace std;  
  
const int N = 100100;  
char s[N];  
int curTreeDep, curBtreeDep;    // 当前一般树和二叉树的深度

// ======>>> 添加输出部分，可删除
int nodeID = 0;
std::vector<int> searchStack;
int tabscount = 0;
// <<<===== 添加输出部分结束


void dfs(int &i, int treeDep, int btreeDep)  
{
    // 以传入的深度与当前深度中的较大者为当前深度
    curTreeDep = max(curTreeDep, treeDep);  
    curBtreeDep = max(curBtreeDep, btreeDep);  

    // 第几个子(当前搜索到的节点是)
    int son_nu = 1;
    while(s[i])  
    {  
        // d 为往下搜索，说明访问的是一个子节点
        if(s[i] == 'd'){

            // ======>>> 添加输出部分，可删除
            for(int i = 0; i< tabscount;++i){
                printf("        ");
            }
            ++tabscount;

            printf("%d --d-> %d [T(%d),BT(%d),son_nu(%d)]\n",
                        searchStack.back(),++nodeID,
                        curTreeDep,curBtreeDep,son_nu);
            searchStack.push_back(nodeID);
            // <<<===== 添加输出部分结束

            // 递归下去继续访问
            dfs(++i, treeDep + 1, btreeDep + son_nu);
            // 当上面调用完成，说明是遇到了 u 
            // 也就是向上访问父节点
            // 所以这里son_nu要加1，表示再次遇到d的时候
            // 这个访问节点是第几个孩子
            ++son_nu;
        }
        else{
            // ======>>> 添加输出部分，可删除
            --tabscount;
            for(int i = 0; i< tabscount;++i){
                printf("        ");
            }
            int sid = searchStack.back();
            searchStack.pop_back();
            printf("%d <-u-- %d \n",searchStack.back(),sid);
            // <<<===== 添加输出部分结束

            ++i;    // i自增，下一个
            return;    // 递归结束控制
        }  
    }  
}  
int main()  
{  
    if(scanf("%s", s) < 1){
        printf("%d => %d\n", 0,0);  
        return 0;
    }

    int i = 0;  
    curTreeDep = curBtreeDep = -1;
    searchStack.push_back(nodeID);
    dfs(i, 0, 0);  
    printf("%d => %d\n", curTreeDep, curBtreeDep);  
    return 0;  
}

这篇关于c++ - ACM问题，，ACM高手快来看下啊！的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！