【wikioi】1029 遍历问题
遍历 问题 wikioi
2023-09-27 14:22:22 时间
题目链接:http://www.wikioi.com/problem/1029/
算法:数学
本题有个2小技巧。
- 一棵二叉树的前序遍历a1a2a3...ai和后序遍历b1b2b3...bi有一种关系:当只有一棵子树的根 在a序列下标为i, 在b序列下标为b
有 a[i-1] == b[j+1]
这是因为当根只有一棵子树时,前序和后序遍历都是先遍历它的孩子,而且是唯一的一个孩子,所以相对位置是一样的。 - 当确定了一棵树的前序和后序遍历时,可以得到用如上方法找到只有一棵子树的根,并且因为上面的性质,子树在为左子女还是右子女并不影响前序后序的顺序,但影响中序遍历的顺序,而可以假设子树为左子女也可以假设为右子女,那么我们得到:
根据前后序得到中序遍历的数量 = 只有一个子女的根 ^ 2
那么答案就好求啦~
代码:
#include <iostream> #include <string> using namespace std; int i, j, s, c; int main() { string a, b; cin >> a >> b; s = a.size(); for(i = 1; i < s; ++i) for(j = s-2; j >= 0; --j) if(a[i] == b[j] && a[i-1]==b[j+1]) c++; cout << (1<<c); return 0; }
相关文章
- 遍历文件夹下的子文件夹的时候,文件夹名字包含逗号或者空格
- Java 遍历文件夹里面的全部文件、指定文件
- Java 集合List、Set、HashMap操作三(查找List中的最大最小值、遍历HashTable、List元素替换、List查找位置)
- 递归解决遍历问题
- enumerate 遍历numpy数组
- Elasticsearch 分页与遍历 From, Size,Search After & Scorll API
- shell遍历多个数组
- 【LeetCode】二叉树的遍历与构建问题
- 微信小程序中的循环遍历问题
- 90、【树与二叉树】leetcode ——104. 二叉树的最大深度:层次遍历+DFS+子问题分解(C++版本)
- delphi如何按照控件的左右顺序来遍历窗体中的每个控件 [问题点数:20 http://bbs.csdn.net/topics/380216822
- 6.2 二叉树遍历
- cocos2d-x 3.0 android mk文件 之 自己主动遍历*.cpp文件
- 二叉树3种遍历的非递归算法
- 马的遍历问题
- Django工程中使用echarts怎么循环遍历显示数据
- 33Sql数据删除与遍历
- 【leetcode】102:二叉树的层序遍历