洛谷 p1249 最大乘积

题目大意

将N分解成若干个互不相同数字之和，求乘积的最大值。

思路

利用 lna + lnb = ln(a + b)，将乘积的最大值转换为和的最大值。题目就可以化解为，从1, 2, 3…n中选出一些数是他们的和最大。

相当于是一个01背包问题和一个高精度乘法。

题目描述

一个正整数一般可以分为几个互不相同的自然数的和，如 3=1+23=1+2，4=1+34=1+3，5＝1+4=2+35＝1+4=2+3，6=1+5＝2+46=1+5＝2+4。

现在你的任务是将指定的正整数 nn 分解成若干个互不相同的自然数的和，且使这些自然数的乘积最大。

洛谷P1012 [NOIP1998 提高组] 拼数

题目描述

设有 nn 个正整数 a_1 \dots a_na1…a**n，将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。

输入格式

第一行有一个整数，表示数字个数 nn。

第二行有 nn 个整数，表示给出的 nn 个整数 a_ia**i。

输出格式

一个正整数，表示最大的整数

输入输出样例

输入 #1

1
2

3
13 312 343

输出 #1

1

34331213

输入 #2

1
2

4
7 13 4 246

输出 #2

1

7424613

说明/提示

对于全部的测试点，保证 1 \leq n \leq 201≤n≤20，1 \leq a_i \leq 10^91≤a**i≤109。

题目有点脑筋急转的意思，刚开始看到有点无从下手，看了题解后才发现这题目很巧妙。几个数字组成一个最大的数字，就相当于结果的字符串，字典序最大，这样一来就可以用排序做了。

STL的比较函数也很有意思

洛谷P1923 求第k小的数

题目描述

输入 nn(n<5000000n<5000000 且 nn 为奇数) 个数字 a_i(0<a_i<10^9)a**i(0<a**i<109) ，输出这些数字的第 kk 小的数。最小的数是第 0 小。

请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。

洛谷 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.

今天做算法笔记上的题目又碰到了反转链表。题目不难，但是写起来就是感觉脑子有点绕，也可能只是我水平太差的原因。

这已经是我第三次碰到这道题了，第一次是大一下开学期末考的时候，当时在机房写了一个多小时，我自己测试都是对的，而且基本上考虑到了所有的情况，但是每次提交都有几个测试点通不过，甚至还换了一种方法重新写了一遍还是不过，当时真的感觉心态有点崩了。

考完了之后还是不服，把题目重新看了一下，才发现题目上说是带有头结点的链表。。。我真的是要脑溢血了，上课的时候老师还在强调不要用头结点，平时作业也没有用过头结点，考试的时候出一道带有头结点的题，我根本没注意到。不过这样也好，从此以后看题目就更加注重这种细节了。