Pre-Post、Rational Arithmetic

Rational Arithmetic（有理数运算）

题目描述：

For two rational numbers, your task is to implement the basic arithmetics, that is, to calculate their sum, difference, product and quotient.

实现对两个有理数的基本运算，包括加、减、乘、除。

输入：

Each input file contains one test case, which gives in one line the two rational numbers in the format “a1/b1 a2/b2”. The numerators and the denominators are all in the range of long int. If there is a negative sign, it must appear only in front of the numerator. The denominators are guaranteed to be non-zero numbers.

每个输入文件只包含一个测试用例，测试用例会给出一行数据，格式为“a1/b1 a2/b2”。
分子分母的范围都在长整型的范围内，如果数字为负，则符号只会出现在分子的前面。分母一定是非零数。

输出：

For each test case, print in 4 lines the sum, difference, product and quotient of the two rational numbers, respectively. The format of each line is “number1 operator number2 = result”. Notice that all the rational numbers must be in their simplest form “k a/b”, where k is the integer part, and a/b is the simplest fraction part. If the number is negative, it must be included in a pair of parentheses. If the denominator in the division is zero, output “Inf” as the result. It is guaranteed that all the output integers are in the range of long int.

针对每个测试用例，都输出四行，分别是这两个有理数的和、差、积和商，格式为“数1 操作符 数2 = 结果”。注意，所有的有理数都将遵循一个简单形式“k a/b”，其中k是整数部分，a/b是最简分数形式，如果该数为负数，则必须用括号包起来。如果除法中的除数为0，则输出“Inf”。结果中所有的整数都在long int的范围内。

示例：

输入：
2/3 -4/2
输出：
2/3 + (-2) = (-1 1/3)
2/3 – (-2) = 2 2/3
2/3 * (-2) = (-1 1/3)
2/3 / (-2) = (-1/3)

输入：
5/3 0/6
输出：
1 2/3 + 0 = 1 2/3
1 2/3 – 0 = 1 2/3
1 2/3 * 0 = 0
1 2/3 / 0 = Inf

题目分析：func(m, n)的作用是对m/n的分数进行化简。
gcd(t1, t2)的作用是计算t1和t2的最大公约数。
在func函数中，先看m和n里面是否有0（即m*n是否等于0）。
如果分母n=0，输出Inf。
如果分子m=0，输出”0″。
flag表示m和n是否异号，flag=true表示后面要添加负号”(-“和括号”)”，再将m和n都转为abs(m)和abs(n)，即取他们的正数部分方便计算。
x = m/n为m和n的可提取的整数部分，先根据flag的结果判断是否要在前面追加”(-“，然后根据x是否等于0判断要不要输出这个整数位。
接着根据m%n是否等于0的结果判断后面还有没有小分数，如果m能被n整除，表示没有后面的小分数，那么就根据flag的结果判断要不要加”)”，然后直接return。
如果有整数位，且后面有小分数，则要先输出一个空格，接着处理剩下的小分数，先把m分子减去已经提取出的整数部分，然后求m和n的最大公约数t，让m和n都除以t进行化简。
最后输出“m/n”，如果flag==true还要在末尾输出”)”

    #include <iostream>
    #include <vector>
    #include <cmath>
    
    using namespace std;
    
    long long a, b, c, d;
    long long gcd(long long t1, long long t2) {//gcd()是用来求最大公因数的
    return t2 == 0 ? t1 : gcd(t2, t1 % t2);
    }
    
    void func(long long m, long long n) {//判断分母或分子中是否有0
    if (m * n == 0) {
        printf("%s", n == 0 ? "Inf" : "0");
        return ;
    }
    
    bool flag = ((m < 0 && n > 0) || (m > 0 && n < 0));//分子分母符号是否相同
    m = abs(m); //求m的绝对值
    n = abs(n);//求n的绝对值
    long long x = m / n;//可被提取出来的整数部分
    printf("%s", flag ? "(-" : "");//符号不同加(-
    if (x != 0) 
        printf("%lld", x);//输出整数位
        
    if (m % n == 0) {//可以整除，没有小数位 
        if(flag) 
        printf(")");
        return ;
    }
    
    if (x != 0) 
    printf(" ");//输出空格
    m = m - x * n;//输出小数位的分子
    long long t = gcd(m, n);//求新的分子分母的最大公因式
    m = m / t; n = n / t;
    printf("%lld/%lld%s", m, n, flag ? ")" : "");
    }
    
    int main() {
    scanf("%lld/%lld %lld/%lld", &a, &b, &c, &d);
    func(a, b); printf(" + "); func(c, d); printf(" = "); func(a * d + b * c, b * d); printf("\n");
    func(a, b); printf(" - "); func(c, d); printf(" = "); func(a * d - b * c, b * d); printf("\n");
    func(a, b); printf(" * "); func(c, d); printf(" = "); func(a * c, b * d); printf("\n");
    func(a, b); printf(" / "); func(c, d); printf(" = "); func(a * d, b * c);
    return 0;
    }

Pre-Post（前序和后序）

题目描述：

We are all familiar with pre-order, in-order and post-order traversals of binary trees. A common problem in data structure classes is to find the pre-order traversal of a binary tree when given the in-order and post-order traversals. Alternatively, you can find the post-order traversal when given the in-order and pre-order. However, in general you cannot determine the in-order traversal of a tree when given its pre-order and post-order traversals. Consider the four binary trees below:

我们都很熟悉二叉树的前序、中序和后序遍历。在数据结构类中，通常会遇到给定中序和后序的情况下求前序的问题，或是给定前序和中序求后序的问题。但一般情况下，当给定树的前序和后序时，并不能确定树的中序遍历。例如下面的这四个二叉树：
All of these trees have the same pre-order and post-order traversals. This phenomenon is not restricted to binary trees, but holds for general m-ary trees as well.

它们都拥有着相同的前序和后序。其实这种情况不仅仅限于二叉树，M叉树也是一样。

输入：

Input will consist of multiple problem instances. Each instance will consist of a line of the form m s1 s2 indicating that the trees are m-ary trees, s1 is the pre-order traversal and s2 is the post-order traversal.All traversal strings will consist of lowercase alphabetic characters. For all input instances, 1 <= m <= 20 and the length of s1 and s2 will be between 1 and 26 inclusive. If the length of s1 is k (which is the same as the length of s2, of course), the first k letters of the alphabet will be used in the strings. An input line of 0 will terminate the input.

输入是由多个测试用例组成。每个用例只有一行，格式为m s1 s2，表示树是m叉树，s1是前序遍历，s2是后序遍历。所有字符串将由小写字母字符组成。对于所有的输入实例，1<=m<=20，s1和s2的长度将介于1和26之间（含1和26）。如果s1的长度是k（当然，s2也是这么长），那使用的就是字母表的前K个字母。输入一行0表示终止输入。

输出：

For each problem instance, you should output one line containing the number of possible trees which would result in the pre-order and post-order traversals for the instance. All output values will be within the range of a 32-bit signed integer. For each problem instance, you are guaranteed that there is at least one tree with the given pre-order and post-order traversals.

对于每个测试用例都要输出一行，表示中序遍历满足该条件的数的个数。输出的范围不会超过int的范围，对于每条用例，都保证至少有一棵树满足要求。

示例：

输入：
2 abc cba
2 abc bca
10 abc bca
13 abejkcfghid jkebfghicda
输出：
4
1
45
207352860

分析：

假设我们的前序是abejkcfghid，后序是jkebfghicda，那么我们根据前序，就能知道：
1、最多可以有13颗子树，也就是每一层都有13个可能位置
2、a是根，第一课子树的根是b
3、通过后树我们能知道，b的子树有j、k、e、b共四个结点
4、再回到前序，向前走4个结点，下一棵子树的根是 c
5、以此类推，最终得到 a 为根的下一层共有 3 棵子树
好了三颗子树长这样：
前序 bejk cfghi d
后序 jkeb fghic d
则这一层一共的可能性就是13个空位随便挑3个摆这3颗子树，那么有C _{13}^3种可能。
之后再递归处理b这棵子树，bejk|jkeb，看以b为根时下一层有多少棵子树。可以看出，只有一棵以e为根的子树，那么可能性就只有C _{13}^1种。再递归ejk|jke这棵树，可能情况自然是C _{13}^2种，递归cfghi|fghic这棵树，可能情况是C _{13}^4种。故而最终结果将会是：C _{13}^3C _{13}^1 C _{13}^2*C _{13}^4种。最终算出这个结果即可。

输入的三个数m、s1、s2分别为：m叉树，范围在1-20之间。s1是先序遍历，s2是后序遍历，长度在1-26之间。如果s1与s2长度相同为k的话，则只输出前k个字母。输入0终止程序。
输出可能导致实例的前后遍历的可能树的数量。其实总结起来就是分析每个树有多少个子树，递归思想可以解决。

    # include<iostream>
    # include<string>
    
    using namespace std;
    
    int arr[21][21];
    string a1,a2;
    void initArr();
    
    long long Cal(string s1,string s2,int m)
    {
    int i,j=0,n=0;
    long long sum=1;
    int len=s1.length();
    s1.erase(s1.begin());//从s1中删除s1.begin()中的元素
    s2=s2.substr(0,s2.length()-1);//指定字符串开始和结尾的位置
    while(s1.length()>j)
    {  
        for(i=j;i<s1.length();i++)
        {
            if(s1[j]==s2[i])
                {
                    sum=sum*Cal(s1.substr(j,i-j+1),s2.substr(j,i-j+1),m);
                j=i+1;
                n++;
                break;
                }
         } 
    }
    sum=sum*arr[n][m];
    return sum;
     
    }
    void initArr()
    {
    int i,j;
    arr[0][1]=arr[1][1]=1;
    for(i=2;i<21;i++)
    {
        arr[0][i]=1;
        for(j=1;j<=i;j++)
        {
            if(j==i)
            arr[j][i]=1;
            else arr[j][i]=arr[j-1][i-1]+arr[j][i-1];
        }
    }
    }
     
    int main()
    {
       int m;
       string  s1,s2;
       long long sum;
       while(cin>>m>>s1>>s2)
       {
      int len=s1.size();
         if (len==0)
        break;
        
      initArr();
        sum=Cal(s1,s2,m);
        cout<<sum<<endl;
    }
       return 0;
    }