[Python知识库]2021-08-27

前言

我觉得今天过得不行，可能我想我放弃，那就放弃吧！

现在开始，打起精神，你正在做的事明天的事情，去把明天的事情给完成！

算法

AcWing 896.最长上升子序列||

思路：

1. $N$ 的数据范围是1e5；
2. Dp转移方程f[i] = max(f[i], f[k]+1);
3. 如果以第j位结尾和以第k位结尾的长度相同，那么就取a[j]和a[k]较小的那一个，小的那个数更加有可能构成最长上升子序列；
4. 那么每次都存下每种长度，数值最小的那一位；
5. “长度比你长，数值还比你小，就更容易构成答案”；
6. a[i]小于a[i]的最大的长度后面；
7. 找小于a[i]的最大的数可以用二分来实现；
8. 假设找到的最大的数是a[k],那么就更新q[k + 1] = min(q[k + 1], a[k]);
9. 不会更新q[1]~q[k]的值，因为a[1]~a[k]的值都小于a[i];
10. 不会更新q[k+2]~end的值，因为q[k+2]到结尾的值都排在a[i]的前面；
11. 二分复杂度$O(logn)$;
12. 二分步骤：（1）确定二分范围；（2）默写模板；（3）设计check函数，答案在check函数的边界位置；

AC代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N];
int q[N];  //用来存下标长度的最小值是哪一个a[i]

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    int len = 0;  //len表示当前最长长度
    for (int i = 0; i < n; i ++ )
    {
        int l = 0, r = len;  //确定二分范围
        while (l < r)
        {
            int mid = l + r + 1 >> 1;  //l = mid要上取整
            if (q[mid] < a[i])  //设计check函数 
                l = mid;  //q[mid]<a[i]可能是答案，放到区间内
            else 
                r = mid - 1;  //q[mid]>=a[i]一定不是答案，放到区间外
        }
        len = max(len, l + 1);  //每次更新最大长度
        q[l + 1] = a[i];  //a[i]这个数字一定比q[l+1]存的数字小，不然不会二分到这里
    }

    printf("%d\n", len);

    return 0;
}

背单词

1. pasture
2. martyr
3. impart
4. earthenware
5. bud

俯卧撑 * 50

高等数学

仰卧起坐 * 100

python语法

1. 匿名函数

   square = lambda x:x*x  #第一个x相当于参数
   square(9)