洛谷 P5461 赦免战俘

自从选拔赛以来就没怎么认真刷题，总是感觉有点累，有点缺少动力。晚上做了到洛谷的基础题，调了1个多小时。。。

明明是一道很简单的递归题，还做了这么久，挺打击的，感觉自己真的是菜。递归可以说是所有算法的基础中的基础了，如果递归都理解的这么吃力，学习其他算法的困难可想而知，感觉自己还差得远，有点迷茫。

题目背景

借助反作弊系统，一些在月赛有抄袭作弊行为的选手被抓出来了！

题目描述

现有 2^n\times 2^n (n\le10)2n×2n(n≤10) 名作弊者站成一个正方形方阵等候 kkksc03 的发落。kkksc03 决定赦免一些作弊者。他将正方形矩阵均分为 4 个更小的正方形矩阵，每个更小的矩阵的边长是原矩阵的一半。其中左上角那一个矩阵的所有作弊者都将得到赦免，剩下 3 个小矩阵中，每一个矩阵继续分为 4 个更小的矩阵，然后通过同样的方式赦免作弊者……直到矩阵无法再分下去为止。所有没有被赦免的作弊者都将被处以棕名处罚。

给出 nn，请输出每名作弊者的命运，其中 0 代表被赦免，1 代表不被赦免。

题目很简单，但是数据的值很大，需要高精度，c++的话需要自己写一个高精度运算。

题目描述

用高精度计算出 S=1!+2!+3!+⋯+n!S=1!+2!+3!+⋯+n!（n≤50n≤50）。

其中“!”表示阶乘，例如：5!=5×4×3×2×15!=5×4×3×2×1。

输入格式

一个正整数 nn。

输出格式

一个正整数 SS，表示计算结果。

7-1 Is It An AVL Tree (25 point(s))

In computer science, an AVL tree (Georgy Adelson-Velsky and Evgenii Landis’ tree, named after the inventors) is a self-balancing binary search tree. It was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one. (Quoted from wikipedia)

For each given binary search tree, you are supposed to tell if it is an AVL tree.

Input Specification:

Each input file contains several test cases. The first line gives a positive integer K (≤10) which is the total number of cases. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary search tree. The second line gives the preorder traversal sequence of the tree with all the keys being distinct. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in a line “Yes” if the given tree is an AVL tree, or “No” if not.

Sample Input:

1
2
3
4
5
6
7

3
7
50 40 36 48 46 62 77
8
50 40 36 48 46 62 77 88
6
50 40 36 48 46 62

Sample Output:

1
2
3

Yes
No
No

题目给出前序遍历的序列，可以利用这个序列一个一个插入来生成一棵树。之后再逐个计算节点因子判断是否为AVL树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

#include <iostream>
#include <algorithm>
using namespace std;

struct Node
{
    int value;
    Node *Left;
    Node *Right;
    Node(int _value): value(_value), Left(NULL), Right(NULL) {}
};

Node* insert(Node *p, int value);
int getHeight(Node *p);
bool AVLJudge(Node *p);

int main(int argc, const char *argv[])
{
    int K;
    cin >> K;
    while(K--)
    {
        int N;
        cin >> N;
        Node *Tree = NULL;
        for(int i = 0; i < N; i++)
        {
            int tmp;
            cin >> tmp;
            Tree = insert(Tree, tmp);
        }
        cout << (AVLJudge(Tree) ? "Yes" : "No") << endl;
    }

    return 0;
}


Node* insert(Node *p, int value)
{
    if(p == NULL)
        p = new Node(value);
    else
    {
        if(value < p->value)
            p->Left = insert(p->Left, value);
        else
            p->Right = insert(p->Right, value);
    }
    return p;
}


int getHeight(Node *p)
{
    if(p == NULL)
        return 0;
    else
        return max(getHeight(p->Left), getHeight(p->Right)) + 1;
}

bool AVLJudge(Node *p)
{
    if(p == NULL)
        return true;
    else
    {
        if(abs(getHeight(p->Left) - getHeight(p->Right)) > 1)
            return false;
        return AVLJudge(p->Left) && AVLJudge(p->Right);
    }
}

代码参考了https://www.cnblogs.com/littlepage/p/13194704.html

这代码写得挺妙的，每一步都有利用递归。

树结点的插入：

1
2
3
4
5
6
7
8
9
10
11
12
13

Node* insert(Node *p, int value)
{
    if(p == NULL)
        p = new Node(value);
    else
    {
        if(value < p->value)
            p->Left = insert(p->Left, value);
        else
            p->Right = insert(p->Right, value);
    }
    return p;
}

利用函数的返回值来修改原值，避免了修改传入参数导致原值没有被修改。调用时记得要赋值Tree = insert(Tree, tmp);

判断结点：

1
2
3
4
5
6
7
8
9
10
11

bool AVLJudge(Node *p)
{
    if(p == NULL)
        return true;
    else
    {
        if(abs(getHeight(p->Left) - getHeight(p->Right)) > 1)
            return false;
        return AVLJudge(p->Left) && AVLJudge(p->Right);
    }
}

利用了尾递归将判断结果传回。

三月了，终于算是开学了。这还是我到目前为止第一个在学校的春季学期，去年由于疫情，整整一个学期都一直呆在家里，没来学校，及其缺少自制力，以至于浪费了太多的时间，没怎么学到什么东西，有点后悔。
到目前为止，大学生活已经差不多过去了一半了，想想自己还是一事无成。有很多都想学习，但真正能够坚持下来的又很少，放假前决定好好学算法和日语，但是现在开学了，我日语一看没看，算法也是想到搞搞，没有集中精神地训练，现在甚至有点想放弃了，因为实在是难度太高，需要大量的时间，不知道盲目坚持对我是否是个错误，是不是应该用这些时间去做一些对自己未来更有用的，是否应该去找一些时间效益更高的事。
但是真正让我找点其他事做我又想不出干啥，很纠结。其实说到底我还是不知道自己想干什么，活了这么久还是没活明白，也是挺搞笑的。

反转二叉树，虽然不是BST但也是树相关的题目，就也写一下吧。

The following is from Max Howell @twitter:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

记录一下210124-210126的长沙之旅

其实我本来对长沙是没什么兴趣的，但是我莫名其妙的就去了一次长沙，现在对长沙改观挺大的，对这个城市现在也蛮有好感了。

这次去长沙的契机还要从几个月前说起，当时是看完成都的超级斩，回去的出租车上跟当时认识的兄弟聊，听说了他们可能有去长沙的计划。我一个对长沙没什么兴趣的突然就来劲了，感觉也可以去一下，毕竟时间也不是很紧，顺便当次旅游，毕竟疫情在家关了大半年了，开学学校也一直封校出不去，今年实在是憋太久了。