子集（阿里巴巴）

image-20220321132728299

我们需要求严格上升的子序列，求严格上升的子序列也是leetcode上的经典题型最长递增子序列，而此题稍作变换，需要求两个数组的严格上升子序列。

我们可以先对x排序，x是上升的，但并不是完全单调上升，因为有相等的x。若假设我们的x是严格单调的的话，这个题就可以转化为，对y求严格单调上升子序列的长度问题即最长递增子序列。（贪心加二分查找）

而对于x相等的情况，我们不妨令y在前的排在前面，这样可以避免重复计算。

1
2
3
4
1    2    2    5
10   21   19   32 
这里我们对x相等的y进行从大到小的排序，这时候结果是3，符合题意，因为x相等如果y是从小到大的话，
有可能统计重复的x, 我们让y降序排列的话就破坏了y单调上升的可能，不会重复统计x;

这里用贪心能全部过，如果暴力的使用动态规划O(n^2)全不过……（或许也可能是我动态规划写错了….）

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
struct Node {
    int x;
    int y;

};
bool cmp(Node& a, Node& b) {
    if (a.x == b.x)return a.y > b.y;
    return a.x < b.x;
}
void func() {
    int n; cin >> n;
    vector<Node>nodes(n+1, Node{ 0,0 });
    for (int i = 1; i <= n; i++) {
        cin >> nodes[i].x;
    }
    for (int i = 1; i <= n; i++) {
        cin >> nodes[i].y;
    }

    sort(nodes.begin()+1, nodes.end(), cmp);

    int sum = 0;
    vector<int>tails(n + 1, -1);//贪心数组
    int end = 0;
    for (int i = 1; i <= n; i++) {
        if (tails[end] < nodes[i].y) {
            end++;
            tails[end] = nodes[i].y;
        }
        else {
            int l = 0; int r = end;
            while (l + 1 != r) {
                int mid = l + ((r - l) >> 1);
                if (tails[mid] >= nodes[i].y) {
                    r = mid;
                }
                else l = mid;
            }
            tails[r] = nodes[i].y;
        }
    }
    cout << end << endl;
}
int main()
{
    int T;
    cin >> T;
    for (int j = 0; j < T; j++) {
        func();
    }
    return 0;
}

x^n+y^n的值（阿里巴巴）

image-20220321133548601

思路：（转自牛客）

image-20220321133707886

这就是一道找规律的题目，还是很简单，但是提交上去死活过不了，因为取模有问题，这题中间可能有负数的情况，而题目的意思是结果取完模后不应该有负数，因此我们应该每次取模应该加上模数。（血的教训啊）dp[i] = ((A * dp[i - 1]) % M - (B * dp[i - 2]) % M + M) % M;这题观察动态转移方程组是可以缩减空间复杂度的降至O(1)

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
//x0+y0 2
//x1+y1 A
//x2+y2 (x1+y1)*(x1+y1)-x1y1*(x0+y0)
//x3+y3 (x1+y1)*(x2+y2)-x1y1*(x1+y1)
//x4+y4 (x1+y1)*(x3+y3)-x1y1*(x2+y2)
//x5+y5 (x1+y1)*(x4+y4)-x1y1*(x3+y3)
//x6+y6 (x1+y1)*(x5+y5)-x1y1*(x4+y4)
const int M = 1e9 + 7;
void func() {
    long long A, B, n;//xy = B;x + y = A
    cin >> A >> B >> n;
    vector<long long>dp(n + 1, 0);
    dp[0] = 2;
    dp[1] = A % M;//x+y
    for (int i = 2; i <= n; i++) {
        dp[i] = ((A * dp[i - 1]) % M - (B * dp[i - 2]) % M + M) % (M);//注意要加M后继续取模M避免得到负数结果
    }
    cout << dp[n] << endl;
}
int main()
{
    int T;
    cin >> T;
    for (int j = 0; j < T; j++){
        func();
    }


    return 0;
}

树高不超过m的n节点二叉树总数（阿里巴巴）

image-20220321134634716

image-20220321141805986

image-20220321141756282

必须要学会拆解问题，动态规划

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
#include <iostream>
using namespace std;

const int M = 1e9 + 7;

long long dp[55][55];
long long N;
long long H;

int main()
{
    cin >> N >> H;
    
    for (int h = 0; h <= H; h++) {
        dp[0][h] = 1;//0个节点，不管限制高度是多少结果都应该为1
    }

    for (int n = 1; n <= N; n++) {		 //节点数目
        for (int h = 1; h <= H; h++) {	 //数高
            for (int k = 0; k < n; k++) {//两个子树相乘0~n-1
                dp[n][h] = (dp[n][h] + dp[k][h - 1] * dp[n - k - 1][h - 1] + M)%M;
            }
        }
    }
    cout << dp[N][H] << endl;

    return 0;
}